[ABC134F] Permutation Oddness
好题，牛牛的一个套路 —— \(\textsf H\)\(\textsf {anghang}\)
写起来简单，想起来难的一个东西，难点主要是在 状态设置 上
我们可以把 \(1 \sim N\) 拆点，于是原题相当于求一个 二分图的完美匹配，并使其 怪异度为 \(k\)
我们考虑设置 \(f_{i, j, k}\) 三个状态
分别表示 当前考虑了前 \(i\) 对点，当前有 \(j\) 对 没有匹配上，当前怪异度为 \(k\)
显然最终答案就是 \(f_{N, 0, K}\)
这里可以发现，当前没有匹配上 其实就是 最终匹配上的点不是前 \(i\) 对点
我们顺序枚举三个状态，当每次 一个新点加入考虑（++i）时，容易发现以下 三种情况
注意，下面 第三维 表示 怪异度 的值 \(x\) 均 没有实际意义，且 不代表同一个变量
可以理解成 占位符，关于 怪异度 的部分最后会讨论
-
新的点中 一对都都没匹配上
显然 此时 没匹配上的对数 \(j\) 多了一个（新增一对，没有匹配）
于是我们需要从 \(f_{i - 1, j - 1, x}\) 处转移
我们当前只考虑前 \(i\) 对点，也就是将 当前没匹配上（实际匹配 \(i - 1 \sim N\)）的均看作 一种情况
故 两者都没匹配上 的可能 只有一种，这里的贡献应当是 \(f_{i - 1, j - 1, x}\)
-
新的点中 匹配上了一对
显然 此时 没匹配上的对数 \(j\) 不变（新增一对，匹配一对），我们从 \(f_{i - 1, j, x}\) 处转移
而 匹配的这一对 有可能是 左部点 \(L_i\) 匹配到一个 \(R_1 \sim R_{i - 1}\) 中未被匹配的右部点，共 \(j\) 个
也可能是 右部点 \(R_i\) 匹配到一个 \(L_1 \sim L_{i - 1}\) 中未被匹配的左部点，共 \(j\) 个
还可能是 这一对点 \((L_i, R_i)\) 互相匹配，显然一共三种情况，有 \(2j + 1\) 种可能匹配
于是这里的贡献应当是 \((2j + 1)f_{i - 1, j, x}\)
-
新的点中 匹配上了两对
显然 此时 没匹配上的对数 \(j\) 少了一个（新增一对，匹配两对），我们从 \(f_{i - 1, j + 1, x}\) 处转移
显然 \(L_i\) 可以找 \(R_1 \sim R_i\) 中 未被匹配的点，共 \(j + 1\) 个
同时 \(R_i\) 可以找 \(L_1 \sim L_i\) 中 未被匹配的点，共 \(j + 1\) 个
当时想为什么这里是 \(j + 1\) 而不是 \(j\)，挺唐诗的
我们是从 前 \(i - 1\) 对点，还剩 \(j + 1\) 对未匹配的 \(f_{i - 1, j + 1, x}\) 处转移过来的
当然有 \(j + 1\) 种选择，而 \(f_{i, j, x}\) 只是表示 当前情况，与 能选择的种数无关
容易知道，\(L_i\) 与 \(R_i\) 的选择 互不干扰，于是最终将产生 \((j + 1) ^ 2\) 种 可能匹配
于是这里的贡献应当是 \((j + 1) ^ 2 f_{i - 1, j + 1, x}\)
加在一起，最终的式子就是 $f_{i, j, x} = f_{i - 1, j - 1, x} + (2j - 1) f_{i - 1, j, x} + (j - 1) ^ 2 f_{i - 1, j + 1, x} $
这时我们来考虑一直忽略的 怪异度 这一维，这里提供一种和 现行题解 不完全相同的理解方式
前面部分参考题解，我们给对 对应点 \((L_i, R_i)\) 之间 连线
那么 怪异度 就是 完美匹配 中 跨过连线 的 条数，这里可以参考 Tan_Wei_Ye 的 这篇题解
我们一直只考虑 前 \(i\) 对点的情况，也就是不要把 线 在一开始连完
只当枚举到 \(i\) 时，才考虑 \(L_i, R_i\) 的对应的线 产生的贡献，而此时有 \(j\) 对没匹配上
换言之就是 \(L_1 \sim L_i, R_1 \sim R_i\) 中 共有 \(2j\) 个点 最终 将匹配到 \(L_{i + 1} \sim L_N, R_{i + 1} \sim R_N\)
也就是有这 \(2j\) 个点 将会跨过 \(L_i, R_i\) 对应的线，于是产生 \(2j\) 的 怪异度
这时就可以 准确地描述 上面的转移了，我们每次一定增加 \(2j\) 的怪异度，最终方程如下
\[f_{i, j, k} = f_{i - 1, j - 1, k - 2j} + (2j + 1) f_{i - 1, j, k - 2j} + (j + 1) ^ 2 f_{i - 1, j + 1, k - 2j} \]根据我们对 怪异度 的理解可以发现，上面的分类讨论 与 此处怪异度的贡献 并无关系
故 不用担心 上面分类讨论时 忽略怪异度 而对正确性造成影响
枚举并转移即可，具体见代码
由于我们 怪异度 在转移过程中 不会减少（不会有 \(f_{i, j, k}\) 需要用到 \(f_{x, y, z} ~~ z>k\)）
故我们第三维转移只需要 终止在 需求的 \(K\) 即可，不需要转移到 理论怪异度上界 \(N ^ 2\)
#include <bits/stdc++.h>
const int MAXN = 55;
const int MOD = 1000000007;
using namespace std;
int F[MAXN][MAXN][MAXN * MAXN];
int N, K;
int main () {
cin >> N >> K, F[0][0][0] = 1;
for (int i = 1; i <= N; ++ i)
for (int j = 0; j <= i; ++ j)
for (int k = j * 2; k <= K; ++ k)
F[i][j][k] = (1ll * ((j << 1) + 1) * F[i - 1][j][k - (j << 1)] + 1ll * (j + 1) * (j + 1) * F[i - 1][j + 1][k - (j << 1)] + (j > 0) * F[i - 1][j - 1][k - (j << 1)]) % MOD;
cout << F[N][0][K] << endl;
return 0;
}