题面
定义一个 \(1 \sim n\) 的排列 \(p\) 的「怪异度」为
求「怪异度」为 \(k\) 的 \(1 \sim n\) 的排列数，答案对 \(10^9+7\) 取模。
题解
考虑转化计算怪异度的过程，我们将值 \(p_i\) 排列在左侧，将下标 \(i\) 排列在右侧，构成一个 \(n \times 2\) 的矩阵。将值和下标一一配对，定义配对一对元素的贡献为 \(\left\lvert p_i-i\right\rvert\)，求使总贡献为 \(m\) 的配对方案。注意，这里的配对要求必须是值和下标配对，换句话说就是这个矩阵不同列的元素配对。
定义 \(f_{i, j, k}\) 为前 \(i\) 行中有 \(j\) 对元素没有进行配对的情况下总贡献为 \(k\) 的方案数。
发现 \(k\) 的定义不便于维护，考虑转化总贡献的计算方法。在矩阵的每两行之间插入一个计数器，计数器的贡献值为经过这个计数器的配对的数量，可以看出配对的总贡献就是所有计数器的贡献和。发现当前计数器的贡献即前 \(i\) 行未配对元素的数量，证明可以考虑在前 \(i\) 行没有配对的元素一定会和第 \(i + 1 \sim n\) 行的元素配对，那么一定会经过矩阵第 \(i\) 行和第 \(i + 1\) 行之间的计数器并产生贡献，故可以进行转移。
\(f\) 的转移可以考虑在当前矩阵的基础上新增了一行，考虑这一行会产生几个配对，不难发现这一行两个元素可以产生的配对数量为 \(0, 1, 2\)，考虑枚举这三种情况进行转移。
配对 \(0\) 对
在前 \(i\) 行有 \(j\) 对没有进行配对且第 \(i\) 行的两个元素均为配对，所以该状态可以从 \(f_{i - 1, j - 1, k - 2j}\) 转移。
配对 \(1\) 对
考虑两种情况：
-
第 \(i\) 行的元素与前 \(i - 1\) 行未配对的元素进行配对，单个元素的方案为 \(j\)，因为有两个元素，所以这部分的方案为 \(2j\)；
-
第 \(i\) 行的两个元素进行配对，方案数为 \(1\)。
因为第 \(i\) 行的元素不会产生新的未配对数量，所以这两种情况均从 \(f_{i - 1, j, k - 2j}\) 中转移而来。
配对 \(2\) 对
考虑前 \(i - 1\) 行有多少对元素未配对，因为第 \(i\) 行的两个元素均与前 \(i - 1\) 行的元素进行了配对，所以消除了前 \(i - 1\) 行的一对未配对元素，因而前 \(i - 1\) 行有 \(j + 1\) 对未配对元素，故该状态从 \(f_{i - 1, j + 1, k - 2j}\) 转移。
对于第 \(i\) 行的每个元素，均可以与另一列前 \(i - 1\) 行的 \(j + 1\) 个未配对元素进行独立配对，故方案数为 \(\left(j + 1\right)^2\)。
根据加法原理，可以得到总的转移式
初始状态为 \(f_{0, 0, 0} = 1\)，根据该转移式递推即可以 \(\mathcal{O}(n^4)\) 的复杂度通过本题。
Code
#include <bits/stdc++.h>
typedef long long valueType;
typedef std::vector<valueType> ValueVector;
constexpr valueType MAXN = 55;
constexpr valueType MOD = 1e9 + 7;
bool ModOperSafeModOption = true;
template<typename T1, typename T2, typename T3 = valueType>
void Inc(T1 &a, T2 b, const T3 &mod = MOD) {
if (ModOperSafeModOption) {
a %= MOD;
b %= MOD;
if (a < 0)
a += MOD;
if (b < 0)
b += MOD;
}
a = a + b;
if (a >= mod)
a -= mod;
}
template<typename T1, typename T2, typename T3 = valueType>
void Dec(T1 &a, T2 b, const T3 &mod = MOD) {
if (ModOperSafeModOption) {
a %= MOD;
b %= MOD;
if (a < 0)
a += MOD;
if (b < 0)
b += MOD;
}
a = a - b;
if (a < 0)
a += mod;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 sum(T1 a, T2 b, const T3 &mod = MOD) {
if (ModOperSafeModOption) {
a %= MOD;
b %= MOD;
if (a < 0)
a += MOD;
if (b < 0)
b += MOD;
}
return a + b >= mod ? a + b - mod : a + b;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 sub(T1 a, T2 b, const T3 &mod = MOD) {
if (ModOperSafeModOption) {
a %= MOD;
b %= MOD;
if (a < 0)
a += MOD;
if (b < 0)
b += MOD;
}
return a - b < 0 ? a - b + mod : a - b;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 mul(T1 a, T2 b, const T3 &mod = MOD) {
if (ModOperSafeModOption) {
a %= MOD;
b %= MOD;
if (a < 0)
a += MOD;
if (b < 0)
b += MOD;
}
return (long long) a * b % MOD;
}
template<typename T1, typename T2, typename T3 = valueType>
void Mul(T1 &a, T2 b, const T3 &mod = MOD) {
if (ModOperSafeModOption) {
a %= MOD;
b %= MOD;
if (a < 0)
a += MOD;
if (b < 0)
b += MOD;
}
a = (long long) a * b % MOD;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 pow(T1 a, T2 b, const T3 &mod = MOD) {
if (ModOperSafeModOption) {
a %= MOD;
b %= MOD - 1;
if (a < 0)
a += MOD;
if (b < 0)
b += MOD - 1;
}
T1 result = 1;
while (b > 0) {
if (b & 1)
Mul(result, a, mod);
Mul(a, a, mod);
b = b >> 1;
}
return result;
}
std::array<std::array<std::array<valueType, MAXN * MAXN>, MAXN>, MAXN> dp;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
valueType N, M;
std::cin >> N >> M;
if (M & 1) {
std::cout << 0 << std::endl;
return 0;
}
dp[0][0][0] = 1;
for (valueType i = 1; i <= N; ++i) {
for (valueType j = 0; j <= i; ++j) {
for (valueType k = 2 * j; k <= M; k += 2) {
dp[i][j][k] = 0;
Inc(dp[i][j][k], mul((j + 1) * (j + 1), dp[i - 1][j + 1][k - 2 * j]));
Inc(dp[i][j][k], mul(2 * j + 1, dp[i - 1][j][k - 2 * j]));
if (j >= 1) {
Inc(dp[i][j][k], dp[i - 1][j - 1][k - 2 * j]);
}
}
}
}
std::cout << dp[N][0][M] << std::endl;
return 0;
}