ARC118E Avoid Permutations 题解

Coffee_zzz · 2025-11-10 12:20:19 · 题解

直接做有点困难，因此考虑钦定一些尚未确定的障碍点在路径上。设被钦定的障碍点的集合为 T 时，满足条件的路径数为 c(T)，则根据容斥原理可知答案可以表示为 \sum_{T} (-1)^{|T|} c(T)。

设 f_{i,j,k,0/1,0/1} 表示，考虑到第 i 行第 j 列的格子，此时一共钦定了 k 个障碍点，第 i 行没有 / 有障碍点，第 j 列没有 / 有障碍点时的方案数。初始时 f_{0,0,0,1,1}=1。

设 x_i=0/1 表示第 i 行没有 / 有确定的障碍点，y_j=0/1 表示第 j 列没有 / 有确定的障碍点。对于 f_{i,j,k,a,b}，考虑转移：

• 如果 (i,j) 处有障碍点，则不做转移；
• 如果 (i,j) 处没有障碍点：
  • 如果 i \le n：
  • 不在 (i,j) 处钦定障碍点，f_{i+1,j,k,x_{i+1},b} \leftarrow f_{i+1,j,k,x_{i+1},b}+f_{i,j,k,a,b}。
  • 如果 a=0 且 b=0：在 (i,j) 处钦定障碍点，f_{i+1,j,k+1,x_{i+1},1} \leftarrow f_{i+1,j,k+1,x_{i+1},1}+f_{i,j,k,a,b}。
  • 如果 j \le n：
  • 不在 (i,j) 处钦定障碍点，f_{i,j+1,k,a,y_{j+1}} \leftarrow f_{i,j+1,k,a,y_{j+1}}+f_{i,j,k,a,b}。
  • 如果 a=0 且 b=0：在 (i,j) 处钦定障碍点，f_{i,j+1,k+1,1,y_{j+1}} \leftarrow f_{i,j+1,k+1,1,y_{j+1}}+f_{i,j,k,a,b}。

设 m 表示初始时 -1 的数量，答案即为：

其中乘 (m-k)! 是因为没有被钦定的 p 可以在剩余的 (m-k) 个位置任意排列。

时间复杂度 \mathcal O(n^3)。

const int N=205,mod=998244353;
int n,m,a[N],fac[N],f[N][N][N][2][2],ans;
bool vis[N][N],x[N],y[N];
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
void solve(){
    cin>>n,fac[0]=1,f[0][0][0][1][1]=1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]!=-1) vis[i][a[i]]=1,x[i]=1,y[a[i]]=1;
        else m++;
    }
    for(int i=1;i<=m;i++) fac[i]=1ll*fac[i-1]*i%mod;
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=n+1;j++){
            if(vis[i][j]) continue;
            for(int k=0;k<=min(i,j);k++){
                for(int a=0;a<=1;a++){
                    for(int b=0;b<=1;b++){
                        if(i<=n){
                            add(f[i+1][j][k][x[i+1]][b],f[i][j][k][a][b]);
                            if(!a&&!b) add(f[i+1][j][k+1][x[i+1]][1],f[i][j][k][a][b]);
                        }
                        if(j<=n){
                            add(f[i][j+1][k][a][y[j+1]],f[i][j][k][a][b]);
                            if(!a&&!b) add(f[i][j+1][k+1][1][y[j+1]],f[i][j][k][a][b]);
                        }
                    }
                }
            }
        }
    }
    for(int k=0;k<=m;k++){
        if(k&1) add(ans,mod-1ll*f[n+1][n+1][k][0][0]*fac[m-k]%mod);
        else add(ans,1ll*f[n+1][n+1][k][0][0]*fac[m-k]%mod);
    }
    cout<<ans<<endl;
}