Firstly, we denote the multiplicative inverse of x mod p as inv(x,p).

- use dp method to calculation x! mod p for x=1 ~ n (1<=n<p, p is some prime)
- calculate inv(n!,p) utilize Extended Euclidean algorithm.
- use dp again to calculate inv(x!,p) for x=n-1 ~ 1 with the fact inv(x!,p) * x = inv((x-1)!, p)
- now, if we want to now inv(x,p) for some x in [1,n], we only need to calculate (x-1)! * inv(x!,p)

Or just do the following:

Great! I've seen that approach once before and since then I was trying to find it again. It's some kind of magic, but I'm going to understand how that works...

Maybe this will help :)

Thanks, it helped a lot

It's quite easy to explain how it works. Let's take simple equation and do some transformations with it:

UPD: too slow

but doesnt a muplicative inverse of x mod p only exist when gcd(x,p) == 1,how do you find the muplicative inverse of a range if some of them dont exist

We can only use this approach if we have prime modulo p and want to calculate inverse in range [1, p).

got it,thank you

i have seen this approach in rng_58's solution.

I know that this is like 6 years old, but this post shows up a lot on Google, and I wanted to mention that you can omit the last

`% p`

.Challange: p = 113513 look at the value of inv[3] :)

That's just because the multiplication between p/i and inv[p%i] overflows, I think.

If so, another good warning for future searches is: Don't forget to declare inv as a long long array (or cast to a long long before multiplying)!

2. calculate inv(x!,p)Do you mean inv(n!,p)?

we only need to calculate (x-1)! * inv(x,p)Do you mean (x-1)! * inv(x!,p)?

Yes, you are right. :p Now I fix it.

Nice method! The also exists O(NloglogN) dp solution, which is slower, but seems to be very easy to implement. Let f[x] be the smallest prime, which divides x. We can calculate f[x] for all x in range 1...n using sieve of Eratosthenes. Then we can calculate inv[x] using formula inv[x]=(inv[x/f[x]]*inv[f[x]])%mod.

If write good sieve of Eratosthenes, it works O(n).

Yes, you are right.

Can you share your most optimized code about sieve Eratosthenes?

Is the following function correct to calculate nCr? ( n Choose r )

(inv[x] is Modular Multiplicative Inverse of x!(x factorial) and fac[x] is x!. i64 is macro of long long. modL is large prime number.)

Yes it is.

`(((333333336*500000004)%1000000007)*120)%1000000007 is 20.`

I tried to calculate

5C2and found it 20 from this function.The correct output is 10.

this and this sites are used for calculation.

Well you don't need inverse of 3 and 2 you need the inverse of 3! = 6 and 2! = 2 (because nCr is equal to n! / ( r! * (n — r)! ) so 5C2 is ( 5! * inverse[6] * inverse[2] ) % 1000000007 = ( 120 * 166666668 * 500000004 ) % 1000000007 = 10.

Since, r! and (n-r)! both are denominator, I'm confused whether following operation is valid or not.

`i64 c=(inv[r]*inv[n-r])%modL;`

sorry, i wrote this under wrong blog announcement