TopCoder SRM 666 Div1 Medium: SumOverPermutations
コード
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; } }