首页 > 代码库 > 【HDOJ】1134 Game of Connections

【HDOJ】1134 Game of Connections

Catlan数。

 1 /* 1134 */ 2 import java.util.Scanner; 3 import java.math.BigInteger; 4  5 /* 6     Catalan: 7     (1) h(n) = h(n-1) * (4*n-2) / (n+1) 8     (2) h(n) = C(2n, n) / (n+1) 9     (3) h(n) = C(2n, n) - C(2n, n+1)10 */11 12 public class Main {13     public static void main(String args[]) {14         Scanner cin = new Scanner(System.in);15         BigInteger[] bi = new BigInteger[MAXN];16         bi[1] = BigInteger.ONE;17         bi[2] = BigInteger.valueOf(2);18         for (int i=3; i<MAXN; ++i) {19             BigInteger x = BigInteger.valueOf(4*i-2);20             BigInteger y = BigInteger.valueOf(i+1);21             bi[i] = bi[i-1].multiply(x).divide(y);22         }23         int n;24         while (cin.hasNext()) {25             n = cin.nextInt();26             if (n == -1)27                 break;28             System.out.println(bi[n]);29         }30     }31     32     public static final int MAXN = 101;33 }

 

【HDOJ】1134 Game of Connections