HDU 1134( Game of Connections Catalan数的第三种应用！)

给定N*2个点，求分别将其两两相连，每个点仅链接一次，而且每条线段不相交！

题目分析：

这又是Catalan数

直接套公式吧，其实证明目前我还没会，嘎嘎

公式：

f[n]=;

直接计算就可以了，这里设计到大数的运算，我是用JAVA写的，不想用C模拟了 呵呵

代码：

import java.io.*;
import java.util.*;
import java.math.*;
public class Main {
	public static void main(String args[]){
		List list=new ArrayList(102);
		BigInteger f=BigInteger.valueOf(1);
		list.add(f);
		list.add(f);
		f=BigInteger.valueOf(2);
		list.add(f);
		for(int i=3;i<=100;i++){
			BigInteger sum=BigInteger.valueOf(0);
			for(int j=0;j<i;j++){
				sum=sum.add( ((BigInteger)list.get(i-1-j)).multiply( ((BigInteger) list.get(j) )) );
			}
			list.add(sum);
		}
		Scanner cin=new Scanner(System.in);
		int n;
		while(cin.hasNext()){
			n=cin.nextInt();
			if(n==-1)
				break;
			System.out.println(list.get(n));
		}
	}
}