BOJ 7737 삼각분할
문제 설명
볼록 $n$각형을 삼각분할 하는 가짓수를 $T_n$이라 할 때, $T_3+T_4+…+T_n$을 구하는 문제이다.
이때 수가 너무 커질 수 있으니 문제에서 주어진 모듈러로 나눈 나머지를 구해야 한다.
기본 지식
삼각 분할의 가짓수임은 카탈란 수임이 잘 알려져 있다. 증명은 생략한다.
$T_{n+2}=\frac{(2n)!}{n!(n+1)!}$이 된다.
$m$과 서로소인 정수 $a$에 대해, $a^{\phi(m)} \equiv 1 (mod$ $m)$임이 성립한다.(오일러 정리)
따라서 $a$의 역원은 $a^{\phi(m)-1}$로 간단하게 구할 수 있다.
풀이
$n\leq 10^5$이므로 $T_n$을 빠르게 구해서 더하면 될 것이다.
$\frac{(2n)!}{n!(n+1)!}$을 계산해야 하는데, 당연히 그냥 계산하기에는 큰 수이고 $mod$ $m$ 상에서 구해야 한다. 오일러 정리를 이용하고 싶지만 일반적으로 $m$과 $n!$, $(n+1)!$이 서로소일 리가 없다.
다행히 모듈러가 크지 않으므로, 모듈러를 소인수분해하고 생각하자.
이제 $n!$을 모듈러의 각 소인수의 지수와, 그 소인수를 제외한 수들의 곱으로 분리해 생각해보자.
전체 $T_n$의 각 소인수의 지수는 ($(2n)!$의 지수-$n!$의 지수-$(n+1)!$의 지수) 로 구할 수 있고, 나머지 서로소인 부분은 오일러 정리를 이용해 역원을 곱해주는 것으로 따로 계산해줄 수 있다.
최종적으로 이 나머지 부분에 각 소인수를 다시 곱해주면 $T_n$을 구할 수 있고, 문제를 풀 수 있다.
정답 코드
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
ll n, m, k, ans, mod=1e9+7;
ll fac[202020], e[10][202020];
//fac[n]: n!의 mod와 서로소인 부분
//e[i][n]: n!의 mod의 i번째 소인수의 지수
ll pw(ll a, ll b)
{
ll ret=1;
while(b)
{
if(b&1) ret=ret*a%mod;
a=a*a%mod;
b>>=1;
}
return ret;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
ll i, j, temp=0;
cin>>n>>mod;
m=k=mod;
vector<ll> p;
for(i=2;i*i<=k;i++)
{
if(k%i) continue;
m=m/i*(i-1);
while(k%i==0) k/=i;
p.push_back(i);
}
if(k>1){
m=m/k*(k-1);
p.push_back(k);
}
m--;//m=phi(mod)-1
fac[0]=1;
for(i=1;i<202020;i++)
{
k=i;
for(j=0;j<p.size();j++)
{
e[j][i]=e[j][i-1];
while(k%p[j]==0)
{
k/=p[j];
e[j][i]++;
}
}
fac[i]=fac[i-1]*k%mod;
}
for(i=1;i<=n-2;i++)
{
temp=fac[2*i]*pw(fac[i], m)%mod*pw(fac[i+1], m)%mod;
for(j=0;j<p.size();j++)
temp=temp*pw(p[j], e[j][2*i]-e[j][i]-e[j][i+1])%mod;
ans=(ans+temp)%mod;
}
cout<<ans;
}