11402 이항 계수 4

11402 이항 계수 4 https://www.acmicpc.net/problem/11402
SW Expert Academy 3238 이항계수 구하기


먼저 위의 문제들을 풀기위해서는 Lucas' Theorem을 알아야 한다.

[출처 : wiki] 

임의의 음이 아닌 정수 m과 n, 소수 p에 대하여 다음과 같이 합동식으로 표현할 수 있다.

• ${\displaystyle {\binom {m}{n}}\equiv \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}},}$

여기서 첨자가 붙은 수들은 m과 n을 소수 p에 대해 다음과 같이 p진 전개했을 때 얻어지는 것이다. 덧붙여, 한쪽의 전개가 k에서 끝나지 않더라도 더 이상 전개하지 않고 정리를 적용시키는 것이 가능하다.

1. ${\displaystyle m=m_{k}p^{k}+m_{k-1}p^{k-1}+\cdots +m_{1}p+m_{0},}$
2. ${\displaystyle n=n_{k}p^{k}+n_{k-1}p^{k-1}+\cdots +n_{1}p+n_{0}}$

즉, $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)$

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; } Colored by Color Scripter

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; } Colored by Color Scripter

cs

13997 이항 계수와 쿼리

13997 이항 계수와 쿼리 https://www.acmicpc.net/problem/13977

$M$개의 자연수 $N$과 정수 $K$가 주어질 때 $_{n}C_{r}$을 구하는 문제이다.

$O(N + log(p) + M)$에 해결할 수 있다.
$_{n}C_{r}$ = $n!/(r!*(n-r)!$ = $n!*(r!*(n-r)!)^{-1}$ = $n!*(r!)^{-1}*(n-r)!^{-1}$

$a^{p}$ $\equiv$ $a$ $(mod$ $p)$ ($a$는 자연수, $p$는 소수)
$a^{p - 1}$ $\equiv$ $1$ $(mod$ $p)$
$a^{p - 2}*a$ $\equiv$ $1$ $(mod$ $p)$ 즉, $a$의 역원은 $a^{p-2}$이다.
$a^{p-2}$는 분할정복으로 $log(p)$만에 구할 수 있고 역원들 또한 전처리해주어 $O(n)$에 해결할 수 있다.

#include <bits/stdc++.h> using namespace std; typedef long long ll; #define mod (ll)(1e9 + 7) const int MAXN = 4e6 + 6; int n, r; ll fact[MAXN]; ll inverse[MAXN]; ll mpow(ll a, ll p) {     if (p == 0) return 1;     if (p == 1) return a;     if (p & 1) return mpow(a, p - 1)*a % mod;     ll tmp = mpow(a, p / 2);     return tmp * tmp % mod; } void init() {     fact[0] = fact[1] = 1;     for (int i = 2; i < MAXN; i++) fact[i] = fact[i - 1] * i % mod;     inverse[MAXN - 1] = mpow(fact[MAXN - 1], mod - 2);     for (int i = MAXN - 2; i >= 1; i--) inverse[i] = inverse[i + 1] * (i + 1) % mod;     inverse[0] = inverse[1] = 1; } ll nCr(ll n, ll r) {     return ((fact[n] * inverse[r] % mod) * inverse[n - r]) % mod; } int main(){     init();     int t;     scanf("%d", &t);     while (t--) {         scanf("%d%d", &n, &r);         printf("%lld\n", nCr(n, r));     }     return 0; } Colored by Color Scripter

cs