TopCoder SRM 666 Div1 Medium: SumOverPermutations

解法

kmjp.hatenablog.jp

コード

public class SumOverPermutations {
	private final int MOD = (int) 1e9 + 7;

	public int findSum(int n) {
		if (n == 1) {
			return 1;
		}
		// パスカルの三角形を作る
		int[][] nCm = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= i; j++) {
				nCm[i][j] = (j == 0 || j == i) ? 1
						: (nCm[i - 1][j - 1] + nCm[i - 1][j]) % MOD;
			}
		}

		long[] oneClosed = new long[n];// i個分の片方だけ閉じた区間を埋める埋め方
		long[] bothClosed = new long[n];// i個分の両方とも閉じた区間を埋める埋め方

		oneClosed[0] = bothClosed[0] = 1;
		oneClosed[1] = n - 1;
		bothClosed[1] = n - 2;

		for (int i = 2; i < n; i++) {
			for (int j = 0; j < i; j++) {
				if (j == 0) {
					// 片方が空いている区間の閉じている端にボールを入れる時
					long add = oneClosed[i - 1];
					add = (add * (n - 1)) % MOD;// ボールの選び方はn-1通りある

					oneClosed[i] += add;
				} else {
					// 片方が空いている区間の閉じている方からj番目のところにボールを入れる時
					long add = bothClosed[j];// 新しく両側が閉じたj個分の区間が生まれる
					add = (add * oneClosed[i - 1 - j]) % MOD;// もう片方はi-1-j個分の片方が閉じた区間となる
					add = (add * n) % MOD;// ボールが置かれる場所は両方が空いているのでn通りの選び方がある
					// 全く同じ手順で同じ結果をもたらす場合でも、今置いたj番目のボールの右にボールを置くか、左にボールを置くか、という選択が各ボールについてできる
					add = (add * nCm[i - 1][j]) % MOD;

					oneClosed[i] += add;
				}
				if (j == 0 || j == i - 1) {
					// 両側が空いている区間の閉じている端にボールを入れる時
					long add = bothClosed[i - 1];
					add = (add * (n - 1)) % MOD;// ボールの選び方はn-1通りある

					bothClosed[i] += add;
				} else {
					long add = bothClosed[j];// 新しく両側が閉じたj個分の区間が生まれる
					add = (add * bothClosed[i - 1 - j]) % MOD;// もう片方もi-1-j個分の両側が閉じた区間となる
					add = (add * n) % MOD;// ボールが置かれる場所は両方が空いているのでn通りの選び方がある
					add = (add * nCm[i - 1][j]) % MOD;

					bothClosed[i] += add;
				}
			}
			oneClosed[i] %= MOD;
			bothClosed[i] %= MOD;
		}

		long ans = 0;
		for (int i = 0; i < n; i++) {
			// 1番最初のボールをi番目に置く時
			if (i == 0 || i == n - 1) {
				// 一番最初のボールを端に置く場合
				long add = oneClosed[n - 1];
				add = (add * n) % MOD;// 両方とも空いていることになっているのでn通りの選び方がある
				ans += add;
			} else {
				long add = oneClosed[i];// 新しくi個分の片方が閉じた区間ができる
				add = (add * oneClosed[n - 1 - i]) % MOD;// 新しくn-1-i個分の片方が閉じた区間ができる
				add = (add * n) % MOD;// ボールが置かれる場所は両方が空いているのでn通りの選び方がある
				add = (add * nCm[n - 1][i]) % MOD;

				ans += add;
			}
			ans %= MOD;
		}
		return (int) ans;
	}
}