Permutation Oddness [AtCoder Beginner Contest 134 F]

https://atcoder.jp/contests/abc134/tasks/abc134_f

前提知識

• 動的計画法（箱根DP）

解説

https://atcoder.jp/contests/abc134/submissions/6480100

箱根DPという典型DPテクがあるので、そこをベースに考えてみる。 今回の問題を1つの順列の入れ替えと考えるのではなく、2つの順列A,Bのマッチング問題と考える。

dp[i][rest][k] := 順列Aをi個使っていてrest個マッチングしていなくて、 順列Bをi個使っていてrest個マッチングしていないときに、 マッチングで差の和がkであるときの組み合わせ

これを適切に計算できれば、dp[N][0][K]が答えになる。 dp[i][rest][k]からの遷移の可能性は5通りある。

• どちらの順列のi+1番目も使わない
  • 使わないと、kは2*rest+2だけ増える
• 順列Aのi+1番目と、順列Bの残りとマッチングさせる
  • kは2*restだけ増える
  • どの残りとマッチングさせるかでrest通りある
• 順列Bのi+1番目と、順列Aの残りとマッチングさせる
  • kは2*restだけ増える
  • どの残りとマッチングさせるかでrest通りある
• 順列Aのi+1番目と、順列Bのi+1番目とマッチングさせる
  • kは2*restだけ増える
• 順列Aのi+1番目と順列Bの残り、順列Bのi+1番目と順列Aの残りとマッチングさせる
  • kは2*rest-2だけ増える
  • どの残りとマッチングさせるかでrest²通りある

これでゴリゴリ遷移させていくと、答えが出てくる。

int N, K;
mint dp[51][51][3100];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    dp[0][0][0] = 1;
    rep(i, 0, N) rep(rest, 0, N) rep(k, 0, K + 1) {
        // どちらの順列のi + 1番目も使わない
        dp[i + 1][rest + 1][k + 2 * rest + 2] += dp[i][rest][k];

        // 順列Aのi + 1番目と、順列Bの残りとマッチングさせる
        if (rest) dp[i + 1][rest][k + 2 * rest] += dp[i][rest][k] * rest;

        // 順列Bのi + 1番目と、順列Aの残りとマッチングさせる
        if (rest) dp[i + 1][rest][k + 2 * rest] += dp[i][rest][k] * rest;

        // 順列Aのi + 1番目と、順列Bのi + 1番目とマッチングさせる
        dp[i + 1][rest][k + 2 * rest] += dp[i][rest][k];
        
        // 順列Aのi + 1番目と順列Bの残り、順列Bのi + 1番目と順列Aの残りとマッチングさせる
        if(rest) dp[i + 1][rest - 1][k + 2 * rest - 2] += dp[i][rest][k] * rest * rest;
    }
    cout << dp[N][0][K] << endl;
}