SW Expert Academy 3238 이항계수 구하기
먼저 위의 문제들을 풀기위해서는 Lucas' Theorem을 알아야 한다.
[출처 : wiki]
여기서 첨자가 붙은 수들은 m과 n을 소수 p에 대해 다음과 같이 p진 전개했을 때 얻어지는 것이다. 덧붙여, 한쪽의 전개가 k에서 끝나지 않더라도 더 이상 전개하지 않고 정리를 적용시키는 것이 가능하다.
즉, $m,n$을 $p$의 진수로 나타내고 그것의 계수들을 $m_{k}, n_{k}$라 했을 때
$_{m}C_{n} (mod$ $p) =$ $(_{m_{k}}C_{n_{k}})$$(_{m_{k-1}}C_{n_{k-1}})$$\cdots$$(_{m_{0}}C_{n_{0}})$$(mod$ $p)$
$_{m}C_{n} (mod$ $p) =$ $(_{m_{k}}C_{n_{k}})$$(_{m_{k-1}}C_{n_{k-1}})$$\cdots$$(_{m_{0}}C_{n_{0}})$$(mod$ $p)$
1. 11402 이항계수 4
위의 정리를 이용하여 기본적인 2차원 dp를 이용하면 $O(M^2)$에 풀 수 있다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2005;
ll n, r;
int m;
int dp[MAXN][MAXN];
ll nCr(int n, int r) {
if (r == 1) return n;
if (r == 0) return 1;
if (n < r) return 0;
int &ret = dp[n][r];
if (ret != -1) return ret;
ret = 0;
return ret = (nCr(n - 1, r - 1) + nCr(n - 1, r)) % m;
}
int main() {
memset(dp, -1, sizeof dp);
scanf("%lld%lld%d", &n, &r, &m);
ll ret = 1;
while (n || r) {
ret *= nCr(n%m, r%m);
ret %= m;
n /= m, r /= m;
}
printf("%lld", ret);
return 0;
}
| cs |
2. 3238 이항계수 구하기
페르마 소정리와 분할정복 거듭제곱을이용해 $O(log$ $p)$에 구할 수 있다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 5;
ll n, r;
int t, m;
ll f[MAXN];
ll mpow(ll a, ll p) {
ll ret = 1;
while (p) {
if (p & 1) ret *= a, ret %= m;
a *= a;
a %= m;
p /= 2;
}
return ret;
}
int main() {
scanf("%d", &t);
for (int i = 1; i <= t; i++) {
scanf("%lld%lld%d", &n, &r, &m);
f[0] = 1;
for (int i = 1; i < m; i++)f[i] = (f[i - 1] * i) % m;
ll ret = 1;
while (n || r) {
ll a = n % m, b = r % m;
if (a < b) ret = 0;
if (ret == 0) break;
ret *= f[a];
ret %= m;
ret *= mpow((f[b] * f[a - b]) % m, m - 2);
ret %= m;
n /= m, r /= m;
}
printf("#%d %lld\n", i, ret);
}
return 0;
}
| cs |
댓글 없음:
댓글 쓰기