11401번 - 이항 계수 3

출처: 백준 알고리즘

주소: www.acmicpc.net/problem/11401

11401번 이항계수3

문제요약:

-> 이항계수 (N, K)을 1,000,000,007으로 나눈 나머지에 대해 출력

 

해결방법:

 1) 이항계수 (N, K)을 구해서 1,000,000,007으로 나눈다.

    => 제일 간단한 방법이지만, N값이 크면 이항계수 (N, K)의 값을 저장할 방법이 없다.

 

 2) "페르마의 소정리"을 이용해서 값을 구한다.

    => a^p-1 ≡ 1 (mod p) {단, p: 소수, a: 정수}

 

소스코드:

#include <iostream>
#define P 1000000007LL
#define MAX_SIZE 4000001
typedef long long ll;
 
// inv[x]의 정의는 x의 inverse가 아닌 x!의 inverse
ll fac[MAX_SIZE], n, k, inv[MAX_SIZE];
 
ll power(ll x, ll y) {
    // x^0 인 경우, while로 들어가지 않는다.
    ll ret = 1;
    
    while (y > 0) {
        // y % 2 == 1인 경우,
        // y가 홀수인 경우
        if (y % 2) {
            ret *= x;
            ret %= P;
        }
        // x 제곱
        x *= x;
        x %= P;
        y /= 2;
    }
    return ret;
}
 
 
int main() {
 
    // factorial 전처리
    fac[1] = 1;
    for (int i = 2; i < MAX_SIZE; i++) {
        fac[i] = (fac[i - 1] * i) % P;
    }
 
    // 페르마의 소정리를 이용하여 fac(400만)의 inverse를 구함
    // 이때 분할정복을 이용하여 logP의 시간에 처리
    inv[MAX_SIZE - 1] = power(fac[MAX_SIZE - 1], P - 2);
    for (int i = MAX_SIZE - 2; i >= 0; i--) {
        // inverse(fac(i)) = inverse(fac(i + 1)) * (i + 1)
        // 위의 수식을 이용하여 전처리
        inv[i] = (inv[i + 1] * (i + 1)) % P;
    }
    // 총 O(N + logP)시간에 전처리
    // 이후 어떤 쿼리가 들어와도 상수시간에// 이항 계수를 1,000,000,007으로 나눈 나머지 계산 가능
    std::cin >> n >> k;    // 예외처리
    if (n == k || !k) {
        printf("%d\n", 1);
        return 0;
    }    // 계산
    ll r = (fac[n] * inv[n - k]) % P;
    r = (r * inv[k]) % P;
    printf("%lld\n", r);
    return 0;
 
}