ABC134 F問題：Permutation Oddness

問題. Permutation Oddness

$\{1, 2, \ldots, N\}$ の順列 $p$ の奇妙さを $\sum_{i = 1}^N |i - p_i|$ と定義する．奇妙さが $K$ であるような順列が何通りあるか答えよ．

制約： $1 \le N \le 50$ ，　 $0 \le K \le N^2$

部集合を $A = \{1, 2, \ldots, N\}, \, B = \{1, 2, \ldots, N\}$ とする辺重み付き完全二部グラフ $G = (A; B, E)$ を考える．各辺 $\{i, j\} \in E$ の重みを $w(\{i, j\}) = |i - j|$ とする．辺 $\{i, j\} \in E \, (i \in A, j \in B)$ を選ぶことと順列の要素が $p_i = j$ となることを対応付ける．このとき，求める答えは $G$ 上の重み和 $K$ の完全マッチングの個数となる．
例えば， $N = 3, \, K = 2$ の入力に対応する完全二部グラフと重み和 $2$ の完全マッチングは下の通りになる．赤色の辺重みは 0 ，青色の辺重みは 1，緑色の辺重みは 2 を表している．このときの答えは 2 となる．
　　　　　　 f:id:tatanaideyo:20190721045659p:plain:w500

解説通りに動的計画法で解く．漸化式 dp[i][j][k] を部グラフを $A = \{1, 2, \ldots, i\} \, , B = \{1, 2, \ldots, i\}$ に制限して，未選択の頂点数が $2 j$ で，確定している奇妙さが $k$ のときの完全マッチングの個数とする．このとき，遷移は

　dp[i][j][k] $=$ $(2 j + 1)$ dp[i - 1][j][k - 2 j]
　　　　　　　　　　 $+ (j + 1)^2$ dp[i - 1][j + 1][k - 2 j] $+$ dp[i - 1][j - 1][k - 2 j]

となる．遷移のイメージ図は下の通り．
　　　　　　 f:id:tatanaideyo:20190721052040p:plain:w550

計算時間： $O(N^2 K)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    const ll MOD = 1e9 + 7;

    ll N, K;
    cin >> N >> K;

    vector<vector<vector<ll>>> dp(
        N + 1, vector<vector<ll>>(N + 2, vector<ll>(K + 1)));
    dp[0][0][0] = 1;

    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j <= i; ++j) {
            for (int k = 2 * j; k <= K; ++k) {
                ll &v = dp[i][j][k];
                (v += (2 * j + 1) * dp[i - 1][j][k - 2 * j]) %= MOD;
                (v += (j + 1) * (j + 1) * dp[i - 1][j + 1][k - 2 * j]) %= MOD;
                if (0 <= j - 1) (v += dp[i - 1][j - 1][k - 2 * j]) %= MOD;
            }
        }
    }

    cout << dp[N][0][K] << endl;

    return 0;
}

完全マッチングまで考えて動的計画法っぽいなと思いつつ求めれなかった．マッチングに飽和されていない頂点部分集合を持つと状態数は $2^N$ 以上になるしな…どうしようという気分．上のように漸化式を書くとこの状態を省略できるのはなるほど感がすごい．漸化式からの遷移は自力で導けたのでそこらへんを思いつくようにするのが課題．

忘れても大丈夫

ABC134 F問題：Permutation Oddness

問題. Permutation Oddness

解法．動的計画法