Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### Heisenbug's blog

By Heisenbug, 9 years ago,

Is there a stupid trick to calculate n-choose-k for a range of n with k always the same, which is faster than forming the full Pascal's triangle? With some fixed k, I need to calculate all n-choose-k modulo 10^9+7 for n up to 100,000 but there's no way I can calculate all the coefficients within 3 seconds.

• +3

 » 9 years ago, # |   -11 C(N, K) = N! / (K! * (N — K)!) => C(N + 1, K) = C(N, K) * (N + 1) / (N + 1 — K), that's obvious.I think, you don't know how to perform the division, so please read about modular multiplicative inverse.
 » 9 years ago, # |   +17 You can divide by x over a prime modulus M by multiplying by xM - 2. This lets you use factorial formula for n choose k.
 » 9 years ago, # |   +8 Well, for that task you don't even need the fact that K is constant, if you precalculate all the factorials, you can answer the nCk query in logarithmic time.
•  » » 9 years ago, # ^ | ← Rev. 2 →   0 Won't you answer the query in O(1) time then?
•  » » » 9 years ago, # ^ |   +1 Nope, you will need to calculate modular inverse(O(logN)).
•  » » » » 9 years ago, # ^ |   0 Actually, you can calculate modular inverse O(1) with O(n) pre-calculate.Let rv[x] is the inverse of x under M, then rv[x] = rv[M % x] * (M — M / x) % M and of course rv[1] = 1.
•  » » » » » 9 years ago, # ^ |   0 That's awesome!! I'm eager to know why it works. Would you explain please?
•  » » » » » » 9 years ago, # ^ |   +1 let M = kx + r, r < x, then k = M / x, r = M % x and both multiple rv[x] we will get so,