3278994_ac_235ms_4384k.java

北大大牛代码 1240道题的原代码 超级权威

import java.math.*;
import java.util.*;

public class Main
{
	static long pow2[], C[][];
	static BigInteger num[];
	
	public static void init()
	{
		pow2 = new long[51];
		C = new long[51][51];
		pow2[0] = 1;
		int i, j;
		for(i = 1;i < 51;++ i) pow2[i] = pow2[i-1] * 2;
		for(i = 0;i < 51;++ i) C[i][0] = C[i][i] = 1;
		for(i = 1;i < 51;i ++)
			for(j = 1;j < i;j ++)
				C[i][j] = C[i-1][j-1] + C[i-1][j];
		
		num = new BigInteger[51];
		num[1] = BigInteger.valueOf(1);
		for(i = 2;i < 51;i ++)
		{
			num[i] = BigInteger.valueOf(0);
			for(j = 1;j < i;j ++)
			{
				BigInteger tmp = BigInteger.valueOf(1);
				tmp = tmp.multiply(num[j]);
				tmp = tmp.multiply(num[i-j]);
				tmp = tmp.multiply(BigInteger.valueOf(pow2[j] - 1));
				tmp = tmp.multiply(BigInteger.valueOf(C[i-2][j-1]));
				num[i] = num[i].add(tmp);
			}
		}
	}
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		init();
		while(true)
		{
			int n = sc.nextInt();
                        if(n==0)
                            break;
			System.out.println(num[n]);
		}
	}
}