### Eddagdeg's blog

By Eddagdeg, history, 2 years ago,

Hello coders! let's suppose we have three numbers n,k,mod=1e9+7 where n,k<=1e9 how to calculate nCk %mod! any hint please! Thanks^__^

• 0

 » 2 years ago, # | ← Rev. 2 →   -18 You can calculate N! in O(log(N)) using Matrix Multiplication, then calculate N! / [ K! * (N — K)! ] % mod How ? (only when mod is prime) (A / B) % mod = A * Pow(B, mod — 2) % mod 
•  » » 2 years ago, # ^ |   0 thanks but how to calculate N! in log(n)?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +16 If you can calculate n! in O(log(n)) then you have solved prime checking in O(log3(n)) or something. See this.
•  » » » 2 years ago, # ^ |   0 so we can calculate n! % mod only using linear solution?
•  » » » » 2 years ago, # ^ |   +35 See this. The main idea is sqrt decomposition and Lagrange interpolation. The complexity is .
•  » » » » » 2 years ago, # ^ |   0 Thank you so much :)
•  » » » 5 weeks ago, # ^ |   +8 Doesn't Wilson's theorem give a $\mathcal{O}(\log n)$ time primality check in that case?
•  » » » » 4 weeks ago, # ^ |   -16 lol no, how you can calculate (p — 1)! % p in log(n)?
•  » » » » » 4 weeks ago, # ^ |   0 The comment I was replying to said " If you could compute $n!$ in $\mathcal{O}(\log n)$ you'd have a $\mathcal{O}(\log^3 n)$ primality check". Note that no claim is made that there is a $\mathcal{O}(\log n)$ algorithm for computing the factorial.
•  » » » » » » 4 weeks ago, # ^ |   0 sorry for carelessness
 » 2 years ago, # |   +23 Another approach is precalculate 106!, (2·106)!, ..., 109! locally and paste it in your code. Then you can easily calculate every factorial using 106 multiplications.
 » 5 weeks ago, # | ← Rev. 2 →   -11 How about prime power? For example, mod = 289. If mod is a prime, you can use Lucas theorem: https://en.wikipedia.org/wiki/Lucas%27s_theorem
•  » » 5 weeks ago, # ^ |   0 Thanks.
 » 5 weeks ago, # | ← Rev. 2 →   0 Way 1: Precalculate the factorials. Then, use Fermat's Little theorem, which says that says that $a^{-1} \equiv a^{p - 2} \pmod{p}$. This allows us to sort of transform modular division into modulo multiplication and then some powers. The pre-computing factorial is $O(n)$, dealing with the denominator is $O(\log(N))$ if you use fast exponentiation. Way 2: Pascal's Identity. Straight forward dynamic programming. This is $O(n^2)$. Optimization: Use Lucas's theorem.
•  » » 5 weeks ago, # ^ |   0 I think you didn't realize that $n = 10^9$ which makes pre computing of factorials $O(n)$ is impossible within time and memory limit
•  » » » 4 weeks ago, # ^ |   -10 I was speaking generally, which is why I included Way 2, which is clearly too slow. I think with Lucas's theorem, Way 1 would be sufficiently fast, though.
•  » » 4 weeks ago, # ^ |   +10 How would you optimize it using Lucas's theorem?
 » 4 weeks ago, # | ← Rev. 2 →   -10 You can calculate C(n,k) = n! * reverse((n — k)!) * reverse(k!) which reverse(a) = power(a, mod — 2)If you have enough memory, you can save first a! into an array