11401 : 이항계수 3 (Dynamic Programming, Divide and Conquer) [C++]

1번, 2번 문제들과 확연히 차이나는 입력의 범위. 400만!

DP를 사용해서 풀 수 없는 문제이다. 하지만 DP가 쓰이긴 한다!

수학은 너무 어렵다. 곱셈의 역원을 공부해보다가 모르겠어서 도움을 구했다.

왜 곱셈의 역원을 구해야하는가?

N! / (K! * (N-K)!) 에서 K! * (N-K)! 의 역원을 구해야 하기 때문!

곱셈의 역원을 구하는 정리인 페르마의 소정리를 이용하면

p가 1000000007 이지만 분할 정복을 이용한 제곱 수 계산 덕분에 logP 시간 소요.

분할 정복을 이용한 제곱 수 계산은 계속 써먹을 것 같아서 따로 올려놓았다.

DP가 쓰이는 부분은 구해준 400만의 역원을 바탕으로 모든 역원을 구하는 부분이다.

그러므로 총 시간 소요는 O(N+LogP)

long long BinomialCoefficient::GetNum(int N, int K)
{
    this->Factorial[1] = 1;
    for (int i = 2; i <= 4000000; i++)
        this->Factorial[i] = (this->Factorial[i - 1] * i) % P;            
    
    this->Invert[4000000] = this->Pow_DC(this->Factorial[4000000], P - 2);
    for (int i = 4000000 - 1; i > 0; i--) 
        this->Invert[i] = (this->Invert[i + 1] * (i + 1)) % P;
     
    if (N == K || K == 0) 
        return 1;

    long long Num = (this->Factorial[n] * this->Invert[n - k]) % P;
    Num = (Num * this->Invert[k]) % P;
    
    return Num;
}

<소스 코드>

*Source of the problem = https://www.acmicpc.net/problem/11401

*문제 출처 : BAEKJOON ONLINE JUDGE