-
Notifications
You must be signed in to change notification settings - Fork 107
/
nCr.cpp
75 lines (59 loc) · 1.66 KB
/
nCr.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
#define int long long
const int N = 1000001;
using namespace std;
// array to store inverse of 1 to N
int factorialNumInverse[N + 1];
// array to precompute inverse of 1! to N!
int naturalNumInverse[N + 1];
// array to store factorial of first N numbers
int fact[N + 1];
// Function to precompute inverse of numbers
void InverseofNumber(int p)
{
naturalNumInverse[0] = naturalNumInverse[1] = 1;
for (int i = 2; i <= N; i++)
naturalNumInverse[i] = naturalNumInverse[p % i] * (p - p / i) % p;
}
// Function to precompute inverse of factorials
void InverseofFactorial(int p)
{
factorialNumInverse[0] = factorialNumInverse[1] = 1;
// precompute inverse of natural numbers
for (int i = 2; i <= N; i++)
factorialNumInverse[i] = (naturalNumInverse[i] * factorialNumInverse[i - 1]) % p;
}
// Function to calculate factorial of 1 to N
void factorial(int p)
{
fact[0] = 1;
// precompute factorials
for (int i = 1; i <= N; i++) {
fact[i] = (fact[i - 1] * i) % p;
}
}
// Function to return nCr % p in O(1) time
int Binomial(int N, int R, int p)
{
// n C r = n!*inverse(r!)*inverse((n-r)!)
int ans = ((fact[N] * factorialNumInverse[R])
% p * factorialNumInverse[N - R])
% p;
return ans;
}
int main()
{
int p = 1000000007;
InverseofNumber(p);
InverseofFactorial(p);
factorial(p);
// 1st query
int N = 15;
int R = 4;
cout << Binomial(N, R, p) << endl;
// 2nd query
N = 20;
R = 3;
cout << Binomial(N, R, p) << endl;
return 0;
}