백준 소스코드 [C++] 16134 조합 (Combination)

www.acmicpc.net/problem/16134

16134번: 조합 (Combination)

백준 소스코드 [C++] 16134 조합 (Combination)

#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[1000001], n, k, inverse[1000001];

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);
    cin >> n >> k;

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

    inverse[1000000] = power(fac[1000000], P - 2);
    for (int i = 1000000 - 1; 0 <= i; i--)
        inverse[i] = inverse[i + 1] * (i + 1) % P;

    ll A = fac[n];
    ll B = (inverse[n - k] * inverse[k]) % P;
    cout << A * B % P;
    return 0;
}