首页 > 代码库 > HDU 1131

HDU 1131

N个节点的不同的树的数目。这样

随便取一个节点作为根,那么他左边和右边的儿子节点个数就确定了,假定根节点标号为x,那么左子树的标号就从1x-1,x-1个,右子树的标号就从x+1n,共n-x个,那么我们的x1取到n,就获得了所有的情况数

这是一个递推的式子,初始值与卡特兰数的初值相同。所以,解正是卡特兰数。又由于节点有序,所以乘上N!。

import java.math.BigDecimal;import java.math.BigInteger;import java.util.Scanner;import java.io.InputStreamReader;class Cont{	BigDecimal []num;	Cont(){		num=new BigDecimal[110];		num[0]=new BigDecimal(1);		BigDecimal Tmp;		for(int i=1;i<=100;i++){			Tmp=new BigDecimal(i);			num[i]=num[i-1].multiply(Tmp);		}	}}public class Main{    public static void main(String args[]){        Scanner in=new Scanner(System.in);        BigDecimal []Can=new BigDecimal[110];        Can[0]=new BigDecimal(1);        BigDecimal B,C,D;        Cont Conmul=new Cont();        for(int i=1;i<=100;i++){            B=new BigDecimal(4*i-2);            C=new BigDecimal(i+1);            D=Can[i-1].multiply(B);            Can[i]=D.divide(C);        }        while(in.hasNext()){    	int x=in.nextInt();	if(x==0) break;	BigDecimal ans=new BigDecimal(1);	ans=ans.multiply(Can[x]);	ans=ans.multiply(Conmul.num[x]);	System.out.println(ans);        }    }}

  

HDU 1131