백준 11401: 이항 계수 3

Gold I 난이도의 이항 계수 3 문제를 C++로 풀이한 내용입니다. 주어진 두 수 n, k에 대해 nCk를 소수 p로 나눈 나머지를 구하는 문제입니다.

문제 소개

• 문제 번호: 11401
• 문제명: 이항 계수 3
• 난이도 (티어): Gold I
• 사용 언어: C++
• 실행 시간: 36 ms
• 메모리: 32972 KB
• 문제 요약:
  nCk (n choose k) 값을 $10^9+7$ (소수 p)로 나눈 나머지를 계산하는 문제입니다.

접근 방법

이 문제는 이항 계수 $nCk$의 정의와 모듈러 연산, 그리고 페르마 소정리를 이용해야 풀 수 있습니다.

$nCk=\frac{n!}{k!(n-k)!}$

모듈러 연산에서 나눗셈은 역원을 곱하는 것으로 대체됩니다. 즉, $a÷b(\mathrm{mod}p)$는 $a\times b^{-1}(\mathrm{mod}p)$와 같습니다. 여기서 $b^{-1}$는 $b$의 모듈러 곱셈 역원입니다.

p가 소수일 때, 페르마 소정리에 의해 $a^{p-1}\equiv 1(\mathrm{mod}p)$ (단, $a$는 $p$의 배수가 아닐 때)입니다. 이 식을 변형하면 $a\times a^{p-2}\equiv 1(\mathrm{mod}p)$가 되므로, $a$의 모듈러 곱셈 역원은 $a^{p-2}(\mathrm{mod}p)$가 됩니다.

따라서, $nCk(\mathrm{mod}p)$는 다음과 같이 계산할 수 있습니다.
$nCk(\mathrm{mod}p)=n!\times (k!\times (n-k)!{)}^{p-2}(\mathrm{mod}p)$

이 문제를 풀기 위해 필요한 주요 알고리즘/자료구조는 다음과 같습니다.

1. 팩토리얼 계산: $n!$, $k!$, $(n-k)!$을 미리 계산하거나 동적으로 계산해야 합니다. 모듈러 연산을 적용하기 위해 각 단계마다 나머지를 취합니다.
2. 모듈러 거듭제곱 (Modular Exponentiation): 페르마 소정리를 이용하여 역원을 계산하기 위해 $a^{p-2}(\mathrm{mod}p)$를 효율적으로 계산해야 합니다. 이는 분할 정복 기법을 이용한 modpow 함수로 구현할 수 있습니다.

이 방법을 선택한 이유는 다음과 같습니다.

• $n$과 $k$의 값이 커질 수 있으므로, 직접 $nCk$를 계산한 후 나머지를 구하는 것은 오버플로우가 발생합니다.
• p가 소수라는 조건 덕분에 페르마 소정리를 사용하여 모듈러 역원을 효율적으로 계산할 수 있습니다.
• 팩토리얼 값을 미리 계산해두거나 (DP), 필요할 때마다 계산하고 모듈러 연산을 적용하면 시간 복잡도를 줄일 수 있습니다.

풀이 과정

1. 입력: 정수 n과 k를 입력받습니다.
2. 모듈러 상수: $MOD=1000000007$ (p)를 정의합니다.
3. 팩토리얼 배열 준비: $0!$부터 $n!$까지의 값을 계산하여 fact 배열에 저장합니다. 각 단계마다 $(fact[i-1]\ast i)(\mathrm{mod}MOD)$로 계산하여 오버플로우를 방지합니다.
   • fact[0] = 1
   • fact[i] = (fact[i-1] * i) % MOD for $i=1$ to $n$
4. 분모 계산: $k!(\mathrm{mod}MOD)$와 $(n-k)!(\mathrm{mod}MOD)$를 fact 배열에서 가져옵니다. 이 두 값을 곱한 결과가 분모 $D=k!\times (n-k)!(\mathrm{mod}MOD)$가 됩니다.
5. 모듈러 역원 계산: 페르마 소정리를 이용하여 분모 $D$의 모듈러 역원 $D^{-1}$를 계산합니다. 이는 modpow(D, MOD - 2) 함수를 호출하여 얻을 수 있습니다.
   • modpow(a, b) 함수는 $a^b(\mathrm{mod}MOD)$를 계산하는 재귀적 또는 반복적 알고리즘입니다. 이 문제에서는 $b=MOD-2$가 됩니다.
