(hdu step 2.3.8)小兔的棋盘(卡特兰数:从左上角走到右上角的路径数)

题目：

1
3
12
-1

1 1 2
2 3 10
3 12 416024

题目分析：

               卡特兰数的应用之一。属于“有一个n*n的矩阵，从左上角走到右上角的路径数(不能越过对角线)”。这道题其实不需要用到大数的。但是为了统一代码风格，凡是卡特兰数我都用JAVA来写。

相应的理论如下：

       1）卡特兰数原本的模型可以描述如下：“对于任意数k，前k个数中-1的个数总是小于或等于1的个数”。

       2）对于这道题，其实所求的路径就是“对于走到任一步k，前k步中向右的不熟总大于或等于向上的步数(否则就穿越对角线了)”>所以这道题可以使用卡特兰数来解决。

对于一个n*n的正方形网格，每次我们能向右或者向上移动一格，那么从左下角到右上角的所有在副对角线右下方的路径总数为

。同样引用Wikipedia上的一张图片来表示：

代码如下：

import java.math.BigInteger;
import java.util.Scanner;


public class Main {

	static BigInteger catalans[] = new BigInteger[101];
	static BigInteger four = new BigInteger("4");
	static BigInteger two = new BigInteger("2");
	static BigInteger one = new BigInteger("1");
	
	
	/**
	 * 用于求卡特兰数
	 */
	public static void prepare(){
		
		catalans[1] = new BigInteger("1");
		
		int i;
		for(i = 2 ; i <= 100 ; ++i){
			catalans[i] = catalans[i-1].multiply(four.multiply(BigInteger.valueOf(i)).subtract(two)).divide(BigInteger.valueOf(i+1));
		}
	}
	
	public static void main(String[] args) {
		prepare();
		
		Scanner scanner = new Scanner(System.in);
		
		int t = 1;
		while(scanner.hasNext()){
			int n = scanner.nextInt();
			
			if(n == -1){
				return ;
			}

			//因为最后的结果应该是包含从左上角和右下角过去的两种解法.所以最后的结果需要乘以2
			System.out.println(t++ + " " + n + " " + catalans[n].multiply(two));
		}
	}
}