IOI研習營模考2-1三元樹
作法 : 公式 (組合)
本人是由二元樹的公式"猜"出來的
http://nccur.lib.nccu.edu.tw/bitstream/140.119/32573/7/75101807.pdf
原本 二元樹 Tn=1/(n+1)*C(2*n,n)
->猜測 三元樹 Tn=1/(2*n+1)*C(3*n,n)
所以可以歸納 ? K元樹 N個節點 Tn=1/((K-1)*n+1)*C(K*n,n) ? 自己想想吧
/*****************************************************************/
#include<stdio.h>
#include<stdlib.h>
int GCD(int x,int y)
{
int temp;
while(x%y)
{
temp=x;
x=y;
y=temp%y;
}
return y;
}
main()
{
int N;
while(scanf("%d",&N)==1)
{
int C[15001]={0},a,b,c;
for(a=2*N+1;a<=3*N;a++)
C[a]=a;
int t=2*N+1;
for(a=2;a<=N;a++)
for(b=2*N+1,c=a;b<=3*N&&c!=1;b++)
{
if(C[b]==1) continue;
int gcd=GCD(C[b],c);
C[b]/=gcd;
c/=gcd;
if(t!=1)
{
gcd=GCD(C[b],t);
t/=gcd;
C[b]/=gcd;
}
}
long long int ANS=1;
for(a=2*N+1;a<=3*N;a++)
ANS=ANS*C[a]%10000000;
printf("%lld\n",ANS);
}
return 0;
}