[백준 13977] 이항 계수와 쿼리

문제 링크 => https://www.acmicpc.net/problem/13977

13977번: 이항 계수와 쿼리

---

이항 계수 (N K) 를 구하는 문제이다.

 

N, K 값의 범위가 최소 1에서부터 최대 4,000,000 으로 주어지며 테스트케이스는 최대 100,000까지 주어진다.

 

이항 계수 (N K) = N! / (N-K)!K! 에 대해서 Factorial를 구하는 방법을 생각해보면 O(N) 이 걸리는데 테스트케이스가 최대 100,000까지 주어졌으므로 O(NM), 즉, 시간초과가 난다.

 

따라서 Factorial 는 단순하게 dp를 통해 0~4,000,000 의 모든 Factorial 값을 미리 채워놓고 활용하는 것이다.

 

dp[0] = 1, for(int i=1; i<=4,000,000; i++) dp[i] = (i * dp[i-1]) % 1,000,000,007;  <= 1,000,000,007로 나눈 나머지여야 함

윗 식과 같이 미리 factorial 를 채우고 다음 작업을 진행하려고 한다. 

 

N! / (N-K)!K! = a (mod 1,000,000,007) 라고 가정하자.

 

그렇다면 N! = a * (N-K)!K! (mod 1,000,000,007) 이 될 것이고 우리는 (N-K)!K! 의 inverse를 x 라고 가정하자.

 

최종적으로 N! * x = a (mod 1,000,000,007) 으로 (N-K)!K! 의 inverse 를 구해주기만 하면 끝이다.

 

그런데 modular의 상태를 보아하니 소수이다. (직접 소수인지 확인해봄)

 

소수라는 의미는...? Fermat's Little Theorem 을 이용할 수 있다는 점이다.

 

따라서 (N-K)!K! 의 inverse는 ((N-K)!K!)^(1,000,000,007-2) (mod 1,000,000,007) 를 통해서 구할 수 있다.

 

큰 수에 대한 거듭제곱은 이전에 계속 활용해왔던 분할정복을 통해서 거듭제곱을 해결할 수 있다.

 

따라서 최종적인 결과는 다음과 같은 식이 세팅이 됨을 알 수 있다.

result = dp[N] * f( (dp[N-K]*dp[K]) % 1,000,000,007, 1,000,000,007-2, 1,000,000,007 );

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

ll dp[4000001];

ll f(ll x, ll n, ll m) {
	if(n == 0) return 1;
	if(n == 1) return x;
	if(n % 2 == 0) {
		ll res=f(x, n/2, m) % m;
		return (res*res) % m;
	}
	else {
		ll res=f(x, n/2, m) % m;
		res = (res*res) % m;
		return (x*res) % m;
	}
}

void set_Factorial(ll m) {
	dp[0] = 1;
	for(ll i=1; i<=4000000; i++) {
		dp[i] = (i*dp[i-1]) % m;
	}
}

ll combi(ll n, ll k, ll m) {
	ll result = dp[n];
	ll inverse = f((dp[n-k]*dp[k]) % m, m-2, m);
	result = (result*inverse) % m;
	return result;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	set_Factorial(1000000007);

	int m;
	cin >> m;
	for(int i=0; i<m; i++) {
		ll n, k;
		cin >> n >> k;
		cout << combi(n, k, 1000000007) << endl;
	}
	
	return 0;
}