백준 13977 - 이항 계수와 쿼리

www.acmicpc.net/problem/13977

 

최대 10만 개의 쿼리에 대해 $\binom{n}{r} \ mod \ 10^9 + 7$ 을 구해야 하는 문제이다.

 

N과 K는 400만 이하이기 때문에 이항 계수 DP나 일반적인 반복문 연산으로는 제한 메모리/시간 내로 10만개의 쿼리를 처리할 수 없다.

알아야 할 것

이 문제를 해결하기 위해선 페르마의 소정리를 이용해야 한다.

 

페르마의 소정리 : 소수 p가 있고 정수 a가 p의 배수가 아닐 때 다음이 성립한다.

 

$a^{p} \equiv a \ (mod \ p)$

 

페르마의 소정리를 통해 문제에서 요구하는 것을 빠르게 계산할 수 있다.

방법

일단 이항계수를 제곱식으로 바꾸면 다음과 같이 된다.

 

$\binom{n}{r} = \frac{n!}{(n - r)!r!} = n! \times ((n - r)!r!)^{-1}$

 

이 때 페르마의 소정리 식의 양변에  $a^2$ 만큼 나눠 $a^{p - 2} \equiv a^{-1} (mod \ p)$ 을 유도할 수 있고 이 합동식을 응용하면

 

$((n - r)!r!)^{10^9 - 2} \mod p$

 

다음과 같이 분모의 모듈러를 구할 수 있게 된다.

 

여기에 $O(logn)$ 지수 제곱법을 이용하면 각 쿼리에 대해 빠른 계산이 가능해진다.

 

이제 빠르게 이항계수의 합동을 구하는 방법을 알았으니 남은 일은 DP를 통해 팩토리얼의 모듈러를 미리 계산해 놓고 들어오는 쿼리마다 결과를 출력하도록 하면 된다.

 

전체 코드

#include <iostream>
 
using namespace std;
using ll = long long;
 
ll mod = 1e9 + 7;
ll fact[4000001];
 
ll pomod(ll a, ll b)
{
    if (b == 1)
        return a % mod;
    
    if (b & 1)
        return pomod(a, b - 1) * a % mod;
    
    return pomod(a * a % mod, b / 2);
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    fact[0] = fact[1] = 1;
    
    for (int i = 2; i <= 4000000; ++i)
        fact[i] = fact[i - 1] * i % mod;
        
    int t; cin >> t;
    while (t--)
    {
        int a, b; cin >> a >> b;
        cout << fact[a] * pomod(fact[a - b] * fact[b] % mod, mod - 2) % mod << '\n';
    }
}