백준 소스코드 [C++] 13977 이항 계수와 쿼리

www.acmicpc.net/problem/13977

13977번: 이항 계수와 쿼리

백준 소스코드 [C++] 13977 이항 계수와 쿼리

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
typedef long long ll;
using namespace std;
#define P 1000000007LL
ll fac[4000001],inverse[4000001];

ll power(ll x, ll y) {
    if (y == 0) return 1;
    if (y % 2 ==1) return (power(x, y- 1) * x) % P;
    ll half = power(x, y / 2) % P;
    return half*half % P;
}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int n, k, t;

    fac[0] = 1;
    for (int i = 1; i <= 4000000; i++)
        fac[i] = fac[i - 1] * i % P; 

    inverse[4000000] = power(fac[4000000], P - 2); 
    for (int i = 4000000 - 1; 0<=i; i--)
        inverse[i] = inverse[i + 1] * (i + 1LL) % P;
    
    cin >> t;
    while (t--) {
        cin >> n >> k;
        ll A = fac[n];
        ll B = (inverse[n - k] * inverse[k]) % P;
        cout << A * B % P<<'\n';
    }
	return 0;
}