백준 11401 이항계수 3

이 문제는 nCk를 구하는 문제이지만 n이 400만으로 굉장히 큽니다. 

 

이항계수는 보통 n이 작을때  nCk = n-1Ck-1 + nCk-1 다음과 같은식으로 동적계획법을 이용해서 구할 수 있지만 이경우 시간복잡도가 O(N^2)이 걸리게 됩니다. 따라서 이문제는 좀더 빠른 방법을 이용하여야 하는데

 

바로 nCk = n!/k!(n-k)! 식을 이용하는 겁니다. 

 

페르마의 소정리에 따라 n^p-1 = 1 (mod p) 임을 알고 있습니다. 

따라서 n^p-2 = n^-1 (mod p) 가되고 결론적으로 우리는 1 / k!(n-k)!  이라는 식을 k!(n-k)!^p-2라는 식으로 치환 할 수 있습니다. 

 

총 정리를 하면 

 

1. 1~n 까지 각 n! % MOD 를 구합니다. ( fac[] 배열)

2. n의 modular inverse를 분할정복을 통해 구합니다. n!^p-2 (inv[] 배열) (O(log p))

3. 이후 n 보다 작은 수들은  inv[a] = (inv[a+1]*(a+1))%mod 를 통해 구할 수 있습니다.

  -> inv[a+1] 이 (a+1)^-1 의 modular inverse 이므로 a+1을 곱해서 a!^-1 의 modular inverse를 구할 수 있습니다.

따라서 이러한 전처리 이후 O(1) 만에 nCk 를 구한는 것이 가능하고 위의 전처리 과정은 O(N)이 소요됨을 알 수 있습니다.

 

다음은 코드입니다.

 

#include <iostream>

using namespace std;

#define MOD 1000000007LL

long long fac[4000010];
long long inv[4000010];

/*
    페르마 소정리를 이용한 nCr 빠르게 구하기
    팩토리얼 % MOD 값을 먼저 전처리 한후
    각 팩토리얼의 modular inverse를 구함

    nCr = n!/k!(n-k)! 이므로 우리는 1 / k!(n-k)!을

    페르마 소정리에 따라 k!(n-k)!^MOD-2 으로 치환이 가능함.

*/

long long solve(long long x, long long y) {
    long long ret = 1;
    while(y > 0) {
        if(y%2) {
            ret *= x;
            ret %= MOD;
        }
        x *= x;
        x %= MOD;
        y /=2;
    }
    return ret;
}

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n,m; cin >> m >> n;

    fac[1] = 1;
    for(int i = 2; i <= m; i++) {
        fac[i] = (fac[i-1]*i)%MOD;
    }

    inv[m] = solve(fac[m], MOD-2); //각 팩토리얼의 modular inverse를 구함

    for(int i = m-1; i >= 1; i--)
        inv[i] = (inv[i+1]*(i+1))%MOD; // inv[i+1] -> (i+1)!^-1 이므로 i+1을 곱하면 (i)!^-1 가 됨.

    long long first = fac[m]*inv[m-n]%MOD;

    if(m == n || n == 0) cout<<1;
    else cout<< first*inv[n]%MOD;
    return 0;
}