[백준] 11402번 - 이항 계수 4 [Java]

문제 링크

---

문제 풀이

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

뤼카의 정리를 통해 보다 작은 이항 계수의 곱을 모듈러 연산한 결과를 구하는 것으로 치환할 수 있는데, 각 이항 계수를 빠르게 구하기 위해 팩토리얼과 역팩토리얼 배열을 활용했다. 각 배열들을 한 번만 초기화하면 각 이항 계수를 $O(1)$ 에 계산할 수 있다. 주어진 $N$, $K$ 를 $M$ 진법으로 변환한 각 자릿수도 필요한데 이는 모듈러 연산을 통해 끝자리를 구하고 계산한 후 나눗셈 연산으로 끝자리를 날려서 다음 자리로 이동하는 테크닉을 활용했다.

역팩토리얼의 경우 페르마의 소정리로 초항을 구한 후 모듈러 곱셈 역원을 활용한 점화식으로 구할 수 있는데 이때 분할 정복을 이용한 거듭제곱으로 로그 시간 내에 거듭제곱을 구하는 방식을 활용했다. $M$ 이 크지 않아서 상수 시간으로 구하는 간단한 방법으로도 해결은 가능하다.

---

코드

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[] fact = initFact(M);  // 팩토리얼 배열
        int[] invFact = initInvFact(M, fact[M - 1]);  // 역팩토리얼 배열(모듈러 역원)
        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 * fact[ni] * invFact[ki] * invFact[ni - ki] % M;

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

        System.out.println(ans);
    }

    private static int[] initFact(int M) {
        int[] fact = new int[M];
        fact[0] = 1;

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

        return fact;
    }

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

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

        return invFact;
    }

    // a^b % mod를 구하는 메서드(분할 정복을 이용한 거듭제곱)
    private static int modPow(int a, int b, int mod) {
        if (b == 0) return 1;

        int half = modPow(a, b / 2, mod);
        if (b % 2 == 0) {
            return half * half % mod;
        } else {
            return half * half % mod * a % mod;  // half * half * a가 int형 범위를 넘어갈 수 있어서 미리 mod 수행
        }
    }
}

---

풀이 정보

1. 풀이 [Java]

• 101 min

---