[atARC118E]Avoid Permutations

为了方便，记$S={(i,j)mid 1le i,jle n}$和$S_{all}={(i,j)mid 0le i,jle n+1}$

令$a_{i}$为给定的序列，其中$a_{i}=-1$的位置表示不限制该位置的值

对于排列$p$，用集合${(i,p_{i})}$来描述其，以下称集合$P$为合法排列集合，当且仅当$P_{0}subseteq Psubseteq S$、$|P|=n$且$P$中不存在两个坐标同行或同列

（$P_{0}$为初始确定的障碍所构成的集合，即$P_{0}={(i,a_{i})mid a_{i}ge 1}$）

对于一条路径，用其经过的坐标所构成的集合描述其，以下称集合$X$为合法路径集合，当且仅当$Xsubseteq S_{all}$且将$X$中所有元素从上到下、从左到右排序后，第一个元素为$(0,0)$、最后一个元素为$(n+1,n+1)$且相邻两个元素曼哈顿距离为1

不难发现，问题即统计$sum_{P为合法排列集合}sum_{X为合法路径集合}[Pcap X=empty]$

注意到$[Pcap X=empty]=sum_{P'subseteq Pcap X}(-1)^{|P'|}$，代入即$sum_{P为合法排列集合}sum_{X为合法路径集合}sum_{P'subseteq Pcap 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$列是否存在元素（$pin [0,3]$）的贡献和（每一对$(X,P')$的贡献为$(-1)^{|P'|}$）

（为了方便，关于$p$作如下定义：第$i$行存在元素当且仅当$pand 1=1$，第$j$列存在元素当且仅当$pand 2=2$）

考虑转移，即枚举$X$的下一个元素是$(i,j+1)$还是$(i+1,j)$，以及其是否要加入$P'$，具体即——
$$
f_{i,j,k,p}->f_{i+1,j,k,pand 2},f_{i,j+1,k,pand 1}\-f_{i,j,k,p}->f_{i+1,j,k+[a_{i+1} e j],3}(pand 2=0且(i+1,j)in S且(a_{i+1}=j或a_{i+1}=-1且forall 1le ile n,a_{i} e j))\
-f_{i,j,k,p}->f_{i,j+1,k+[a_{i} e j+1],3}(pand 1=0且(i,j+1)in S且(a_{i}=j+1或a_{i}=-1且forall 1le ile n,a_{i} e 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_{0le ile n}(n-i)!f_{n+1,n+1,i,0}$

时间复杂度为$o(n^{3})$，可以通过

#include<bits/stdc++.h>
using namespace std;
#define N 205
#define mod 998244353
int n,ans,fac[N],a[N],vis[N],f[N][N][N][4];
int main(){
    fac[0]=1;
    for(int i=1;i<N;i++)fac[i]=1LL*i*fac[i-1]%mod;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if (a[i]>0){
            vis[0]++;
            vis[a[i]]=1;
        }
    }
    f[0][0][vis[0]][0]=1;
    for(int i=0;i<=n+1;i++)
        for(int j=0;j<=n+1;j++)
            for(int k=0;k<=n;k++)
                for(int p=0;p<4;p++){
                    if (i<=n){
                        f[i+1][j][k][p&2]=(f[i+1][j][k][p&2]+f[i][j][k][p])%mod;
                        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;
                    }
                    if (j<=n){
                        f[i][j+1][k][p&1]=(f[i][j+1][k][p&1]+f[i][j][k][p])%mod;
                        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;
                    }
                }
    for(int i=0;i<=n;i++)ans=(ans+1LL*fac[n-i]*f[n+1][n+1][i][0])%mod;
    printf("%d",ans);
}