n8118's blog

ncr for large values of n
By n8118, history, 9 years ago, In English

how to calculate ncr % M when the value of n has greater range(n <= 10^12). M = 10^9 + 7.

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

Comments Comments (5)
| Write comment?
»
9 years ago, # |
  Vote: I like it -6 Vote: I do not like it

See Lucas' Theorem

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

For small M you can use Lucas's theorem.
For small N you can use Pascal's triangle.
For small R you can juse use slow algo in O(RlogM) by using factorial-formula.

→ Reply
»
9 years ago, # |
  Vote: I like it -20 Vote: I do not like it

Please do not reply presently for this doubt as it is from a running contest https://www.codechef.com/FEB16/problems/STROPR

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Come on, if for example someone needs help with Dijkstra but there's some long challenge having a problem about Dijkstra's algorithm, do you think nobody should say a word about Dijkstra during the long contest? Moreover, where do you see that problem? I ran over all problems and the only one about permutations was this one — https://www.codechef.com/FEB16/problems/SEAPERMS. But I don't really see how it's related to the question asked in the blog and also N<=10^5 in the Codechef's problem.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Actually, it is related . I just solved it that way. But yes you are right. There's no harm helping him with what he has asked. Because even if he manages to find this, he still has a lot more to do.

      → Reply