백준 11401 - 이항 계수 3

백준 11401 문제 바로가기

풀이

• N, K 범위에 의해서 일반적인 방법으로는 해결할 수 없다.

• 페르마의 소정리를 활용하여 해결할 수 있다.

소스 코드

#include <cstdio>

typedef long long LL;

const int P = 1000000007;

int N, K;
int fac[4000005];

int mpow(int x, int n) {
    int ret = 1;
    while (n != 0) {
        if (n & 1) {
            ret = (LL)ret * x % P;
        }
        x = (LL)x * x % P;
        n >>= 1;
    }
    return ret;
}

int main() {
    scanf("%d%d", &N, &K);
    fac[0] = 1;
    for (int i = 1; i <= N; ++i) {
        fac[i] = (LL)i * fac[i - 1] % P;
    }
    printf("%d", (LL)fac[N] * mpow((LL)fac[K] * fac[N - K] % P, P - 2) % P);
    return 0;
}