[백준/BOJ] 13977번 : 이항 계수와 쿼리 (페르마의 소정리)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 13977번 : '이항 계수와 쿼리' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Gold I 티어에 해당하며, 문제를 풀이하기 위해 페르마의 소정리와 분할 정복을 이용한 거듭 제곱에 대한 이해가 필요합니다.

 

 

13977번 : 이항 계수와 쿼리

 

조합 연산을 수행하기만 하면 되는 간단한 문제이지만, N과 K의 범위가 아주 크며 모듈로 연산을 수시로 해주어야 하는 문제입니다.

시간 초과가 발생하지 않기 위해서는 페르마의 소정리를 활용하여 문제를 풀어야 합니다.

 

 

페르마의 소정리란, mod m에서 어떤 수를 a로 나누는 것은 a의 역원을 곱하는 것과 같으므로 이를 활용하는 것입니다.

m이 소수일 때 a^(m-1) ≡ 1 (mod m)이고 a^(m-1) = a × a^(m-2) 이므로 결국 a의 곱셈에 대한 역원이 a^(m-2)임을 알 수 있습니다. (이 조건은 m이 소수인 경우에만 해당됩니다.)

 

 

 

따라서 위와 같이 N C K를 연산한다고 할 때, 분모에 있는 수를 나누지 말고 단순히 m-2 제곱한 것을 곱해주기만 하면 모듈로 연산을 했을 때 결과적으로 같은 값이 나옴을 알 수 있습니다.

이 때 m-2 제곱을 하는 과정에서 빠른 거듭제곱을 수행하기 위해 분할 정복을 이용한 거듭제곱 알고리즘을 사용해주면 됩니다.

 

이제 풀이를 코드로 옮겨서 작성해보도록 하겠습니다.

 

#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;

long long factorial[4000001] = {1};

long long fastPow(long long ret, int exp) {
    if(exp == 0) return 1;
    else if(exp == 1) return ret;

    if(exp % 2 == 0) {
        long long temp = fastPow(ret, exp/2);
        return (temp * temp) % MOD;
    }
    else {
        long long temp = fastPow(ret, exp - 1);
        return (temp * ret) % MOD;
    }
}

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

    for(int i=1; i<=4000000; i++)
        factorial[i] = (factorial[i-1] * i) % MOD;

    int T; cin >> T;
    while(T--) {
        int N, K; cin >> N >> K;
        cout << factorial[N] * fastPow((factorial[K] * factorial[N-K]) % MOD, MOD - 2) % MOD << "\n";
    }
}

 

페르마의 소정리를 사용하여 조합 계산에서 분모로 나누는 것이 아닌, 분모에 대한 역원을 곱하여 같은 값이 나오도록 계산해줍니다.

fastPow 함수는 말 그대로 빠른 거듭제곱 함수로, 지수가 짝수인 경우에는 a^2n = (a^n)^2와 같은 방식으로 쪼개어 O(log n) 시간에 거듭제곱을 할 수 있도록 구현해주었습니다.

 

 

 

제출해보면 위와 같이 정답 처리를 받을 수 있습니다.