ABC134 F. Permutation Oddness

問題

1からNまでの順列pの「奇妙さ」を「Σ_{i=1}^N |i - p_i|」と定義する。
奇妙さがkであるような順列の個数の10^9+7で割った余りを求めよ。

制約

• 1 <= N <= 50
• 0 <= K <= N^2

解法

「1からNを並べたもの」と「順列p」のペアを考える。
順列pでの数字を線でつないで表現すると以下のように書ける。

この場合、右側の順列pは{3, 1, 4, ?, ?}に対応する。

ところで、問題の「奇妙さ」は、「数字の間に引いた線」と「ペアの線」の交点(赤色の点)の数で考えることができる。
これを元にDPを考える。

そのまま考えると、つないでいない点を保持する必要がありそうでbitDPになりそうだが、以下のように考えると、点の個数だけ保持すれば良くなる。

状態は、
dp[i][j][k][l] := iペア目までで、まだつないでいない左側の点がj個、まだつないでいない右側の点がk個、ここまでの奇妙さの合計がlである順列の個数
だが、jとkは実は常に同じになり、片方だけで良いので、
dp[i][j][k] := iペア目までで、片側でまだつないでいない点がj個、ここまでの奇妙さの合計がkである順列の個数
となる。

遷移は、配るDPで考えると、dp[i][j][k]について、(i+1)ペア目をどうするかで4パターンありえる。

1. 両方共、点を繋がない
   • 横線と交差する点は2*(j+1)個になるので、dp[i+1][j+1][k+2*(j+1)] += dp[i][j][k]
2. (i+1)ペア目同士を繋ぐ
   • 横線と交差する点は2*j個になるので、dp[i+1][j][k+2*j] += dp[i][j][k]
3. (i+1)ペア目の片方を、iペア目以前の繋いでない点のどれかと繋ぐ
   • 横線と交差する点は2*j個になるが、iペア目以前のどれに繋ぐかでj通り、どちら側かで2通りなので、dp[i+1][j][k+2*j] += dp[i][j][k] * 2*j
4. (i+1)ペア目の両方を、iペア目以前の繋いでない点のどれかと繋ぐ
   • 横線と交差する点は2*(j-1)個になり、iペア目以前のどれに繋ぐかが左右でj通りずつあるので、dp[i+1][j-1][k+2*(j-1)] += dp[i][j][k] * j*j

初期値はdp[0][0][0] = 1通りで計算すればよい。
答えはdp[N][0][K]になる。

これは、箱根駅伝DP(箱根DP)とも呼ばれるらしい。
Hakone | Aizu Online Judge