HDU 1003 / Game of Connections：卡特蘭數與大整數

題目轉化

2n 個點圍成圓，兩兩連線且線段不相交，求連法總數。等價於凸 (n+2) 邊形三角剖分數，即第 n 個卡特蘭數：

C₀ = 1
Cₙ = Cₙ₋₁ * (4n-2) / (n+1)

數據範圍

• n ≤ 100
• C₂₀ = 6,564,120,420 超 32 位
• C₉₉ ≈ 2.27×10⁵⁷ 需大整數

Java BigInteger 實現

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

public class Main {
    public static void main(String[] args) {
        BigInteger[] C = new BigInteger[101];
        C[1] = BigInteger.ONE;
        for (int i = 2; i <= 100; ++i) {
            C[i] = C[i-1]
                .multiply(BigInteger.valueOf(4*i - 2))
                .divide(BigInteger.valueOf(i + 1));
        }
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            if (n == -1) break;
            System.out.println(C[n]);
        }
    }
}

關鍵點

• 遞推公式避免大數階乘除法，精度穩定
• BigInteger 自動處理任意精度
• 預計算所有 C[1..100]，查詢 O(1)

樣例

輸入：
2
3
-1
輸出：
2
5