[BaekJoon] 11402번 - 이항 계수 4 [Java]

문제 링크

---

문제 풀이

자연수 $N$ 과 정수 $K$ 에 대한 이항 계수를 $M$ 으로 나눈 나머지를 구해야 하는데, $N$ 이 최대 $10^{18}$ 이며 $K$ 는 최대 $N$ 인 음이 아닌 정수, $M$ 은 $2,000$ 이하의 소수이다. 매우 큰 수로 이루어진 이항 계수를 계산하는 것은 단순한 다이나믹 프로그래밍이나 페르마의 소정리로는 불가능한데 $M$ 이 작은 소수이며 $M$ 으로 나눈 나머지를 구해야 한다는 점에서 뤼카의 정리를 활용하면 해결할 수 있다.

뤼카의 정리를 통해 보다 작은 이항 계수의 곱을 모듈러 연산한 결과를 구하는 것으로 치환할 수 있는데, $M$ 이 최대 $2,000$ 이니 2차원 dp 테이블에 모든 이항 계수를 전처리로 계산해 놓으면 각 항을 $O(1)$ 로 찾을 수 있다.

---

코드

1. 풀이 [Java]

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

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

        long N = Long.parseLong(st.nextToken());
        long K = Long.parseLong(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] dp = new int[1 + M][1 + M];
        for (int i = 0; i <= M; i++) {
            dp[i][0] = 1;

            for (int j = 1; j <= i; j++) {
                dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % M;
            }
        }

        long ans = 1;

        // 뤼카의 정리
        while (N > 0) {
            // N, K를 M진법으로 변환시 자릿수
            int ni = (int) (N % M);
            int ki = (int) (K % M);

            if (ni < ki) {
                ans = 0;
                break;
            }

            ans = ans * dp[ni][ki] % M;

            // 다음 자릿수로 이동하는 효과
            N = N / M;
            K = K / M;
        }

        System.out.println(ans);
    }
}

2. 풀이 [C++]

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

int dp[1 + 2000][1 + 2000];

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

    long long n, k;
    int m;
    cin >> n >> k >> m;

    for (int i = 0; i <= m; i++) {
        dp[i][0] = 1;

        for (int j = 1; j <= i; j++) {
            dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % m;
        }
    }

    long long ans = 1;

    // 뤼카의 정리
    while (n > 0) {
        // N, K를 M진법으로 변환시 자릿수
        int ni = (int)(n % m);
        int ki = (int)(k % m);

        if (ni < ki) {
            ans = 0;
            break;
        }

        ans = ans * dp[ni][ki] % m;

        // 다음 자릿수로 이동하는 효과
        n = n / m;
        k = k / m;
    }

    cout << ans;
}

---