문제
자연수 N과 정수 K가 주어졌을 때, C(N, K)를 1,000,000,007로 나눈 나머지를 구하는 문제이다. N이 최대 4,000,000으로 매우 크기 때문에 파스칼의 삼각형이나 단순 팩토리얼 계산으로는 풀 수 없다.
입력
- 첫째 줄: N, K (1 이상 4,000,000 이하, 0 이상 N 이하)
출력
- C(N, K)를 1,000,000,007로 나눈 나머지
예제
| 입력 | 출력 |
|---|---|
5 2 | 10 |
풀이
페르마의 소정리를 이용한 모듈러 역원으로 C(N,K) mod p를 구한다. C(N,K) = N! / (K! × (N-K)!)이고, 나누기를 모듈러 역원으로 변환한다.
- C(N,K) = N! × (K! × (N-K)!)^(-1) mod p로 변환한다.
- p가 소수이므로 페르마의 소정리에 의해 a^(-1) mod p = a^(p-2) mod p가 성립한다.
fac(N)함수로 N!을 계산하되, 매 단계마다 MOD로 나머지를 취한다.pow(base, expo)함수로 분할 정복을 이용한 빠른 거듭제곱을 구현한다.- 최종 답:
fac(N) * pow(fac(K) * fac(N-K) % MOD, MOD-2) % MOD
핵심 아이디어: 모듈러 나눗셈은 직접 나눌 수 없다. 페르마의 소정리(a^(p-1) ≡ 1 mod p)를 적용하면 a의 역원은 a^(p-2) mod p이다. 이를 분할 정복 거듭제곱으로 O(log p) 시간에 계산한다.
코드
package com.ssafy.an.day149;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Day102BOJ11401이항계수구현 { // 11401 이항계수
static final long MOD = 1_000_000_007;
static int N, K; // nCk
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] tmp = br.readLine().split(" ");
N = Integer.parseInt(tmp[0]);
K = Integer.parseInt(tmp[1]);
System.out.println(fac(N) * pow(fac(K) * fac(N - K) % MOD, MOD - 2) % MOD);
br.close();
}
public static long fac(long n) { // 팩토리얼
long res = 1L;
while (n > 1)
res = res * n-- % MOD;
return res;
}
public static long pow(long base, long expo) {
if (expo == 1)
return base % MOD;
long temp = pow(base, expo / 2);
if (expo % 2 == 1)
return (temp * temp % MOD) * base % MOD;
return temp * temp % MOD;
}
}복잡도
- 시간: O(N + log p) — 팩토리얼 계산 O(N) + 거듭제곱 O(log p)
- 공간: O(log p) — 재귀 스택 깊이