2018년 4월 6일 금요일

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 == 0return 1;
    if (p == 1return a;
    if (p & 1return 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

댓글 없음:

댓글 쓰기