백준 1670 - 정상 회담 2

icpc.me/1670

 

 

8명이 완벽하게 악수하는 경우의 수까지 직접 구해보자.

N=8일 때 완벽하게 악수할 수 있는 경우

 

각 항을 $D_n$으로 표현했을 때 $D_2 = 1, D_4 = 2, D_6 = 5, D_8 = 14$이고 이는 카탈란 수임을 알 수 있게 된다.

 

카탈란 수를 적절히 구해주도록 하자. 다만 주어지는 나머지 987654321이 소수가 아니므로 페르마의 소정리를 통해 이항 계수에서 분모를 구할 수 없으므로 이항 계수 5를 해결하는 데 사용된 구현을 통해 카탈란 수를 구해주면 AC를 받을 수 있다.

 

전체 코드

#include <cstdio>
#include <vector>
#include <unordered_map>
 
#define mod 987654321
 
using namespace std;
using ll = long long;
 
bool nprime[20001];
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 % mod;
    return po(a * a % mod, b / 2);
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    n >>= 1;
 
    nprime[1] = true;
    for (int i = 2; i <= 2 * n; ++i)
    {
        if (nprime[i]) continue;
        
        pnum.push_back(i);
 
        for (int j = i + i; j <= 2 * n; j +=i) nprime[j] = true;
    }
 
    ll left = 1, right = 1;
 
    for (int i = 0; i < pnum.size(); ++i)
        for (int j = pnum[i]; j <= 2 * n; j *= pnum[i])
            pcnt[pnum[i]] += 2 * n / j - 2 * (n / j);
 
    for (auto it = pcnt.begin(); it != pcnt.end(); ++it)
        left *= po(it->first, it->second), left %= mod;
 
    pcnt.clear();
    
    for (int i = 0; i < pnum.size(); ++i)
        for (int j = pnum[i]; j <= 2 * n; j *= pnum[i])
            pcnt[pnum[i]] += 2 * n / j - (n - 1) / j - (n + 1) / j;
 
    for (auto it = pcnt.begin(); it != pcnt.end(); ++it)
        right *= po(it->first, it->second), right %= mod;
 
    ll res = left - right;
 
    while (res < 0)
        res += mod;
    printf("%lld", res);
}