题目大意
定义一个 \(1 \sim n\) 的排列 \(p\) 的「怪异度」为
\[\sum_{i=1}^n|p_i-i| \]求「怪异度」为 \(m\) 的 \(1 \sim n\) 的排列数，答案对 \(10^9+7\) 取模。
思路
考虑把 \(p_i\) 和 \(i\) 看作小球与盒子，方便题意理解。
考虑球与盒子的匹配。
假设球在左侧，盒子在右侧，他们构成了一个二分图。
从上到下顺着排列每组球与盒子，球与盒子之间有一条横线。
我们发现，假设第 \(i\) 个盒子与 \(j\) 个球相连，他们之间的距离为 \(\left\lvert i - j \right\rvert\)，他们产生的贡献相当于从 \(i\) 到 \(j\) 的连线穿过的横线的数量。
那么我们考虑状态如何设计，记 \(dp_{i,j,k}\) 表示已经匹配了前 \(i\) 行，有 \(j\) 组球与盒子未匹配，怪异度为 \(k\) 的方案数。
那么初始值为 \(dp_{0,0,0}=1\)，答案为 \(dp_{n,0,m}\) 表示匹配了前 \(i\) 行，没有球与盒子未匹配，怪异度为 \(m\) 的方案数。
考虑转移，对于一行，有一个球和一个盒子，可以匹配 \(0,1,2\) 组三种可能，那么就分这三种情况进行转移。
匹配 \(0\) 组
都不匹配的话，应该是 \(dp_{i-1,j-1,k-2j}\)。
考虑第二维为什么是从 \(j-1\) 个未匹配组转移过来。
先考虑我们匹配 \(1\) 组的情况，我们新加入了 \(1\) 组，即第 \(i\) 行的球与盒子，又匹配了 \(1\) 组，那么新的没有匹配的组数没有发生变化，即第二维从 \(j\) 转移到 \(j\)。
那么匹配 \(2\) 组的情况，相比于匹配 \(1\) 组的情况多匹配了一组，所以要从 \(j + 1\) 转移到 \(j\)；同理，匹配 \(0\) 组的情况就要从 \(j-1\) 转移到 \(j\)。
再考虑第三维。原本前面那些没有被匹配的盒子与球是可能被匹配到第 \(i\) 行及以后的，但是现在我们考虑的转移第 \(i\) 行并没有匹配这 \(j\) 组盒子与球。
那么这 \(j\) 组盒子与球只能匹配到第 \(i +1\) 行及以后，那么相等于我们前面的 \(j\) 组球与盒子又需要多穿过一条横线，那么总共 \(2j\) 个物品，就使得怪异值增加了 \(2j\)，所以从 \(k-2j\) 转移过来。
匹配 \(1\) 组
将第 \(i\) 个球与前面的 \(i-1\) 行未被匹配的 \(j\) 个盒子进行匹配，有 \(j\) 种选择，每种选择的方案数为 \(j \times dp_{i-1,j,k-2j}\)。
用第 \(i\) 个盒子去匹配球的方案数同理。
第 \(i\) 个球连第 \(i\) 个盒子的方案数单独处理，为 \(dp_{i-1,j,k-2j}\)。
匹配 \(2\) 组
如果要匹配两组，那么第 \(i\) 行的球与盒子之间不能相互选择。
第 \(i\) 行的球与前 \(i-1\) 行的 \(j+1\) 个未匹配的盒子转移过来，盒子同理，根据乘法原理，有 \((j + 1)^2dp_{i-1,j+1,k-2j}\) 种方案。
状态转移方程
\[dp_{i,j,k}=j \times dp_{i-1,j,k-2j}+j \times dp_{i-1,j,k-2j}+dp_{i-1,j,k-2j}+(j+1)^2 \times dp_{i-1,j+1,k-2j}+dp_{i-1,j-1,k-2j} \]Code
#include <bits/stdc++.h>
using namespace std;
typedef long long MainType;
const int N = 55;
const int Mod = 1e9 + 7;
int n,m;
MainType dp[N][N][N * N];
// dp[i][j][k]
// 对于前 i 组有 j 组没有配对，怪异度为 k 的方案数
int main() {
#ifdef ONLINE_JUDGE == 1
freopen("genshin.in","r",stdin);
freopen("genshin.out","w",stdout);
#endif
cin >> n >> m;
dp[0][0][0] = 1;
for(int i = 1;i <= n; i++) {
for(int j = 0;j <= i; j++) {
for(int k = j * 2;k <= m; k++) {
if(j < 1)
dp[i][j][k] = (dp[i - 1][j + 1][k - j * 2] * (j + 1) % Mod * (j + 1) % Mod + dp[i - 1][j][k - j * 2] * (j * 2 + 1) % Mod) % Mod;
else
dp[i][j][k] = (dp[i - 1][j + 1][k - j * 2] * (j + 1) % Mod * (j + 1) % Mod + dp[i - 1][j][k - j * 2] * (j * 2 + 1) % Mod + dp[i - 1][j - 1][k - j * 2] % Mod) % Mod;
}
}
}
cout << dp[n][0][m] % Mod;
#ifdef ONLINE_JUDGE == 1
fclose(stdin);
fclose(stdout);
#endif
return 0;
}