这几天做hdu的ACM steps,遇到了好几个卡塔兰数。

卡塔兰数是组合数学中一个常在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡塔兰
(1814–1894)命名。

卡塔兰数的一般项公式为

卡特兰数前几项为 :1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012……

怎么来的我也不知道，好几个题大神们推出是卡塔兰数，然后我就安公式用java的大数求的……我用的公式是h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (n>=2)

下面附上几道题，以后慢慢研究……

1
2
3
10

1
2
5
16796

Hint
The result will be very large, so you may not process it by 32-bit integers.
 

##代码

import java.util.Scanner;
import java.math.BigInteger;
public class Main {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner cin = new Scanner(System.in);
        BigInteger[]  a = new BigInteger[110];
        BigInteger b;
        int n,i,j;
        a[0]= new BigInteger("1");
        a[1]= new BigInteger("1");
        for(i=2;i<=100;i++){
            b=new BigInteger("0");
            for(j=0;j<i;j++){
                b=b.add(a[j].multiply(a[i-j-1]));
            }
            a[i]=b;
            //System.out.println(a[10]);
        }
            
        while(cin.hasNext()){
            n = cin.nextInt();
            System.out.println(a[n]);
        }
        cin.close();
    }

}

第二个题

看的网上的解题报告，说是卡塔兰数*A（N，N）的全排列，即不算顺序……表示不懂……不会推……

1
2
10
25
0

1
4
60949324800
75414671852339208296275849248768000000

##

第三个题

这个题是我看着那个样例，感觉是卡塔兰数，然后就那么写的，然后就过了……

1
2
3

1
2
5

第四个题

据说这个题也是……我木有发现……用dp干出来的……组合数学，坑爹啊……

3 0
3 1
3 3
0 0

Test #1:
6
Test #2:
18
Test #3:
180

##代码

代码好乱，反正就是求了所有的分支；dp[i][j]=dp[i-1][j]*(n-i+1)+dp[i][j-1]*(m-j+1);边界处理下完了……卡塔兰数解法木有看呢……

import java.util.Scanner;
import java.math.BigDecimal;
import java.math.BigInteger;
public class Main {
	public static void main(String[] args) {
		// TODO 自动生成的方法存根
	Scanner cin = new Scanner(System.in);
	int n,i,m,k,j,t=0;
	BigInteger[][] dp;
	BigInteger ww,iw,jw,nw,mw;
	while(true){
		n = cin.nextInt();
		m = cin.nextInt();
		if(n==0&&m==0)
			break;
		t++;
		if(n<m){
			System.out.println("Test #"+t+":");
			System.out.println(0);
			continue;
		}
		dp = new BigInteger[n+1][m+1];
		for(i=0;i<=n;i++)
			for(j=0;j<=m;j++)
			dp[i][j]=new BigInteger("0");
		dp[0][0]=new BigInteger("1");
		ww = new BigInteger("1");
		for(i=0;i<n;i++)
			ww=ww.add(new BigInteger("1"));
		nw = ww;
		mw = new BigInteger("1");
		for(j=1;j<m;j++)
			mw = mw.add(new BigInteger("1"));
		//System.out.println(ww+" "+mw);
		for(i=1;i<=n;i++)
			dp[i][0]=dp[i-1][0].multiply(ww=ww.subtract(new BigInteger("1")));
		//for(i=0;i<=n;i++)
		//System.out.print(dp[i][0]+" ");
		//System.out.println();
		iw = new BigInteger("0");
		for(i=1;i<=n;i++){
			iw=iw.add(new BigInteger("1"));
			jw = new BigInteger("-1");
			for(j=1;j<=m;j++){
				jw=jw.add(new BigInteger("1"));
				if(i-1>=j)
				dp[i][j]=dp[i-1][j].multiply(nw.subtract(iw));//(n-i+1);
				//System.out.println(n-i+1);
				//System.out.println(nw.subtract(iw));
				if(j>0){
					ww=dp[i][j-1].multiply(mw.subtract(jw));
					dp[i][j]=dp[i][j].add(ww);
				}
				//dp[i][j]=dp[i][j].add(dp[i][j-1].multiply(mw.subtract(jw)));//*(m-j+1);
				//System.out.print(dp[i][j]+" ");
			}
			//System.out.println();
		}
		System.out.println("Test #"+t+":");
		System.out.println(dp[n][m]);
	}
	cin.close();
	}

}

#########################################################################################################

这组合数学要是会的话感觉好牛X，什么都不用想有公式往里面一代数， so easy, 的就A了……不会压力好大啊……