### Hd7's blog

By Hd7, history, 15 months ago,

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!

• 0

 » 15 months ago, # |   +7
•  » » 15 months ago, # ^ |   0 thank u
 » 15 months ago, # |   0 I found a link: e-maxxStuff: 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]$.
•  » » 12 months ago, # ^ |   0