There is a test of Algorithms. Teacher provides a question bank consisting of N questions and guarantees all the questions in the test will be from this question bank. Due to lack of time and his laziness, Codu could only practice M questions. There are T questions in a question paper selected randomly. Passing criteria is solving at least 1 of the T problems. Codu can’t solve the question he didn’t practice. What is the probability that Codu will pass the test?
Input Format
First line contains single integer T denoting the number of test cases.
First line of each test case contains 3 integers separated by space denoting N, T, and M.
Output Format
For each test case, print a single integer.
If probability is p/q where p & q are co-prime, print (p*mulInv(q)) modulo 1000000007, where mulInv(x) is multiplicative inverse of x under modulo 1000000007.
Constraints
0 < T <= 10000
0 < N, T <= 1000
0 <= M <= 1000
M,T <= N
Sample Input and Output
Example 1
Input
1
4 2 1
Output
500000004
Explanation
The probability is 1⁄2. So output is 500000004.
CODE
Will be uploaded soon.
#include
int combinations(int n, int r)
{
int itr,numerator=1,denominator=1,result;
for(itr=1; itr<=r; itr++)
{
denominator = denominator*itr;
numerator = numerator*(n-(itr-1));
}
result = numerator/denominator;
return result;
}
int calGCD(int num1,int num2)
{
int rem;
while (1)
{
rem = num1 % num2;
if(rem == 0)
return num2;
if(rem != 0)
{
num1 = num2;
num2 = rem;
}
}
}
int mulInv(int a)
{
unsigned long long int m=1000000007,itr,b;
for (itr = 1; itr 0)
{
scanf(“%llu\t%llu\t%llu”,&qb_questions,&choosen,&learnt);
unknown = qb_questions – learnt;
waysOfChoosing = combinations(qb_questions,choosen);
waysOfFailing = combinations(unknown,choosen);
p = waysOfChoosing – waysOfFailing;
q = waysOfChoosing;
gcd = calGCD(p,q);
if(gcd != 1)
{
p=p/gcd;
q=q/gcd;
}
result = (p*mulInv(q))%1000000007;
printf(“%llu”,result);
T–;
}
return 0;
}
#include
#include
using namespace std;
int fact(int i)
{
if(i>1)
return i*fact(i-1);
else
return 1;
}
int gcdExtended(int a, int b, int *x, int *y)
{
// Base Case
if (a == 0)
{
*x = 0, *y = 1;
return b;
}
int x1, y1; // To store results of recursive call
int gcd = gcdExtended(b%a, a, &x1, &y1);
*x = y1 – (b/a) * x1;
*y = x1;
return gcd;
}
int modinv(int a, int m)
{
int x, y;
int g = gcdExtended(a, m, &x, &y);
int res = (x%m + m) % m;
return res;
}
void print(int q,int r)
{
if(r==0)
cout<<q;
else
{
cout<
}
import math
a=int(input())
n,m,t=list(map(int,input().split()))
s=float(t/m)
print(math.ceil(s*1000000007))
while b>1:
q = b//m2
t2 = m2
m2 = b % m2
b = t2
t2 = y
y = x – q * y
x = t2
if (x < 0):
x = x + m0
could you please explain why have you done this?
import math
from fractions import Fraction
m2 = 1000000007
t=int(input())
for i in range(t):
n,t,m = map(int,input().split())
prob=1-(((math.factorial(n-m))*(math.factorial(n-t)))/((math.factorial(n-m-t))*(math.factorial(n))))
if prob==0:
print(0)
elif prob==1:
print(1)
else:
num=Fraction(prob).numerator
den=Fraction(prob).denominator
a=num
b=den
while(den):
num, den = den, num % den
gcd=num
if gcd==1:
m0 = m2
y = 0
x = 1
while b>1:
q = b//m2
t2 = m2
m2 = b % m2
b = t2
t2 = y
y = x – q * y
x = t2
if (x < 0):
x = x + m0
print(x)
Output:-
1
4 2 1
500000004
while b>1:
q = b//m2
t2 = m2
m2 = b % m2
b = t2
t2 = y
y = x – q * y
x = t2
if (x < 0):
x = x + m0
could you please explain why have you done this?