Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

mr_warlock's blog

Calculate nCr mod p^x
By mr_warlock, history, 19 months ago, In English

I am stuck on this following problem:

Statement:

Given n, r, x and P where P is a PRIME number.

Print the value nCr % P^x

Constraints:

1 <= r <= n <= 1e12
2 <= x <= 20
2 <= P^x <= 1e6

Thanks for reading the problem. It will be really helpful if you can give me a solution.

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

»
19 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

When we try to find out (a * b) % m, then ((a % m) * (b % m)) % m will also give the same answer. Because it follows the commutative property. But during (a / b) % m if we do ((a % m) / (b % m)) % m, it will give us the wrong answer. Because it does not follow the commutative property.

In your case nCr = n! / (r! * (n — r)!). So to find this answer with mod. You need to use modular inverse. Learn modular inverse first. Then you will understand everything.

→ Reply
  • »
    »
    19 months ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +11 Vote: I do not like it

    Yes I can do modulo inverse in r! and (n-r)!
    But the problem arise when I have to calculate the factorial as its constraints is very big
    What if n is 1e12 and r is 5e11... It cant fit the timelimit in trivial way!

    Thanks for your time.

    → Reply
    • »
      »
      »
      19 months ago, hide # ^ |
       
      Vote: I like it +1 Vote: I do not like it

      Ops! My bad I didn't notice the constraints and your rating. I thought that it was just for the modular inverse. sorry :)

      → Reply
»
19 months ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

I've got good news and bad news. The good news is that this paper has the answer, and is an interesting read overall. The bad news is that the authors really did not write with programmers in mind.

→ Reply
»
19 months ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

https://cp-algorithms.com/combinatorics/binomial-coefficients.html#binomial-coefficient-for-large-n-and-small-modulo

This?

→ Reply
  • »
    »
    19 months ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    yes yes but this method only works if M is prime what if M is not ptime but prime power

    Cant find a way :(

    → Reply
    • »
      »
      »
      19 months ago, hide # ^ |
       
      Vote: I like it +1 Vote: I do not like it

      When $$$m$$$ is not square-free, a generalization of Lucas's theorem for prime powers can be applied instead of Lucas's theorem.

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

It can be solved by exLucas algorithm. To study it, search on the Internet.

ExLucas can solve $$$\binom nm\mod p$$$ of any $$$0\le m\le n$$$ and $$$0 \lt p\le 10^6$$$.

This is my code if you want to have a look.

If anybody found mistake in code, feel free to reply.

exLucas
→ Reply