Блог пользователя Hd7

Автор Hd7, история, 5 лет назад, По-английски

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
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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