4004426_ac_3375ms_4124k.java

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

//package p1846;

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

public class Main {

	private Scanner in;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		new Main().run();
	}
	
	private void run() {
		in = new Scanner(System.in);
		int n = in.nextInt();
		BigInteger[] f = new BigInteger[n + 3];
		f[3] = new BigInteger("1");
		f[4] = new BigInteger("3");
		f[5] = new BigInteger("12");
		BigInteger F = new BigInteger("12");
		for (int i = 5; i < n; i++) {
			BigInteger tmp = BigInteger.valueOf(i * (i - 1) / 2);
			F = F.multiply(BigInteger.valueOf(i));
			f[i + 1] = F;
			for (int k = 2; k < i - 2; k++) {
				f[i + 1] = f[i + 1].add(f[i - k].multiply(tmp));
				tmp = tmp.multiply(BigInteger.valueOf(i - k));
			}
		}
		System.out.println(f[n]);
	}

}