\(\text{[AGC022F] Checkers 题解}\)
近一段时间以来做过的最抽象的题目。
首先我们发现合并次数是 \(n-1\) 次，因此我们可以把这个东西抽象成一棵树来处理。具体地，对于 \(A\) 关于 \(B\) 对称，令 \(B\) 对 \(A\) 连边。那么答案实际上就是根的值。发现答案一定形如 \(\sum c_i2^{d_i}\) 的形式，其中 \(c\in\{-1,1\}\)。寻找影响 \(c\) 的因素，不难发现影响它的有自己的一坨儿子的取反和在自己的祖先处不停地取反。考虑每个位置的 \(c\) 是困难的，注意到叶子节点的 \(c\) 恒定，考虑维护父子间 \(c\) 的关系（相等或不相等）。那么从下往上就变得困难，我们从上往下维护，维护每个点最终是否与其父亲的正负性相同。那么下边的 \(c_i\) 都表示与父亲的关系。
下面我们要发现一些性质，记 \(son_i\) 表示 \(i\) 的儿子个数：
- 当且仅当 \(son_i\) 为奇数时，\(c_i\) 取反。
这个东西的理解是你手玩一下，列出从左往右变化的式子就能发现。
- 儿子间相邻位置 \(c_i\) 不同
这里的不同指的是不考虑儿子子树内的 \(c\)，那么每一次变换时都会将上一个取反，后面会捆在一起取反，因此得到这个结论。
那么我们现在可以开始 dp 了。我们设 \(dp_{i,j}\) 表示考虑前 \(i\) 个数，最外层有 \(j\) 个 \(son_x\) 为奇数的方案数。那么枚举下一层的节点个数为 \(k(k\ge j)\)，那么考虑到满足儿子个数为奇数的时候这个点会满足儿子 \(c\) 的取值和父亲相等的会比不相等的多一个，那么会有下一层与父亲 \(c\) 相同的个数为 \(t=\frac{k-j}2\)，要满足 \(2|k-j\)。
现在的问题是考虑要解决此时扩展的节点中有多少个节点满足儿子个数为奇数。先枚举实际情况下与父亲 \(c\) 相同的点的个数 \(p\)，这个实际情况下指的是考虑儿子内部转移的情形，那么能得到的下一层中儿子个数为奇数的点的数量要 \(\ge|t-p|\)，原因是考虑儿子个数为奇数可以改变当前 \(c\) 的奇偶性，那么按照 \(t,p\) 的大小分类讨论一下可以得到这个东西的正确性。但是这里我们只向 \(|t-p|\) 而不是 \(|t-p|+2r\) 转移，原因是形态不同的树权值有可能相同，那么我们只统计个数最小的情形是有正确性的。
那么给出转移式：
初始状态是 \(dp_{1,0}=dp_{1,1}=n\)，答案是 \(dp_{n,0}\)，复杂度是 \(O(n^4)\)。
代码：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 55, mod = 1e9 + 7;
int n;
int C[N][N], dp[N][N];
void add(int &x, int y) {x = (x + y) % mod;
}
signed main() {cin >> n;C[0][0] = 1;for (int i = 1; i <= n; i++)for (int j = 0; j <= i; j++)C[i][j] = ((j == 0 ? 0 : C[i - 1][j - 1]) + C[i - 1][j]) % mod;dp[1][0] = dp[1][1] = n;for (int i = 1; i <= n; i++)for (int j = 0; j <= i; j++)for (int k = j ? j : 2; i + k <= n; k += 2) {int t = (k - j) >> 1;for (int p = 0; p <= k; p++) add(dp[i + k][abs(t - p)], dp[i][j] * C[n - i][k] % mod * C[k][p] % mod);}cout << dp[n][0] <<'\n';return 0;
}