Calculate combination nCk with module??

Revision en1, by Hd7, 2019-09-01 17:04:48

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!

Tags #combinatorics

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Hd7 2019-09-01 17:04:48 769 Initial revision (published)