摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 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;
}