1

How do I find C (n , r) mod k where 

0 < n,r < 10^5
k = 10^9 + 7 (large prime number)

I have found links to solve this using Lucas theorem here.

But this wouldn't help me in cases where my n , r, K all are large. The extension of this problem is :-

Finding sum of series like :-

(C(n,r) + C(n, r-2) + C(n, r-4) + ...... ) % k

Original constraints hold.

Thanks.

aaditya chauhan
  • 55
  • 5

4 Answers4

3

I know algorithm with complexity O(r*log_n) Firstly look at algorithm to calc C(n,r) without mod k:

int res = 1;
for(int i=1; i<=r; i++){
  res*=(n+1-i);
  res/=i;
}

In your case, you can't divide, because you use modular arithmetics. But you can multiply on the modular multiplicative inverse element, information about it you can find here https://en.wikipedia.org/wiki/Modular_multiplicative_inverse. You code will be like this:

int res = 1;
for(int i=1; i<=r; i++){
  res*=(n+1-i);
  res%=k;
  res*=inverse(i,k);
  res%=k;
}
Mikhail Kasparyan
  • 135
  • 2
1

This is a typical use case for dynamic programming. Pascal's triangle gives us

C(n, r) = C(n-1, r) + C(n-1, r-1)

Also we know 

C(n, n) = 1
C(n, 0) = 1
C(n, 1) = n

You can apply modulus to each of the sub-results to avoid overflow. Time and memory complexity are both O(n^2)

saby
  • 158
  • 1
  • 1
  • 7
0

I think, the faster way will be using modular inverse.

Complexity will be as low as log(n)

for example

ncr( x, y) % m will be

a = fac(x) % m;
b = fac(y) % m;
c = fac(x-y) % m;

now if you need to calculate (a / b ) % m you can do (a % m) * ( pow( b , m - 2) % m ) // Using Fermat’s Little Theorem

https://comeoncodeon.wordpress.com/2011/10/09/modular-multiplicative-inverse/

Sumsuddin Shojib
  • 3,583
  • 3
  • 26
  • 45
0

C(n,r) = n!/(r!(n-r)!) = (n-r+1)!/r!

As k is a prime, for every r < k we can find its modular multiplicative inverse r^-1 using Extended Euclidean algorithm in O(lg n).

So you may calculate ((n-r+1)!/r) % k as (((n-r+1)! % k) * r^-1) % k. Do it over 1~r then you will get the result.

Gary Sham
  • 503
  • 4
  • 10