https://www.acmicpc.net/problem/14517

문제

$M$개의 자연수 $N$과 정수 $K$가 주어졌을 때 이항 계수 $\binom{N}{K}$를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 $M$이 주어진다. (1 ≤ $M$ ≤ 100,000)

둘째 줄부터 $M$개의 줄에 $N$과 $K$가 주어진다. (1 ≤ $N$ ≤ 4,000,000, 0 ≤ $K$ ≤ $N$)

출력

총 $M$개의 줄에 $\binom{N}{K}$를 1,000,000,007로 나눈 나머지를 출력한다.

풀이

1,000,000,007이 소수이므로 모듈러 역원을 쉽게 구할 수 있다.

어떤 수 $a$에 대해 $ax = 1 (\mod{m})$인 수 $x$를 $a$의 모듈러 역원이라 한다. 페르마 소정리에 따르면, 소수 $p$에 대해 $a^{p-1} = 1 (\mod{p})$이다. 따라서, 소수 $p$에 대해 어떤 수 $a$의 모듈러 역원은 $a^{p-2}$로 구할 수 있다.

이항 계수의 정의에 따라 $\binom{N}{K} = \frac{N!}{K! (N-K)!}$이고, 이 값을 소수 1,000,000,007 (:= $p$)로 나눈 나머지는 모듈러 역원을 통해 계산할 수 있다.

테스트 케이스가 여러 개이고, $N \leq 4,000,000$이므로 팩토리얼을 $p$로 나눈 나머지를 미리 계산하였다가 사용하면 시간을 줄일 수 있을 것이며, 어떤 수의 거듭제곱은 분할정복을 이용하면 $O(\log N)$에 구할 수 있으므로 이를 사용하는 것도 도움이 될 것이다.

코드

c++

#include <bits/stdc++.h>
#define ull unsigned long long
#define p 1000000007
using namespace std;
ull f[4000001] = {1,};
ull pow2(ull a){
    ull b = p - 2, result = 1;
    while (b != 0){
        if (b % 2) result = (result * a) % p;
        a = (a * a) % p;
        b /= 2;
    }
    return result;
}
ull ncr(ull n, ull k){ return (((f[n] * pow2(f[k])) % p) * pow2(f[n - k])) % p; }
int main(){
    ios::sync_with_stdio(false); cin.tie(NULL);
    ull m, n, k;
    cin >> m;
    for (ull i = 1; i < 4000001; i++) f[i] = (f[i - 1] * i) % p;
    for (ull i = 0; i < m; i++){
        cin >> n >> k;
        cout << ncr(n, k) << "\n";
    }
}