백준 11402, Lucas’s Theorem
Lucas’s Theorem 을 그대로 구현하는 문제.
$n$ 과 $k$ 가 주어질때, $n$과 $k$를 소수 $p$ 진법으로 분해하여 $ {n \choose k}\, \bmod\, p $ 를 고속으로 계산하는 방법이다.
이걸 응용하는 문제는 얼마나 어려울지 감이 오지 않는다.
Source Code
//BOJ11402
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define Msize 2020
ll binomial[Msize][Msize];
ll N, K, M;
void binomialCount() {
memset(binomial, 0, sizeof(binomial));
binomial[0][0] = 1;
binomial[1][0] = 1;
binomial[1][1] = 1;
for (int i = 2; i <= 2000; ++i) {
binomial[i][0] = 1;
binomial[i][i] = 1;
for (int j = 1; j < i; ++j) {
binomial[i][j] = (binomial[i - 1][j] + binomial[i - 1][j - 1]) % M;
}
}
return;
}
int main() {
cin >> N >> K >> M;
binomialCount();
ll ans = 1;
while (N > 0) {
ll nmod, kmod;
nmod = N % M;
kmod = K % M;
ans *= binomial[nmod][kmod];
ans %= M;
N -= nmod;
K -= kmod;
N /= M;
K /= M;
}
printf("%lld\n", ans);
return 0;
}