dreamoon_love_AA's blog

By dreamoon_love_AA, 7 years ago, , Firstly, we denote the multiplicative inverse of x mod p as inv(x,p).

1. use dp method to calculation x! mod p for x=1 ~ n (1<=n<p, p is some prime)
2. calculate inv(n!,p) utilize Extended Euclidean algorithm.
3. use dp again to calculate inv(x!,p) for x=n-1 ~ 1 with the fact inv(x!,p) * x = inv((x-1)!, p)
4. 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)  Comments (19)
 » Or just do the following: inv = 1; for (int i=2; i
•  » » 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 :)
•  » » » 7 years ago, # ^ | ← Rev. 2 →   It's quite easy to explain how it works. Let's take simple equation and do some transformations with it: p % i = p - (p / i) * i p % i = -(p / i) * i (mod p) // divide by i * (p % i) inv[i] = - (p / i) * inv[p % i] UPD: too slow
•  » » i have seen this approach in rng_58's solution.
•  » » 11 months ago, # ^ | ← Rev. 2 →   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 :)
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   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)?
•  » » 7 years ago, # ^ | ← Rev. 2 →   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.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   Can you share your most optimized code about sieve Eratosthenes?
 » Is the following function correct to calculate nCr? ( n Choose r ) i64 nCr(i64 n,i64 r) { i64 c=(inv[r]*inv[n-r])%modL; return (fac[n]*c)%modL; } (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 5C2 and found it 20 from this function. 333333336 is inverse modulus of 3 500000004 is inverse modulus of 2 120 is factorial of 5 1000000007 is a prime number 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 * inverse ) % 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;