[BaekJoon] 11401번 - 이항 계수 3 [Java]

문제 링크

---

문제 풀이

자연수 $N$ 과 정수 $K$ 에 대한 이항 계수를 $1,000,000,007$ 로 나눈 나머지를 구해야 하는 문제다. 단순한 다이나믹 프로그래밍으로는 해결할 수 없는데 페르마의 소정리와 이진 거듭제곱 을 적용하면 해결할 수 있다.

이항 계수의 경우 분모를 모듈러 곱셈 역원으로 바꾸면 아래와 같이 된다.($p = 1,000,000,007$ 이고 $p$ 는 소수이며 $k!$, $(n-k)!$ 과 서로소라 모듈러 곱셈 역원이 존재하는 상황)

\[\binom{n}{k} = \frac{n!}{k!(n-k)!} \equiv n!\,(k!)^{-1}\,((n-k)!)^{-1} \pmod{p}\]

이제 팩토리얼과 역팩토리얼 배열을 만들면 저 식의 값을 계산할 수 있는 데, 팩토리얼 배열의 경우 점화식으로 초기화하되 모듈러를 적용해서 오버플로우를 방지했다. 역팩토리얼 배열의 경우 아래 식으로 계산할 수 있다.

\[(n-1)!^{-1} \equiv n \cdot (n!)^{-1} \pmod{p}\]

초항의 경우 페르마의 소정리를 활용하면 아래와 같이 구할 수 있다.

\[n!^{-1} \equiv (n!)^{p-2} \pmod{p}\]

여기서 $p-2 = 1,000,000,005$ 이므로 해당 거듭제곱 연산을 이진 거듭제곱으로 구하면 된다.

---

코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {

    static final int MOD = 1_000_000_007;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        long[] fact = initFact(N);  // 팩토리얼 배열
        long[] invFact = initInvFact(N, fact[N]);  // 역팩토리얼 배열

        System.out.println(fact[N] * invFact[K] % MOD * invFact[N - K] % MOD);
    }

    static long[] initFact(int N) {
        long[] fact = new long[1 + N];
        fact[0] = 1;

        for (int i = 1; i <= N; i++) {
            fact[i] = fact[i - 1] * i % MOD;
        }

        return fact;
    }

    static long[] initInvFact(int N, long a) {
        long[] invFact = new long[1 + N];
        invFact[N] = modPow(a, MOD - 2);  // 역팩토리얼의 초항(페르마의 소정리 활용)

        for (int i = N - 1; i >= 0; i--) {
            invFact[i] = invFact[i + 1] * (i + 1) % MOD;
        }

        return invFact;
    }

    static long modPow(long a, int b) {
        long res = 1;

        while (b > 0) {
            if ((b & 1) > 0) res = res * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }

        return res;
    }
}

2. 풀이 [C++]

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

constexpr int MOD = 1000000007;

long long modpow(long a, int b) {
    long long res = 1;

    while (b > 0) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }

    return res;
}

vector<long long> initFact(int n) {
    vector<long long> fact(1 + n);
    fact[0] = 1;

    for (int i = 1; i <= n; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }

    return fact;
}

vector<long long> initInvFact(int n, long a) {
    vector<long long> invFact(1 + n);
    invFact[n] = modpow(a, MOD - 2);  // 역팩토리얼의 초항(페르마의 소정리 활용)

    for (int i = n - 1; i >= 0; i--) {
        invFact[i] = invFact[i + 1] * (i + 1) % MOD;
    }

    return invFact;
}

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

    int n, k;
    cin >> n >> k;

    vector<long long> fact = initFact(n);                 // 팩토리얼 배열
    vector<long long> invFact = initInvFact(n, fact[n]);  // 역팩토리얼 배열

    cout << fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
}

---