백준13977 이항 계수와 쿼리

작성일 | In

문제 링크

  • http://icpc.me/13977

시간복잡도

  • 전처리 이후 쿼리당 O(1)

풀이

nCr = n! / ( r! * (n-r)! )입니다.

전처리 단계에서 1! % mod부터 4000000! % mod까지 모두 구해주고, 역원도 모두 구해줍니다.
그러면 각 쿼리를 상수 시간 안에 처리할 수 있습니다.

전체 코드

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
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll fac[4040404];
ll inv[4040404];
const ll mod = 1e9+7;

ll pw(ll a, ll b){
	ll ret = 1;
	while(b){
		if(b & 1) ret = ret * a % mod;
		b >>= 1;
		a = a * a % mod;
	}
	return ret;
}

void init(){
	fac[0] = 1;
	for(int i=1; i<=4000000; i++) fac[i] = fac[i - 1] * i % mod;
	inv[4000000] = pw(fac[4000000], mod-2);
	for(int i=3999999; i>=0; i--){
		inv[i] = inv[i+1] * (i + 1) % mod;
	}
}

ll ncr(ll n, ll r){
	ll ret = fac[n];
	ret = ret * inv[r] % mod;
	ret = ret * inv[n-r] % mod;
	return ret;
}

void solve(){
	ll n, r; cin >> n >> r;
	cout << ncr(n, r) << "\n";
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	init();
	while(t--) solve();
}