UVa 10007 - Count the Trees（卡特兰数+阶乘+大数）

题目链接：UVa 10007

题意：统计n个节点的二叉树的个数

1个节点形成的二叉树的形状个数为：1

2个节点形成的二叉树的形状个数为：2

3个节点形成的二叉树的形状个数为：5

4个节点形成的二叉树的形状个数为：14

5个节点形成的二叉树的形状个数为：42

把n个节点对号入座有n！种情况

所以有n个节点的形成的二叉树的总数是：卡特兰数F[n]*n！

程序：

 import java.math.BigInteger;

 import java.util.Scanner;

 public class Main {

     public static void main(String args[]){

         Scanner cin=new Scanner(System.in);

         BigInteger h[]=new BigInteger[302];

         BigInteger a[]=new BigInteger[302];

         BigInteger fact=BigInteger.valueOf(1);

         int n;

         h[1]=BigInteger.valueOf(1);

         a[1]=BigInteger.valueOf(1);

         for(int i=2;i<=300;i++){

             fact=fact.multiply(BigInteger.valueOf(i));

             BigInteger k=BigInteger.valueOf(i*4-2);

             h[i]=h[i-1].multiply(k);

             h[i]=h[i].divide(BigInteger.valueOf(i+1));

             a[i]=h[i].multiply(fact);

             //System.out.println(" "+h[i]+" "+fact+" "+a[i]);

         }

         while(true){

             n=cin.nextInt();

             if(n==0)

                 break;

             System.out.println(a[n]);

         }

     }

 }