题解：P9385 [THUPC 2023 决赛] 阴阳阵法
_Lexora
·
·
题解
这是一道妙妙的计数 DP。
首先根据题目性质，该图是一个有向基环内向树森林。
由于每个环上的黑点数量和白点数量的乘积是偶数，所以方案要么是一奇一偶，要么两个偶数。有三种情况，不太好处理，于是我们考虑容斥计算白点和黑点数量均为奇数的方案数。下面我们称其为奇奇环。
考虑计算 f_{i,j} 表示用 i 个白点和 j 个黑点构建出若干个奇奇环的方案数（带容斥系数）。发现需要辅助数组 c_{i,j} 表示用 i 个白点和 j 个黑点构建出一个奇奇环的方案数。易知
c_{i,j}=(i-1)! \binom{i}{j}j!
::::warning[解释]
即为 i 个白点先排成环（圆排列方案数），由于黑点只能连向白点，故只能在 i 个白点的空隙中选取 j 个放黑点，再乘上黑点的排列数。
::::
令 \operatorname{ODD} 为奇数的集合，则
f_{i,j}=-\sum_{a,b \in \operatorname{ODD}} \binom{i}{a} \binom{j-1}{b-1} c_{a,b}f_{i-a,j-b}
且 f_{0,0}=1。
::::warning[解释]
第二项组合数是 \binom{j-1}{b-1} 是因为一个环可能被重复算 b 次，故我们钦定编号最小的点作为环的起始点。在这之后，组合系数再乘上 \binom{i}{a} 即可，因为已经钦定了环头，接下来的每一种选法都对应着不同的环。
| 这里的负号即为容斥系数，可以理解为有一个奇奇环容斥系数为 -1，两个为 1，依此类推。 |
| 将转移系数都拆开，并令 x=i-a, y=j-b，可得 |
| $$ |
| f{i,j}=-\sum{x,y}\frac{i!}{x!}\cdot\frac{(j-1)!}{y!}\cdot\binom{i-x-1}{j-y-1}f_{x,y} |
| $$ |
注意到 x\equiv i-1\,(\operatorname{mod}\,2),y\equiv j-1\,(\operatorname{mod}\,2)，转移式的下标和奇偶性有很大关系，于是我们考虑定义 g_{i,j}^{(\alpha,\beta)} 表示当对于 i,j 的 x,y 奇偶性分别为 \alpha,\beta 时，对 f_{i,j} 转移中的贡献（x<i,y<j，每个 g 的第 0 行和第 0 列都为 0）。
接下来我们固定一对 \alpha,\beta，省略 g 的上标。
考虑这个东西怎么转移，有两种视角：
::::success[组合恒等式]
根据 Pascal 组合恒等式，并对比系数，易知 g_{i,j} 由 i \cdot g_{i-1,j},i(j-1)g_{i-1,j-1} 贡献而来。
除此之外，由于考虑到 i,j 时，新增了状态 (x-1,y-1)，故我们需要加入它的贡献，也即 i \cdot f_{i-1,j-1} \cdot [i-1\equiv \alpha\,(\operatorname{mod}\,2),j-1\equiv \beta\,(\operatorname{mod}\,2)]。
::::warning[解释]
::::
::::success[组合意义]
组合系数 $\binom{i-x-1}{j-y-1}$ 可以理解为在二维平面上从 $(x-y, y+1)$ 走到 $(i-j, j)$ 的方案数，且每一步只能往上或往右走。因此可以知道 $g_{i,j}$ 是从 $g_{i-1,j}$ 和 $g_{i-1,j-1}$ 转移过来的，同理对比系数即可，实际上代替了 Pascal 组合恒等式。其余部分同第一种方法。
::::
至此，所有需要处理的数组转移已完成，考虑答案，即为
$$
\sum_{i=0}^n \sum_{j=0}^m \binom{n}{i}\binom{m}{j}f_{i,j}(n+m)^{n-i}n^{m-j}
$$
::::warning[解释]
即把限制形成环的方案和自由点的方案相乘再累加，由于黑点只能指向白点，所以自由黑点的方案数是 $n^{m-j}$；而自由白点可以指向任意点，故其方案数为 $(n+m)^{n-i}$。
::::
::::success[Code]
```cpp
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 2010;
int n, m, P, f[N][N], g[2][4][N], C[N][N];
void add(int &x, int y) { if ((x += y) >= P) x -= P; }
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> P, f[0][0] = 1;
int k = max(n, m);
for (int i = 0; i <= k; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++)
add(C[i][j], C[i - 1][j]), add(C[i][j], C[i - 1][j - 1]);
}
for (int i = 1, o = 1; i <= n; i++, o ^= 1) {
for (int j = 1; j <= m; j++) {
for (int a = 0; a <= 1; a++) {
for (int b = 0; b <= 1; b++) {
int s = a << 1 | b;
g[o][s][j] = 0;
add(g[o][s][j], 1LL * i * g[o ^ 1][s][j] % P);
add(g[o][s][j], 1LL * i * (j - 1) % P * g[o ^ 1][s][j - 1] % P);
if ((i & 1 ^ 1) == a && (j & 1 ^ 1) == b) add(g[o][s][j], 1LL * i * f[i - 1][j - 1] % P);
}
}
int s = ((i & 1 ^ 1) << 1) | ((j & 1 ^ 1) & 1);
f[i][j] = g[o][s][j] ? P - g[o][s][j] : 0;
}
}
int ans = 0;
for (int i = n, p = 1; i >= 0; i--, p = 1LL * p * (n + m) % P)
for (int j = m, q = 1; j >= 0; j--, q = 1LL * q * n % P)
add(ans, 1LL * C[n][i] * C[m][j] % P * f[i][j] % P * p % P * q % P);
cout << ans << "\n";
return 0;
}
```
::::