6. 최종 결과 계산: $n!(\mathrm{mod}MOD)$ (분자 $N$)와 계산된 역원 $D^{-1}$을 곱하여 최종 결과를 얻습니다.
   • $Ans=(N\times D^{-1})(\mathrm{mod}MOD)$

핵심 아이디어

• 모듈러 연산에서 나눗셈은 역원 곱셈으로 대체된다.
• p가 소수일 때, 페르마 소정리를 이용하면 $a^{-1}\equiv a^{p-2}(\mathrm{mod}p)$이다.
• modpow 함수를 이용하여 $a^{p-2}(\mathrm{mod}p)$를 효율적으로 계산한다.
• 팩토리얼 값을 미리 계산하여 $O(N)$ 시간에 $nCk$의 구성 요소를 얻는다.

주의할 점

• $n$과 $k$의 값은 최대 $10^6$까지 될 수 있으므로, 팩토리얼 계산 시 반드시 모듈러 연산을 적용해야 합니다.
• modpow 함수는 지수 $b$가 큰 경우에도 빠르게 계산할 수 있어야 합니다. (분할 정복 이용)
• 문제 조건에서 $n<p$라는 보장이 있으므로 $n!$, $k!$, $(n-k)!$은 p의 배수가 아니며, 따라서 역원이 항상 존재합니다.

코드 설명

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

using ll = long long;
const ll MOD = 1000000007; // p = 소수

/*
    문제: nCk mod p, 단 p는 소수 (11401)

    핵심 아이디어:

    nCk = n! / (k! (n-k)!)
         = n! * (k!(n-k)!)^{-1}   (mod p)

    여기서 나눗셈은 mod 세계에서는 "역원"으로 바뀜.
*/

/*
    수학적 배경 요약:

    mod p 세계에서
        Z_p = {0,1,2,...,p-1}

    그 중 역원이 존재하는 집합:
        Z_p^* = {1,2,...,p-1}

    (p가 소수이므로 0만 빼고 전부 p와 서로소)

    따라서:
        a ∈ Z_p^*  <=>  gcd(a,p)=1  <=>  a ≠ 0 (mod p)

    이 집합은 곱셈에 대해 군(group).
*/

/*
    페르마 소정리:

        a ∈ Z_p^* 이면
        a^(p-1) ≡ 1 (mod p)

    양변에 a^{-1} 곱하면:

        a^(p-2) ≡ a^{-1} (mod p)

    즉:
        역원 = a^(p-2)
*/

ll modpow(ll a, ll b) {
    /*
        이 함수는 a^b mod p 를 계산.

        여기서:
            a ∈ Z_p^* (역원이 존재하는 원소)
            b는 지수 (여기서는 보통 p-2)

        수학적으로 우리가 계산하는 건:
            a^b = a^(b_0*2^0 + b_1*2^1 + ...)

        즉 b를 이진수로 분해해서:
            필요한 제곱들만 곱하는 것.
    */

    ll res = 1;

    while (b > 0) {

        /*
            b & 1 :

            b를 이진수로 봤을 때
            최하위 비트가 1인지 검사.

            예:
                b = 13 = 1101₂
                -> 1,0,1,1 순서로 처리됨

            의미:
                지금 보고 있는 2^i 항이
                실제로 지수에 포함되면 곱함.
        */
        if (b & 1) {
            res = res * a % MOD;
            /*
                res는 지금까지 선택된 항들의 곱.
                수학적으로:
                    res = Π a^{2^i}
            */
        }

        /*
            a = a * a :

            a를 제곱하는 이유:

                처음엔 a = a^(1)
                다음엔 a = a^(2)
                다음엔 a = a^(4)
                다음엔 a = a^(8)
                ...

            즉:
                a는 "밑"이 아니라
                현재 2^i에 해당하는 거듭제곱 값.
        */
        a = a * a % MOD;

        /*
            b >>= 1 :

            b를 오른쪽으로 1비트 shift.
            즉:
                b = floor(b / 2)

            다음 비트(2^(i+1))로 이동.
        */
        b >>= 1;
    }

    return res;
}

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

    ll n, k;
    cin >> n >> k;

    /*
        문제 조건:
            n < p

        그래서 n! 안에는 p가 안 들어감.
        따라서:

            n! mod p ≠ 0
            k! mod p ≠ 0
            (n-k)! mod p ≠ 0

        즉:
            분모 a = k!(n-k)! ∈ Z_p^*
            → 역원 존재.
    */

    vector<ll> fact(n+1);
    fact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = fact[i-1] * i % MOD;
        /*
            여기서 i는 그냥 1,2,3,...,n
            mod p의 환사상에 의해:
                (x*y) mod p = (x mod p)*(y mod p)
            이므로
                매 단계마다 mod p 붙여도 구조 보존.
        */
    }

    ll numerator = fact[n];
    ll denominator = fact[k] * fact[n-k] % MOD;

    /*
        denominator = a 라고 하면:

            a ∈ Z_p^*

        그래서:
            a^(p-1) ≡ 1
            a^(p-2) ≡ a^{-1}
    */

    ll inv = modpow(denominator, MOD-2);

    ll ans = numerator * inv % MOD;
    cout << ans << "\n";
}

