为了方便，记$S=\{(i,j)\mid 1\le i,j\le n\}$和$S_{all}=\{(i,j)\mid 0\le i,j\le n+1\}$
令$a_{i}$为给定的序列，其中$a_{i}=-1$的位置表示不限制该位置的值
对于排列$p$，用集合$\{(i,p_{i})\}$来描述其，以下称集合$P$为合法排列集合，当且仅当$P_{0}\subseteq P\subseteq S$、$|P|=n$且$P$中不存在两个坐标同行或同列
（$P_{0}$为初始确定的障碍所构成的集合，即$P_{0}=\{(i,a_{i})\mid a_{i}\ge 1\}$）
对于一条路径，用其经过的坐标所构成的集合描述其，以下称集合$X$为合法路径集合，当且仅当$X\subseteq S_{all}$且将$X$中所有元素从上到下、从左到右排序后，第一个元素为$(0,0)$、最后一个元素为$(n+1,n+1)$且相邻两个元素曼哈顿距离为1
不难发现，问题即统计$\sum_{P为合法排列集合}\sum_{X为合法路径集合}[P\cap X=\empty]$
注意到$[P\cap X=\empty]=\sum_{P‘\subseteq P\cap X}(-1)^{|P‘|}$，代入即$\sum_{P为合法排列集合}\sum_{X为合法路径集合}\sum_{P‘\subseteq P\cap X}(-1)^{|P‘|}$
交换枚举顺序，即$\sum_{X为合法路径集合}\sum_{P‘\subseteq X}(-1)^{|P‘|}\sum_{P为合法排列集合,P‘\subseteq P}1$
当$P‘$满足$P‘\subseteq S$且$P‘\cup P_{0}$中不存在两个坐标同行或同列，此时最后$P$的方案数即$(n-|P‘\cup P_{0}|)!$
下面，对$(X,P‘)$进行dp，即令$f_{i,j,k,p}$表示当前走到$(i,j)$，当前$|P‘\cup P_{0}|=k$且$|P‘\cup P_{0}|$在第$i$行和第$j$列是否存在元素（$p\in [0,3]$）的贡献和（每一对$(X,P‘)$的贡献为$(-1)^{|P‘|}$）
（为了方便，关于$p$作如下定义：第$i$行存在元素当且仅当$p\and 1=1$，第$j$列存在元素当且仅当$p\and 2=2$）
考虑转移，即枚举$X$的下一个元素是$(i,j+1)$还是$(i+1,j)$，以及其是否要加入$P‘$，具体即——
$$
f_{i,j,k,p}->f_{i+1,j,k,p\and 2},f_{i,j+1,k,p\and 1}\\-f_{i,j,k,p}->f_{i+1,j,k+[a_{i+1}\ne j],3}(p\and 2=0且(i+1,j)\in S且(a_{i+1}=j或a_{i+1}=-1且\forall 1\le i\le n,a_{i}\ne j))\\
-f_{i,j,k,p}->f_{i,j+1,k+[a_{i}\ne j+1],3}(p\and 1=0且(i,j+1)\in S且(a_{i}=j+1或a_{i}=-1且\forall 1\le i\le n,a_{i}\ne j+1))
$$
（$xf_{S_{1}}->f_{S_{2}}$表示令$f_{S_{2}}+=xf_{S_{1}}$）
初始状态为$f_{0,0,\sum_{i=1}^{n}[a_{i}\ge 1],0}=1$，答案为$\sum_{0\le i\le n}(n-i)!f_{n+1,n+1,i,0}$
时间复杂度为$o(n^{3})$，可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 205 4 #define mod 998244353 5 int n,ans,fac[N],a[N],vis[N],f[N][N][N][4]; 6 int main(){ 7 fac[0]=1; 8 for(int i=1;i<N;i++)fac[i]=1LL*i*fac[i-1]%mod; 9 scanf("%d",&n); 10 for(int i=1;i<=n;i++){ 11 scanf("%d",&a[i]); 12 if (a[i]>0){ 13 vis[0]++; 14 vis[a[i]]=1; 15 } 16 } 17 f[0][0][vis[0]][0]=1; 18 for(int i=0;i<=n+1;i++) 19 for(int j=0;j<=n+1;j++) 20 for(int k=0;k<=n;k++) 21 for(int p=0;p<4;p++){ 22 if (i<=n){ 23 f[i+1][j][k][p&2]=(f[i+1][j][k][p&2]+f[i][j][k][p])%mod; 24 if ((!(p&2))&&(i<n)&&(j>=1)&&(j<=n)&&((a[i+1]==j)||(a[i+1]==-1)&&(!vis[j])))f[i+1][j][k+(a[i+1]!=j)][3]=(f[i+1][j][k+(a[i+1]!=j)][3]+mod-f[i][j][k][p])%mod; 25 } 26 if (j<=n){ 27 f[i][j+1][k][p&1]=(f[i][j+1][k][p&1]+f[i][j][k][p])%mod; 28 if ((!(p&1))&&(j<n)&&(i>=1)&&(i<=n)&&((a[i]==j+1)||(a[i]==-1)&&(!vis[j+1])))f[i][j+1][k+(a[i]!=j+1)][3]=(f[i][j+1][k+(a[i]!=j+1)][3]+mod-f[i][j][k][p])%mod; 29 } 30 } 31 for(int i=0;i<=n;i++)ans=(ans+1LL*fac[n-i]*f[n+1][n+1][i][0])%mod; 32 printf("%d",ans); 33 }
原文：https://www.cnblogs.com/PYWBKTDA/p/14780655.html
