https://www.acmicpc.net/problem/11402
오늘 풀어볼 문제는 이항 계수 관련 문제이다.
이항 계수란 쉽게 말해 조합인데, 조합의 경우는 두 수 x,y에서 x < y, y < 0 인 경우를 제외한 일반항을 뜻한다.
즉 이 문제에서 구해야 할 것은 이항 계수의 일반항을 m이라는 수로 나눈 나머지이다.
우선 조건으로 주어진 수의 범위가 10^18 이기 때문에 일반적인 방법으로는 풀기 어렵다.
따라서 조합을 구할 때 DP를 이용하여 값을 기억하는 방법으로 조합을 구하려고 시도해 보았다.
하지만 역시나 너무 큰 수이기 때문에 이마저도 해결할 수 없었다.
DP를 사용하긴 하되, 다른 무언가가 더 필요했다.
이 문제를 풀기 위해서는 알아야 할 것이 두 가지가 있다.
물론 DP를 이용하여 프로그래밍하는 방법도 알아야 하겠지만 수학적인 개념이 필요했다.
첫 번째는 바로 뤼카의 정리이다.
뤼카의 정리를 증명하거나 자세히 설명하기에는 너무 어렵기도 해서 간단히 설명해 보자면
nCk를 m으로 나눈 나머지를 구하기 위해서 해야 할 일은 다음과 같다.
이 문제에서 주어진 수 N과 K에 대하여 나머지를 구할 수 m에 대한 m진 전개를 한다.
이후 m진 전개한 N과 K의 각 자릿수의 조합끼리 곱한 후 m으로 나눈 나머지를 구한다.
그러면 해당 나머지가 nCk를 m으로 나눈 나머지가 된다.
두 번째는 페르마의 소정리이다.
페르마의 소정리에 따르면
(n-1)^p = n^p -1 (mod p) 가 항상 성립한다.
따라서 이를 이용해 조합을 큰 수의 계산 없이도 구할 수 있다.
이제 위의 수학적 개념들을 이용해 코드를 작성해보자.
#include <iostream>
#include <vector>
using namespace std;
int combination(int N, int K, int M){
// 페르마의 소정리 이용
int A = 1, B = 1;
for (int i = N; i > N-K; i--)
A = A*i %M;
for (int i = K; i >= 2; i--)
B = B*i %M;
N = 1, K = M-2;
while (K){
if (K & 1) N = N*B %M;
K >>= 1;
B = B*B %M;
}
return A*N %M;
}
int main(){
long long N, K;
int M;
scanf("%lld %lld %d", &N, &K, &M);
int result = 1;
// 뤼카의 정리
while (N || K){
result = result*combination(N%M, K%M, M) %M;
N /= M, K /= M;
}
printf("%d", result);
}
처음엔 단순히 조합을 계산하여 나머지를 구하는 문제인 줄 알고 가볍게 생각한 문제였다.
하지만 조건의 범위가 너무 커 DP를 활용해도 일반적인 방법으로는 도저히 풀 수 없었다.
나머지를 이용해 계산 수를 줄이는 방법을 알고리즘 시간에 배웠었지만 이해도 잘 안된 상태로 문제에 적용하기에 너무 어려웠다.
이번에 소개한 뤼카의 정리와 페르마의 소정리도 이 문제를 풀면서 알게 되었다.
위에는 간단하게 설명했지만, 사실 증명까지 들어가면 굉장히 어려운 부분인 듯 하다. 아마 이 문제의 m의 조건이 소수인 것도 이를 활용하기 위해서인 것 같다.
이번 문제는 내가 생각해서 풀었기 보다 어떤 방식으로 해결해야 하는지를 많이 찾아보며 공부했다.
DP를 공부하기 위한 문제였지만 DP 자체보다는 다른 곳에 초점이 실린 듯 해서 아쉽기도 하지만
다양한 조건의 경우 어떻게 알고리즘을 구성해야 하는지 한 가지 더 배운 것 같다.
