526互联

Atcoder Regular Contest 118 E - Avoid Permutations（容斥+DP）

发布时间 2023-04-19 17:35:03作者: tzc_wk

挺套路的 DP。

第一步是显然的：转换贡献体，DP 一条从 \((0,0)\) 到 \((n+1,n+1)\) 的路径，然后计算有多少个排列满足这条路径不经过任何一个 \((i,p_i)\)。

正着统计肯定不好求，考虑容斥。即我们钦定一些路径上的点，满足这些点必须对应某个 \((i,p_i)\)，然后计算有多少个 \(p\) 符合这个条件，乘以 \((-1)^{\text{钦定的点的个数}}\) 统计入答案。显然如果你钦定的点与已经确定的点的横、纵坐标分别两两不同，那么符合条件的 \(p\) 的个数就是 \((\text{总的 -1 的个数}-\text{你钦定的点的个数})!\)。并且由于我们的路径只能向右或向上，因此判断一个新加入的点的横纵坐标是否与已有的点相同，就只用看当前行和当前列是否有点被钦定。

这样思路就出来了：\(dp_{x,y,k,a,b}\) 表示当前在 \((x,y)\)，钦定了 \(k\) 个点，当前行是否有点被钦定的状态为 \(a\)，当前列是否有点被钦定的状态为 \(b\)。转移是 simple 的。时间复杂度 \(O(n^3)\)。

#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
int n,a[205],dp[205][205][205][2][2],m,fac[205],res;
bool v[205][205],R[205],C[205];
void add(int &x,int v){((x+=v)>=MOD)&&(x-=MOD);}
void sub(int &x,int v){((x-=v)<0)&&(x+=MOD);}
int main(){
	scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);m=n;
	for(int i=1;i<=n;i++)if(~a[i])v[i][a[i]]=R[i]=C[a[i]]=1,m--;
	for(int i=(fac[0]=1);i<=n;i++)fac[i]=1ll*fac[i-1]*i%MOD;
	dp[0][0][0][1][1]=1;
	for(int i=0;i<=n+1;i++)for(int j=0;j<=n+1;j++)for(int k=0;k<=m;k++)
		for(int a=0;a<2;a++)for(int b=0;b<2;b++)if(dp[i][j][k][a][b]){
			int V=dp[i][j][k][a][b];
			if(i<n+1&&!v[i+1][j])add(dp[i+1][j][k][R[i+1]][b],V);
			if(j<n+1&&!v[i][j+1])add(dp[i][j+1][k][a][C[j+1]],V);
			if(!a&&!b&&i<n+1&&!v[i+1][j])sub(dp[i+1][j][k+1][R[i+1]][1],V);
			if(!a&&!b&&j<n+1&&!v[i][j+1])sub(dp[i][j+1][k+1][1][C[j+1]],V);
		}
	for(int k=0;k<=m;k++)res=(res+1ll*fac[m-k]*dp[n+1][n+1][k][0][0])%MOD;
	printf("%d\n",res);
}