### F-35's blog

By F-35, history, 6 days 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^__^

 » 6 days 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 
•  » » 6 days ago, # ^ |   0 thanks but how to calculate N! in log(n)?
•  » » 6 days 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.
•  » » » 6 days ago, # ^ |   0 so we can calculate n! % mod only using linear solution?
•  » » » » 6 days ago, # ^ |   +35 See this. The main idea is sqrt decomposition and Lagrange interpolation. The complexity is .
•  » » » » » 6 days ago, # ^ |   0 Thank you so much :)
 » 6 days 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.