백준11401 이항 계수3

작성일 | In

문제 링크

  • http://icpc.me/11401

사용 알고리즘

  • Mudulo Inverse

풀이

(a + b) % mod = (a % mod) + (b % mod)
(a - b) % mod = (a % mod) - (b % mod)
(a × b) % mod = (a % mod) × (b % mod)
위 3가지 모두 성립하지만, 나눗셈에 대해서는 성립하지 않습니다.
나눗셈은 역수를 곱하는 것으로 치환할 수 있듯이 모듈러 연산의 곱셈 역원을 곱하는 것으로 대체할 수 있습니다.

이 문제에서 mod는 1e9+7, 즉 소수입니다.
정수 a와 소수 p가 있을 때, 법 p에서 ap와 a는 합동입니다.
즉, ap ≡ a (mod p)입니다.
또한, ap-1 ≡ 1 (mod p)입니다.

따라서 ap-1 = a × ap-2 ≡ 1 (mod p)입니다.
ap-2가 a × t ≡ 1 (mod p)를 만족하는 t이므로, 역원은 ap-2입니다.

팩토리얼을 이용한 nCr 공식을 이용해 적당히 구해주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod = 1e9 + 7;

// a ^ mod-2

ll mul(ll a, ll b, ll c){
	if(b == 1) return a;
	if(b == 0) return 1;
	ll now = mul(a, b/2, c);
	now *= now; now %= c;
	if(b&1){
		now *= a; now %= c;
	}
	return now;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	ll n, k; cin >> n >> k;

	ll t1 = 1;
	for(int i=n; i>=n-k+1; i--){
		t1 *= i; t1 %= mod;
	}
	ll t2 = 1;
	for(int i=1; i<=k; i++){
		t2 *= i;
		t2 %= mod;
	}
	t2 = mul(t2, mod-2, mod);

	ll ans = t1 * t2 % mod;
	cout << ans;
}