Hd7's blog

By Hd7, history, 5 years ago, In English

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!

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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]$$$.