[백준/C,C++] 11401번: 이항 계수 3

www.acmicpc.net/problem/11401

11401번: 이항 계수 3

www.acmicpc.net/problem/11051

11051번: 이항 계수 2

과 비슷한 문제입니다. 다른 점은 입력 값인데 11051번: 이항 계수 2와 비교하여 훨씬 큽니다.

 

최댓값이 들어올 경우 DP로는 시간 제한에 걸리기 때문에,

분할 정복을 이용하여 풀어야합니다.

 

이항 계수는 $\frac{n!}{k!(n-k)!}$ 공식으로 구할 수 있습니다.

 

예제 입력을 예로 들면$\frac{5\times4\times3\times2\times1}{2\times1\times(3\times2\times1)}$ 과 같은데,

 

$\frac{5\times4}{2\times1}$ 즉 $\frac{n\times n-1\times ... \times n-k}{k!}$ 로도 나타낼 수 있겠네요.

 

 

하지만 위 식은 분수(나누기)의 형태로 모듈러 연산을 사용할 수 없습니다.

 

페르마의 소정리에 따르면 p가 소수이고 A에 p의 배수가 아닐 때, $A^{p-1}\equiv 1\pmod{p}$ 입니다.

 

이 식은 $A\times A^{p-2}\equiv B\pmod{p}$ 식과 동치이므로 바꿔줄 수 있습니다.

 

$\frac{n\times n-1\times ... \times n-k}{k!}$ 해당식에서 k!을 A라고 했을 때, 분자와 분모에 $A^{p-2}$ 를 곱해주면

 

$\frac{n\times n-1\times ... \times n-k\times A^{p-2}}{A^{p-1}}$ 이 되겠죠.

 

 

여기서 p는 1,000,000,007 이고 소수입니다. k의 범위는 최대 4,000,000까지로 p의 배수가 될 수 없습니다.

 

즉 $A^{p-1}$ 를 1,000,000,007로 나눈 나머지는 해당 문제에서 언제나 값이 1입니다.

 

그렇다면, 분모는 사라지고 $n\times n-1\times ... \times n-k\times A^{p-2}$ 가 남게되는데

 

최종적으로 문제에서 구해야 하는 값은 $n\times n-1\times ... \times n-k\times k!^{p-2}\,\bmod\,p$ 가 됩니다.

 

$n\times n-1\times ... \times n-k$ 은 팩토리얼을 구현한 함수로 쉽게 구할 수 있습니다.

 

하지만 p가 1,000,000,007로 매우 큰 수인 관계로 $k!^{p-2}$ 는 분할 정복을 통한 거듭제곱 계산으로 구해야 합니다.

 

#include<iostream>

using namespace std;

const int MOD = 1000000007;

long long fact(int s, int n)
{
    long long tmp = 1;

    for (int i = s; i <= n; i++) {
        tmp = tmp * i % MOD;
    }

    return tmp;
}

long long power(int a, int b)
{
    if (b == 1) return a % MOD;

    long long tmp = power(a, b / 2);

    return b % 2 ? (tmp * tmp % MOD) * a % MOD : tmp * tmp % MOD;
}

int main(void)
{
    int n, k; cin >> n >> k;

    cout << fact(n - k + 1, n) * power(fact(1, k), MOD - 2) % MOD;

    return 0;
}