ABC134F 题解
传送门
建议先看其他题解，看不懂再来看我的QWQ，仅作补充或解释。
显然是一个
考虑转移。对于编号为
-
这两个互相配对。
-
当前盒子装之前没配对的小球，当前小球暂且保留。
-
当前盒子暂且保留，当前小球装入之前没配对的盒子。
-
当前盒子装之前没配对的小球，当前小球装入之前没配对的盒子。
-
当前盒子和小球都暂且保留。
然后就会出现当前最难以解决的一个问题：
只知道之前有几个盒子没配对，怎么知道是哪几个？如果不知道怎么转移 k？
显然，如果
但是，尚未匹配，怎么知道贡献？
我想提及一个大多数题解都一笔带过的方法：增量贡献。
假设 1 号盒子和 1 号小球不匹配，那么 1 号盒子以后可能与其他号小球匹配，1 号小球同理。
在所有的匹配可能中，因为 1 号盒子和 1 号小球不匹配而对整体怪异度造成的最小贡献是 2，即 1 号盒子与 2 号小球匹配，2 号盒子与 1 号小球匹配的情况。
我们可以先把这个大小为 2 的最小贡献保存下来，即暂且认为最终匹配情况就是上文所说的那种情况，如果情况有变，就再更新贡献。
如果真是假设的情况，那么匹配时不需要再计算贡献，因为之前已经算好了。
什么时候“情况有变”？那当然是 2 号盒子不跟 1 号小球配对，或者 2 号小球不跟 1 号盒子配对啊。
如果 2 号盒子不跟 1 号小球配对而跟 2 号小球配对，我们就又暂且认为 1 号小球会跟 3 号小球配对，这时贡献只会增加 1，对 1 号盒子也同理。
如果 2 号盒子既不跟 1 号小球配对，也不跟 2 号小球配对，那我们就也暂且认为 1,2 号盒子都与 3 号小球配对，此时 2 号盒子产生 1 的贡献，1 号盒子的贡献加 1。
也就是说，对于
这样是不是好转移多了？来试试，对于上面的几种情况：
- 这一对盒子和小球不产生贡献，但是之前的所有假设作废，要重新暂且认为之前没配对的盒子/小球与编号为
i+2 的小球/盒子配对，贡献会在原来的基础上增加2\times j 。
配个图说明，左边是盒子右边是小球，假设虚线是假设的边，实线是确定的边，红色虚线是作废的假设，当前考虑到第 3 组盒子小球。
如果 1 号、2 号小球和盒子都不匹配，是这样的：
他们都暂且认为与 3 号盒子/小球匹配，此时贡献为 6。
转移后，是这样的：
- 之前没配对的盒子的假设全部作废，除了选中的小球，其他之前没配对的小球的假设也作废，并且新增一个当前小球的假设。综合起来，贡献还是比之前多了
2\times j 。
-
由对称性可知，其实和 2 是一样的，图不配了。
-
- 所有盒子和小球的假设都作废，并且新增一对假设，贡献多
2\times(j+1) 。
代码很容易就写出来了，记得在转移的时候乘上可以选择的种类数。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll P = 1000000007;
ll n, K, dp[55][55][55 * 55];
void add(ll& x, ll y) {
x = (x + y) % P;
}
int main() {
cin >> n >> K;
dp[1][0][0] = dp[1][1][2] = 1;
for (ll i = 1; i < n; i++) {
for (ll j = 0; j <= i; j++) {
for (ll k = 0; k <= n * n; k++) {
add(dp[i + 1][j][k + 2 * j], dp[i][j][k]); // 情况 1
if (j) {
add(dp[i + 1][j][k + 2 * j], j * dp[i][j][k] * 2); // 情况 2,3
add(dp[i + 1][j - 1][k + 2 * (j - 1)], j * j * dp[i][j][k]); // 情况 4
}
add(dp[i + 1][j + 1][k + 2 * (j + 1)], dp[i][j][k]); // 情况 5
}
}
}
cout << dp[n][0][K] << endl;
return 0;
}