I see a lot of people handling nCk with module(1e9+7) like that?
vector<ll> inv(h+w+1);
vector<ll> fact(h+w+1);
vector<ll> fact_inv(h+w+1);
inv[1] = 1;
for(int i=2; i<h+w+1; i++){
inv[i] = MOD - (MOD/i) * inv[MOD%i] % MOD;
}
fact[0] = 1;
fact_inv[0] = 1;
for(int i=1; i<h+w+1; i++){
fact[i] = fact[i-1]*i % MOD;
fact_inv[i] = fact_inv[i-1]*inv[i] % MOD;
}
auto comb = [&](int n, int k){
if (n<0 || k<0) return 0LL;
if (n < k) return 0LL;
return fact[n]*fact_inv[n-k] % MOD * fact_inv[k] % MOD;
};
What I can infer is that inv[i]
is 1/i
. Now, i don't understand the way they calculate inv[i]
? Let me a more detailed explanation about that. Thanks in advance!
Modular inverse
thank u
I found a link: e-maxx
Stuff: At last line, just move $$$i$$$ from right to left become $$$i^{-1} = r[i]$$$ and $$$m\ mod\ i$$$ from left to right and become $$$ (m\ mod\ i)^{-1} = r[m\ mod\ i]$$$.
This link is writen in English