11401번: 이항 계수 3

11401번: 이항 계수 3

사용 언어: C++

문제 요약

자연수 N과 정수 K가 주어질 때, 이항 계수 NCK를 1,000,000,007로 나눈 나머지를 구하는 문제입니다.

• N은 최대 4,000,000까지 주어질 수 있어, 단순 계산으로는 해결이 어렵고
• 1,000,000,007은 소수(prime number)라는 점이 이 문제의 핵심

풀이

일단 모듈려 연산은 나눗셈에 대해 분배법칙이 성립하지 않고, 계산 자체도 N이 400만까지 가서 단순 계산은 불가능.

그래서 해결 방법이 모듈러 곱셈 역원을 쓰는 건데, 이게 어떤 수 B로 나누는 것은, B의 역원(B^-1)을 곱하는 것과 같다는 거고, 이를 이루기 위해 쓰는 것이 페르마의 소정리.

 

페르마의 소정리

페르마의 소정리는, P가 소수이면, a^(P−1) ≡ 1(modP) -> 양변을 a로 나누면 -> a^(−1) ≡ a^(p−2) (modp)

그래서 정리하면 (구하려는 수) ^ (P-2)라는 간단한 식으로 역원을 찾을 수 있음.

 

그리고 페르마의 소정리를 이루기 위해 쓰는 분할 정복을 이용한 거듭제곱이 여기에 들어가는데, base의 exp 제곱을 매우 빠르게 구하기 위해 사용됨.

 

분할 정복을 이용한 거듭제곱 예시: power(3, 13)

만약 3^10을 구해야 한다면, 단순하게 3을 10번 곱할 수 있습니다. 하지만 3^1000이라면 1000번이나 곱해야 해서 매우 비효율적이죠.

분할 정복 거듭제곱은 지수를 절반으로 나눠가며 계산하는 아이디어에 기반합니다.

• 3^10 = (3^5)^2
• 3^5 = 3 * 3^4
• 3^4 = (3^2)^2
• 3^2 = 3 * 3

이렇게 계산 과정을 연쇄적으로 줄여나가면 곱셈 횟수를 획기적으로 줄일 수 있습니다. 이 알고리즘은 지수의 이진수 표현과 깊은 관련이 있습니다.

예를 들어 13은 이진수로 1101이고, 이는 8 + 4 + 1을 의미합니다. 따라서 3^13은 3^(8+4+1) = 3^8 * 3^4 * 3^1 과 같습니다. 이 알고리즘은 바로 이 원리를 이용해 3^1, 3^2, 3^4, 3^8... 등을 차례로 만들어 필요한 것들만 res에 곱해주는 방식으로 동작합니다.

이제 코드의 각 줄이 어떻게 이 아이디어를 구현하는지 power(3, 13)을 예시로 따라가 보겠습니다.

• 초기 상태: res = 1, base = 3, exp = 13

1. 첫 번째 반복 (exp = 13)

• exp % 2 == 1 (13은 홀수) → 참
• res = res * base → res는 1 * 3 = 3이 됩니다. (결과에 3^1을 곱함)
• base = base * base → base는 3 * 3 = 9가 됩니다. (다음 계산을 위해 3^2을 준비)
• exp = exp / 2 → exp는 13 / 2 = 6이 됩니다.

2. 두 번째 반복 (exp = 6)

• exp % 2 == 1 (6은 짝수) → 거짓
• base = base * base → base는 9 * 9 = 81이 됩니다. (다음 계산을 위해 3^4을 준비)
• exp = exp / 2 → exp는 6 / 2 = 3이 됩니다.

3. 세 번째 반복 (exp = 3)

• exp % 2 == 1 (3은 홀수) → 참
• res = res * base → res는 3 * 81 = 243이 됩니다. (결과에 3^4을 곱함)
• base = base * base → base는 81 * 81 = 6561이 됩니다. (다음 계산을 위해 3^8을 준비)
• exp = exp / 2 → exp는 3 / 2 = 1이 됩니다.

4. 네 번째 반복 (exp = 1)

• exp % 2 == 1 (1은 홀수) → 참
• res = res * base → res는 243 * 6561이 됩니다. (결과에 3^8을 곱함)
• base = base * base → base는 6561 * 6561이 됩니다. (다음 계산을 위해 3^16을 준비)
• exp = exp / 2 → exp는 1 / 2 = 0이 됩니다.

5. 반복 종료

• exp가 0이 되었으므로 while문을 탈출합니다.
• 최종 res 값 (즉, 3^1 * 3^4 * 3^8 = 3^13)을 반환합니다.

답

#include <iostream>

using namespace std;

long long P = 1000000007;

// 분할 정복을 이용한 거듭제곱
long long power(long long base, long long exp)
{
    long long res = 1;
    base %= P;
    while (exp > 0)
    {
        if (exp % 2 == 1)
        {
            res = (res * base) % P;
        }
        base = (base * base) % P;
        exp /= 2;
    }
    return res;
}

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

    long long N, K;
    cin >> N >> K;

    // N부터 N-K+1까지 mod 연산
    long long numerator = 1;
    for (int i = 0; i < K; i++)
    {
        numerator = (numerator * (N - i)) % P;
    }

    // K! mod 연산
    long long denominator = 1;
    for (int i = 1; i <= K; i++)
    {
        denominator = (denominator * i) % P;
    }

    // 페르마 소정리
    long long inverse_denominator = power(denominator, P - 2);

    long long result = (numerator * inverse_denominator) % P;

    cout << result << "\n";

    return 0;
}