주요 부분 설명

• const ll MOD = 1000000007;: 모듈러 연산을 위한 상수로, 소수 p 값을 저장합니다.
• ll modpow(ll a, ll b): 이 함수는 분할 정복을 이용하여 $a^b(\mathrm{mod}MOD)$를 $O(\log b)$ 시간 복잡도로 계산합니다. 지수 $b$가 $MOD-2$인 경우, 즉 모듈러 역원을 구할 때 사용됩니다.
• vector<ll> fact(n+1);: 0!부터 n!까지의 팩토리얼 값을 저장할 벡터입니다. 각 값은 MOD 연산을 거쳐 저장됩니다.
• fact[i] = fact[i-1] * i % MOD;: 팩토리얼 값을 동적으로 계산하며, 각 단계마다 MOD 연산을 적용합니다.
• ll numerator = fact[n];: n! 값을 가져옵니다.
• ll denominator = fact[k] * fact[n-k] % MOD;: k!와 (n-k)! 값을 곱하고 MOD 연산을 적용하여 분모를 계산합니다.
• ll inv = modpow(denominator, MOD-2);: 계산된 분모의 모듈러 역원을 modpow 함수를 이용해 구합니다.
• ll ans = numerator * inv % MOD;: 분자와 분모의 역원을 곱하여 최종 결과를 얻고 MOD 연산을 적용합니다.

복잡도 분석

• 시간 복잡도:
  • 팩토리얼 계산: O(N) (N은 입력 n의 최댓값)
  • 모듈러 거듭제곱 (modpow): O(log MOD) (MOD는 10^9 + 7)
  • 총 시간 복잡도는 팩토리얼 계산에 의해 O(N) 입니다.
• 공간 복잡도:
  • 팩토리얼 값을 저장하기 위한 fact 배열: O(N)
  • 총 공간 복잡도는 O(N) 입니다.

배운 점

이 문제는 이항 계수를 모듈러 연산 하에서 계산하는 방법을 익힐 수 있는 좋은 문제였습니다. 특히 페르마 소정리를 이용한 모듈러 역원 계산과 분할 정복을 이용한 모듈러 거듭제곱 알고리즘(modpow)의 중요성을 다시 한번 확인할 수 있었습니다.

• 핵심 개념: 모듈러 나눗셈은 역원 곱셈으로 대체된다.
• 페르마 소정리 활용: p가 소수일 때 $a^{p-2}\equiv a^{-1}(\mathrm{mod}p)$ 임을 이해하고 적용하는 능력.
• 효율적인 알고리즘: modpow를 사용하여 지수가 큰 거듭제곱 연산을 빠르게 수행하는 방법.
• DP 활용: 팩토리얼 값을 미리 계산하여 중복 계산을 피하고 시간 복잡도를 최적화하는 방법.

이러한 개념들은 조합론 문제뿐만 아니라 다양한 알고리즘 문제에서 모듈러 연산이 필요할 때 유용하게 적용될 수 있습니다.