竹園論壇

標題: d230 - IOI研習營模考2-1三元樹 [打印本頁]

作者: Sylveon 時間: 2014-5-2 07:57
標題: d230 - IOI研習營模考2-1三元樹
原文：http://zerojudge.tw/ShowProblem?problemid=d230
AC ：http://zerojudge.tw/Submissions?problemid=d230&account=lfs92002
ACCODE：http://ideone.com/L1pMBW
廣義卡特蘭數，代公式Tk(n) = 1/((k-1)*n)*C(k*n,n)就OK，只是MOD的數字不是質數，無法使用逆元(乘法反元素)來處理除法，在此使用了約分法來進行除法的部分。應該可以DP，只是我懶得推公式XD

/**********************************************************************************/
/*  Problem: d230 "IOI研習營模考2-1三元樹" from IOI                      */
/*  Language: CPP (644 Bytes)                                                    */
/*  Result: AC(0.4s, 288KB) judge by this@ZeroJudge                            */
/*  Author: lfs92002 at 2014-03-14 09:16:05                                     */
/**********************************************************************************/

#include<cstdio>
#include<algorithm>
using namespace std;
#define MOD 10000000
int base[15001];
inline int gcd(int a,int b)
{
while((a%=b)&&(b%=a));
return a+b;
}
int main()
{
int n;
int p,j;
while(~scanf("%d",&n))
{
for(int i=2*n+1;i<=3*n;++i)
base[i]=i;
for(int i=1;i<=n;++i)
{
p=i,j=2*n+1;
while(p!=1)
{
int d=gcd(p,base[j]);
p/=d;
base[j++]/=d;
}
}
p=2*n+1;
j=2*n+1;
while(p!=1)
{
int d=gcd(p,base[j]);
p/=d;
base[j++]/=d;
}
long long ans=1;
for(int i=2*n+1;i<=3*n;++i)
ans=ans*base[i]%MOD;
printf("%lld\n",ans);
}
return 0;
}

歡迎光臨竹園論壇 (http://forum.tfcis.org/)