astrothegod's blog

Finding binomial coefficient with big n, k and mod
By astrothegod, history, 4 months ago, In English

The problem is calculate nCk with n <= 10^18, k <= 10^6 and mod = 10^9 + 7. Can anyone give me some hints or pesudo code. Thanks

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe this will help https://www.geeksforgeeks.org/compute-ncr-p-set-3-using-fermat-little-theorem/

→ Reply
»
4 months ago, # |
← Rev. 4   Vote: I like it +19 Vote: I do not like it

just calc,k is small

n!/(n-k)!k!

as (n-k) is big, you can do simplify

→ Reply