백준 11439 - 이항 계수 5

icpc.me/11439

 

 

$N, K, M \leq 4 \times 10^6$ 일 때 $\binom{N}{K} \mod M$ 을 구하는 문제이다.

 

이 문제는 이항 계수 4까지 풀어나가면서 배운 지식을 활용할 수 없다.

 

N, K가 크기에 단순한 dp로 풀 수 없고 M이 소수라는 보장이 없기에 페르마의 소정리조차 사용할 수 없다.

 

그렇다면 이건 개인용 컴퓨터로는 풀 수 없는 문제일까? 물론 그렇지 않다. 이 글을 따라가 보자.

 

소수 추출하기

간단하게 작은 수의 이항 계수를 구해보자.

 

$\binom{5}{4}$ 를 계산한다고 했을 때 $\frac{5!}{4!\times(5 - 4)!} = \frac{5 \times 4 \times 3 \times 2 \times 1}{(4 \times 3 \times 2 \times 1) \times (1)}$ 가 된다.

 

답은 5가 되지만 그전에 다른 걸 살펴볼 필요가 있다.

 

2로 몇 번 나눠지는가?

5!이 2로 몇 번 나눠지는지 보자. 2와 4가 있으므로 3번 나눠지는 걸 쉽게 알 수 있다.

 

아! 그러면 분모와 분자를 소인수분해해주면 수가 작아져서 반복문으로도 되겠구나!라고 생각하고 무턱대고 나누면 TLE를 받게 된다.

 

다섯 조각인 케이크를 몇 묶음으로 묶어서 나눠준다고 해보자. 각 케이크 조각에는 번호를 붙였다.

1

2

3

4

5

 

이 케이크를 두 조각씩 배분한다고 해보자.

1

2

3

4

5

 

케이크는 두조각씩 두 묶음을 분배할 수 있고 케이크의 각 묶음에서 두 조각이 되는 지점은 2와 4가 된다.

 

그러면 이번엔 네 조각씩 배분해보자.

1

2

3

4

5

 

케이크는 네조각씩 한 묶음을 분배할 수 있고 케이크의 각 묶음에서 네 조각이 되는 지점은 4이다.

 

그리고 앞서 살펴봤던 지점들은 총 3개가 된다.

 

무언가 깨달았는가?

 

2로 몇 번 나눠지는지 알기 위해 소인수분해를 일일이 하는게 아닌 팩토리얼에 사용되는 수를 나열하고 2로 나눠지는 수, 4로 나눠지는 수, 2의 제곱수로 나눠지는 수... 들을 더하면 2로 몇번 나눠지는지 로그의 시간 복잡도로 더 빠르게 알 수 있다.

 

이 과정에서 제곱수를 활용하니 모든 수를 고려할 필요가 없고 소수만을 이용해 계산하면 된다.

 

이 방법을 이용해 map이나 배열을 사용해서 분해된 소수의 개수를 저장해 주자.

 

분모의 경우 $2^{-1}$이므로 분자와 동일한 방식으로 구해준 후 분자에서 빼면 마지막엔 곱해야 할 수만 남게 된다.

 

이 과정에서 유리수가 될 문제는 없냐고?

 

여기에 관련된 증명이 있으니 참고하면 될 것이다.

 

이를 수식으로 정리하면 $\binom{N}{K}$에서 2를 소인수분해 한다고 했을 때 그 개수는 $\Sigma_{i = 1}^{} (\frac{N}{2^i} - \frac{K}{2^i} - \frac{N - K}{2^i})$ 으로 나타낼 수 있다.

 

이제 소인수분해를 마쳤으니 남겨진 소수들을 곱하고 나머지를 취하면 문제를 해결할 수 있다.

 

전체 코드

#include <bits/stdc++.h>
 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
using namespace std;
using ll = long long;
 
int n, k, m;
 
bool nprime[4000001];
vector<int> pnum;
unordered_map<int, int> pcnt;
 
ll po(ll a, int b)
{
    if (!b)
        return 1;
 
    if (b == 1)
        return a;
    
    if (b & 1)
        return po(a, b - 1) * a % m;
    
    return po(a * a % m, b / 2);
}
     
int main()
{
    cin >> n >> k >> m;
    nprime[1] = true;
 
    for (int i = 2; i <= n; ++i)
    {
        if (nprime[i])
            continue;
        
        pnum.push_back(i);
 
        for (int j = i + i; j <= n; j += i)
            nprime[j] = true;
    }
 
    for (int j = 0; j < pnum.size(); ++j)
        for (ll h = pnum[j]; h <= n; h *= pnum[j])
            pcnt[pnum[j]] += n / h - k / h - (n - k) / h;
 
    ll res = 1;
 
    for (auto it = pcnt.begin(); it != pcnt.end(); ++it)
    {
        res *= po(it->first, it->second);
        res %= m;
    }
 
    cout << res;
}