백준 소스코드 [C++] 11401 이항 계수 3

www.acmicpc.net/problem/11401

11401번: 이항 계수 3

백준 소스코드 [C++] 11401 이항 계수 3

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

    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;
    
    ll A = fac[n];
    ll B =(inverse[n - k]*inverse[k]) % P;
    cout<<A*B%P;
	return 0;
}