[백준] 13977 이항 계수와 쿼리

문제 링크

http://icpc.me/13977

13977번: 이항 계수와 쿼리

풀이

모듈러 역원에 대해 알아야 하는 문제다.

모듈러 역원에 대한 내용은 여기를 참고하자.

n!을 전처리하여 미리 구해두고, 각 쿼리마다 n! * ((n-r)! * r!)^(mod-2)을 구하면 된다.

이때 제곱은 분할정복을 이용하여 계산한다.

코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll mod = 1e9 + 7;
const int N = 4e6 + 6;
ll fac[N];

ll pw(ll a, ll b) {
    ll ret = 1;
    while (b) {
        if (b % 2) ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret % mod;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    fac[0] = fac[1] = 1;
    for (int i = 2; i < N; i++) fac[i] = fac[i - 1] * i % mod;
    int m; cin >> m;
    while (m--) {
        int n, r; cin >> n >> r;
        ll a = fac[n], b = pw(fac[r] * fac[n - r] % mod, mod - 2); 
        cout << a * b % mod<< "\n";
    }
}