题意：有n个点，问把它们连起来的方案数
思路：n个点一共n * (n-1) / 2 条边,设为h[n],一共方案数2 ^ h[n]，去掉不连通的情况，选取一个固定点，再选k（0 ≤ k < n-1）个点方案数C(n-1,k)，和它连通方案数ans[k+1]，其他n-1-k个点的条边随便连
ans[n] = 2^h[n]- sum{ C(n-1,k) * ans[k+1] * 2^h[ n-1-k ] } （0 ≤ k < n-1）
import java.util.*; import java.math.*; public class Main{ static BigInteger ans[] = new BigInteger[55]; static int h[] = new int[55]; static BigInteger C[][] = new BigInteger[55][55]; static BigInteger two[] = new BigInteger[2505]; public static void main(String[] args) { // TODO Auto-generated method stub two[0] = BigInteger.ONE; for(int i = 1; i < 2505; i++) two[i] = two[i-1].multiply(BigInteger.valueOf(2)); C[0][0] = BigInteger.ONE; for(int i = 1; i <= 50; i++) { for(int j = 0; j <= i; j++) { if(j == 0 || j == i) C[i][j] = BigInteger.ONE; else C[i][j] = C[i-1][j-1].add( C[i-1][j] ); } } h[1] = 0; for(int i = 2; i <= 50; i++) h[i] = i*(i-1)/2; ans[1] = BigInteger.ONE; for(int i = 2; i <= 50; i++) { BigInteger temp; temp = two[ h[i] ]; for(int j = 0; j <= i-2; j++) temp = temp.subtract(two[h[i-1-j]].multiply(ans[j+1]).multiply(C[i-1][j])); ans[i] = temp; } Scanner sc = new Scanner(System.in); while(sc.hasNext()) { int n = sc.nextInt(); if(n == 0) break; System.out.println(ans[n]); } } } /* a.add(b); 加法运算 a.subtract(b); 减法运算 a.multiply(b); 乘法运算 a.divide(b); 除法运算 a.mod(b); 取模运算 a.gcd(b); 最大公因数 a.max(b); 最大值(a,b) a.min(b); 最小值(a,b) a.modPow(k, mod); 返回(a^k)%mod a.pow(b); a.toString(); 返回大整数的string型 System.out.println(a); 自带换行的输出 System.out.print(a); 不自带换行的输出 Scanner sc = new Scanner(System.in); if(n.compareTo(BigInteger.ZERO)==0) break; */
第二次写Java，temp.subtract（）完了后，竟然忘记赋给temp了，上次是add（），调了半天，果然还是不习惯
