[13977] 이항 계수와 쿼리

https://www.acmicpc.net/problem/13977

13977번: 이항 계수와 쿼리

<문제>

"[11401] 이항계수 3"에 팩토리얼값을 메모이제이션하면 된다.

하나의 이항계수를 구하는 문제에는 굳이 메모이제이션 할 필요가 없지만,

쿼리문제에서는 메모이제이션후 쿼리당 O(1)만에 이항계수를 구할 수 있다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;
ll fac[4000001];
ll f(ll a, ll b) {
    ll mid;
    if (b == 0) return 1;
    if (b % 2 == 1) return (f(a, b - 1) * a) % MOD;
    mid = f(a, b / 2) % MOD;
    return (mid * mid) % MOD;
}
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int i;
    fac[0] = 1;
    for (i = 1; i <= 4000000; i++) fac[i] = (fac[i - 1] * i) % MOD;
    int m;
    cin >> m;
    while (m--) {
        int n, k;
        cin >> n >> k;
        ll up = fac[n];
        ll down = (fac[k] * fac[n - k]) % MOD;
        down = f(down, MOD - 2) % MOD;
        cout << (up * down) % MOD << '\n';
    }
    return 0;
}