2084 Game of Connections

問題概要

円周上に点が順に1,2,3,...,2nと並んでいる。
これらの点を全て、交差しない線分で一対一にペアを作るように結ぶ。
このような結び方は何通りあるか求めよ。

n≦100とする。

解法

1番の点が2i番目に結ばれるとする。
すると、円は2(i-1)個の点の部分と2(n-k)個の部分に分かれる。

全体の結び方はそれぞれの場合の数の積の和だから、
dp[n]=Σ{dp[i-1]*dp[n-k]|1≦i≦n}という漸化式が成り立ち、DPできる。
答えは100までなのであらかじめ計算しておくとよい。

ソースコード

class Main {
	public static void main(String[] args) {
		new Main().new PKU2084().run();
	}
	class PKU2084{
		void run(){
			BigInteger dp[]=new BigInteger[101];
			dp[0]=BigInteger.ONE;
			for(int i=1;i<101;i++){
				dp[i]=BigInteger.ZERO;
				for(int k=1;k<=i;k++)dp[i]=dp[i].add(dp[i-k].multiply(dp[k-1]));
			}
			int n; Scanner sc=new Scanner(System.in);
			for(;;){
				n=sc.nextInt(); if(n<=0)break;
				System.out.println(dp[n]);
			}
		}
	}
}