$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;
}
| cs |
