3789999_re.java

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

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

public class Main {
	private BigInteger[][] num;
	private Scanner in;

	public static void main(String[] args) {
		new Main().run();
	}

	private void run() {
		in = new Scanner(System.in);
		num = new BigInteger[10][101];

		int k, n;
		while (in.hasNext()) {
			k = in.nextInt();
			n = in.nextInt();
			for (int i = 0; i <= k; i++) {
				num[i][1] = BigInteger.ONE;
			}
			for (int i = 2; i <= n; i++) {
				num[0][i] = num[0][i - 1].add(num[1][i - 1]);
				for (int j = 1; j < k; j++) {
					num[j][i] = num[j - 1][i - 1].add(
						num[j][i - 1].add(num[j + 1][i - 1]));
				}
				num[k][i] = num[k][i - 1].add(num[k - 1][i - 1]);
			}
			BigInteger tmp = BigInteger.ZERO;
			for (int i = 0; i <= k; i++) {
				tmp = tmp.add(num[i][n]);
			}
			BigInteger tight = tmp.multiply(new BigInteger("100000000"));
			BigInteger total = BigInteger.valueOf(k + 1).pow(n);
			tight = tight.divide(total);
			double ans = tight.intValue();
			System.out.format("%.5f\n", ans / 1000000.0);
		}
	}

}