[ARC118E]Avoid Permutations 题解

Umbrella_Leaf · 2023-03-21 09:01:16 · 题解

称不能经过的坐标 (i,P_i) 为关键点。

首先我们考虑，对于一个固定的排列 P 如何计算 F(P)。不经过任意一个关键点的方案不好求，遂想到容斥。

对每个关键点，我们有两种选择：无视，或者经过但是答案乘上 -1。直接在网格图上 DP 即可：设 dp_{i,j} 表示走到 (i,j) 的方案数，转移时分类讨论。

那么有了不固定排列之后还是可以这样 DP：设 dp_{i,j,k,0/1,0/1} 表示走到 (i,j)，经过了 k 个原本不确定的关键点，此时第 i 列是否已经有关键点，第 j 行是否已经有关键点。需要记录 k 的原因是：除了钦定经过的 k 个关键点外，剩下的未确定关键点可以随意排列，因此最后要乘上一个 (m-k)!，m 表示 P 中不确定的位置数。

这样直接转移就能够以 O(n^3) 的复杂度通过。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353;
int n,m;
int a[205],b[205];
ll dp[205][205][205][2][2];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)b[i]=-1;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i]>0)b[a[i]]=i;
        else m++; 
    }
    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 p=0;p<2;p++)
                    for(int q=0;q<2;q++)if(dp[i][j][k][p][q]){
                        if(i<=n){
                            dp[i+1][j][k][a[i+1]>=0][q]=(dp[i+1][j][k][a[i+1]>=0][q]+dp[i][j][k][p][q])%mod;
                            if(a[i+1]==j&&j)dp[i+1][j][k][1][1]=(dp[i+1][j][k][1][1]-dp[i][j][k][p][q]+mod)%mod;
                            if(a[i+1]<0&&!q)dp[i+1][j][k+1][1][1]=(dp[i+1][j][k+1][1][1]-dp[i][j][k][p][q]+mod)%mod;
                        }
                        if(j<=n){
                            dp[i][j+1][k][p][b[j+1]>=0]=(dp[i][j+1][k][p][b[j+1]>=0]+dp[i][j][k][p][q])%mod;
                            if(b[j+1]==i&&i)dp[i][j+1][k][1][1]=(dp[i][j+1][k][1][1]-dp[i][j][k][p][q]+mod)%mod;
                            if(b[j+1]<0&&!p)dp[i][j+1][k+1][1][1]=(dp[i][j+1][k+1][1][1]-dp[i][j][k][p][q]+mod)%mod;
                        }
                    }
    ll ans=0,now=1;
    for(int i=m;i>=0;i--)ans=(ans+dp[n+1][n+1][i][1][1]*now%mod)%mod,now=now*(m-i+1)%mod;
    printf("%lld\n",ans);
    return 0;
}