Блог пользователя n8118

ncr for large values of n
Автор n8118, история, 9 лет назад, По-английски

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

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

See Lucas' Theorem

→ Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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.

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить