题解：P9385 [THUPC 2023 决赛] 阴阳阵法

· · 题解

很厉害的题。 首先你看到这个白黑点个数乘积为偶数，那就是都不为奇数。显然不合法的情况比合法的更简单，所以可以尝试容斥。

考虑这样一个过程：刚开始有 n 个白点，给他们随便定出边，方案数是 (n+m)^n。然后按编号从小到大加入黑点，让这个黑点随便连向一个白点。如果加入某个黑点后出现了一个不合法的环，减去这种方案。

如何减？假如这个不合法的环上有 x 个白点和 y 个黑点，我们把这个环之间的边断了，变成一个子问题：有 n-x 个白点和 m-y 个黑点，这 n+m-x-y 个点可以内部连边也可以连向那 x+y 个孤点，合法的方案数。这个方案数就是我们要减去的。这个就是我们 dp 的状态 f_{i,j}，其中 i=n-x,j=m-y。

显然 f_{n,m} 是最终答案。求 f_{i,j} 我们可以类似上述过程，枚举一个不合法的环，随便分配一下编号（注意编号最大的黑点一定在环内），这个是 O(n^2m^2) 的。

其实我们并不关心一个环它具体的黑白点个数，我们只关心是否都是奇数，那其实我们可以考虑钦定某个起点，逐个加点，钦定编号。我们把那个编号最大的黑点放在最后加入，因为它不需要分配编号，且放在前面会影响其他黑点编号的分配。所以起点应该是一个白点，也就是编号最大的黑点连向的点。

那我们定义 g_{i,j,0/1,0/1,0/1} 表示正在加入一个环满足条件的方案数。五个参数分别代表：目前整个图上的白黑点数、环上白黑点的个数的奇偶性、目前链尾点的颜色。转移显然。

#include<bits/stdc++.h>
using namespace std;
const int N=2005;
int n,m,mod,f[N][N],g[N][N][2][2][2];
inline void Mod(int &x){x>=mod?x-=mod:0;}
int main(){
    cin>>n>>m>>mod;
    for(int i=0;i<=n;++i){
        for(int j=0;j<=m;++j){
            if(j) f[i][j]=(1ll*f[i][j-1]*n+mod-g[i][j-1][1][0][0])%mod;
            else f[i][0]=(i?1ll*f[i-1][0]*(n+m)%mod:1);
            Mod(g[i+1][j][1][0][0]+=1ll*f[i][j]*(i+1)%mod);
            for(int x=0;x<=1;++x)
            for(int y=0;y<=1;++y){
                Mod(g[i+1][j][!x][y][0]+=1ll*(g[i][j][x][y][0]+g[i][j][x][y][1])*(i+1)%mod);
                Mod(g[i][j+1][x][!y][1]+=1ll*g[i][j][x][y][0]*(j+1)%mod);
            }
        }
    }
    cout<<f[n][m];
    return 0;
}