POJ2084 Game of Connections（catalan數）

​​http://poj.org/problem?id=2084​​

大意：有2n個數字形成一個圓形，直線段連接配接一對數字，每一個數字必須連接配接到另一個數字上。（沒有相交的線段）

分析：

沒有相交的線段"，2,3隻能在右邊的圓形區域進行比對，4——8也不能越過紅線，在三角形中進行連線比對。設n個點的比對方案數是h(n)，那麼中的結果就該是h(2)h(5)。極限情況：1和2連接配接，答案就該是h(0)h(n-1)； 1和8連接配接，答案是h(n-2)h(1)。沒錯，真相隻有一個！這是catalan數。注意：這裡的n不是2n，因為1，4相連和4，1相連是一回事。

由通項公式得到：h(n)=C(2n,n)/(n+1)=(2n)!/[n!(n+1)!]

n達到了100，涉及到 大數。。

import java.math.BigInteger;
import java.util.*;
public class Main {
    public static BigInteger []fac=new BigInteger[405];
    public static void get(){
        fac[1]=BigInteger.ONE;
        for(int i=2;i<=400;i++){
            fac[i]=fac[i-1].multiply(BigInteger.valueOf(i));
        }
    }
    public static void main(String[] args) {
        Scanner cin=new Scanner(System.in);
        int n;
        get();
        while(cin.hasNext()){
            n=cin.nextInt();
            if(n==-1) break;
            System.out.println(fac[2*n].divide(fac[n]).divide(fac[n+1]));
        }
    }
}      

做題時，如果不能嚴格證明它是catalan，也可以從前幾項猜想可能性。catalan的前幾項：

1

2

5

14

42

132

429

1430

4862

16796

58786

208012