(hdu step 2.3.6)Game of Connections(大數:凸多邊形的三角形劃分)

 

 

題目：

 

Game of Connections

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 673 Accepted Submission(s): 443   Problem DescriptionThis is a small but ancient game. You are supposed to write down the numbers 1, 2, 3, ... , 2n - 1, 2n consecutively in clockwise order on the ground to form a circle, and then, to draw some straight line segments to connect them into number pairs. Every number must be connected to exactly one another. And, no two segments are allowed to intersect.

It's still a simple game, isn't it? But after you've written down the 2n numbers, can you tell me in how many different ways can you connect the numbers into pairs? Life is harder, right? InputEach line of the input file will be a single positive number n, except the last line, which is a number -1. You may assume that 1 <= n <= 100. OutputFor each n, print in a single line the number of ways to connect the 2n numbers into pairs. Sample Input

2
3
-1

Sample Output

2
5

  SourceAsia 2004, Shanghai (Mainland China), Preliminary RecommendEddy

 

 

題目分析：

這一道題，讀完題以後，抽象以下，其模型可以歸結為“凸多邊形的三角形劃分。其中線段兩兩不相交”。而這一模型又可以使用卡特蘭數來解決。

需要注意的是：catalans[20]就已經達到了6564120420。這已經超過了int的范圍。catalans[99]的值為227508830794229349661819540395688853956041682601541047340。這已經超過了證書所能表示的范圍，所以使用大數來處理

 

代碼如下：

 

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


public class Main {

	public static void main(String[] args) {
		BigInteger catalans[] = new BigInteger[101];
		
		catalans[1] = new BigInteger(1);
		
		BigInteger four = new BigInteger(4);
		BigInteger two = new BigInteger(2);
		BigInteger one = new BigInteger(1);
		
		int i;
		for(i = 2 ; i <= 100 ; ++i){//注意catalan[20]已經是6564120420了.所以需要用到大數
			//根絕catalans數的遞推公式來求得每一項的catalan數
			catalans[i] = catalans[i-1].multiply(four.multiply(BigInteger.valueOf(i)).subtract(two)).divide(BigInteger.valueOf(i+1));
		}
		
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext()){
			int n = scanner.nextInt();
			if(n == -1){
				return ;
			}
			
			System.out.println(catalans[n]);
		}
	}
}