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