“142857 = 27 * 11 * 13 * 37. You can find the result of nCr % m for each m = 27, 11, 13, 37.”
as 27 is not a prime, i hope we would have to resort to last method of finding all fact[n] and inverse-fact[n] for 27.
So we want nCr and we have x! for all x, WHY do we need inverse factorial ? Is it for (n-r)! and r!. To find inverse of (n-r) and r mod M and then multiply all of their factorials and then find % M.
and also one can’t do this by nCr=(n-1)Cr+(n-1)C(r-1)
given that the minimum space would be just 2 rows but
each of size r which in this case is 1000000000?
@imujjwalanand the last method described. Keep factorials and inverse-factorials modulo p. And you can get nCr % p in O(1) time with pre-computation of O§ and space O§
In Java this works quite ok for large N,K
private static BigInteger binomial(final int N, final int K) {
BigInteger ret = BigInteger.ONE;
for (int k = 0; k < K; k++) {
ret = ret.multiply(BigInteger.valueOf(N-k))
.divide(BigInteger.valueOf(k+1));
}
return ret;
Thank you for such a helpful answer, I have a conceptual doubt that why M needs to be prime for this for Modular
multiplicative inverse to be applied, I mean the condition is only that A and M should be coprime for the existence of inverse so M need not be prime for that.
Am I missing something , Can you please explain reason for M to be prime.
In c++ if you want to calculate nCr for large number of n and r, Here is the simplest logic to do that
void noOfCombination(int n, int k){
int i=0;
long long res=1;
if (k less_than n/2)
k = n - k;
for(i = 0; i less_than k; i++){
res *= (n-i);
res /= (i+1);
}
//output result
return;
}
Once i had to find C(n,r) mod p for very large n,r,p but p was prime. To be exact n<=(2e9) ,r<=(1e9) and p=(2e9)+33
I really googled it but got no answer. So finally came up with an idea and it worked so i thought to share it .please correct me if it might fail in any case:-
The basic idea was to divide n into parts such that we can find any factorial in O(N) time where N can be adjusted according to question’s complexity, i took N to be 1e5 because i had to calculate only 3 factorial per testcase. So i divided it into 20000 (it’s not random) groups each having product of all numbers in that group modulo p. 1st group contains number from 1 to 1e5 and 2nd group contains number from 1 to (2e5) and so on .generally ith group contains number from 1 to i*(1e5) let’s say we are keeping these values in array f[20001].
please keep f[0] equal to 1 and keep the value of groups starting from 1 index.
**Please don’t calculate your f array with in your program because that would be just stupid. I calculated with my IDE and kept it in a file and then copy ,pest **
Note:- if we increase the size of array f we can decrease the time to find factorial.
How to find factorial:-
let’s say we have to find factorial of any random number 1567394027
steps:-
This is only where M is prime … But in that particular problem M is not prime and so can we reduce it into Base form (And still Lucas Theorem Holds) ? And if we use CRT how can we use it ?