2025_7_3 T4

· · 个人记录

今天(2025_7_19)的题,T3吉司机线段树，T4凸优化，都是我们不大擅长的点，所以回来复习模拟赛难题

算是较简单的 NOIP T4,不过这场考试虽然质量较高，但全都是DP?不管了

首先，我们不太好根据题目看出什么性质，也不太好处理题目的限制条件，考虑容斥，假设至少经过了 i 个不合法的点到达 (n+1,n+1) 的方案数为 f_i，答案为 \sum_{i=0}^{n}f_i\times (-1)^i \times (n-i)!

麻烦的是，题目中的排列有部分数是 -1，换句话而言，对于路径的限制是不全的，想要处理 f_i 难上加难，但因为限制是一个排列，每行每列只会有一个不可经过的点，而且路径只能向下或右走，所以边在网格上走路径，边尝试加障碍

设 dp_{i,j,k,p,q}，指目前走到了网格 (i,j)，已经确定 k 个障碍点，当前行有没有钦定过障碍，当前列有没有钦定过障碍,显然， dp_{i,j,k,p,q} 的转移如下

dp_{i+1,j,k,0,q}+=dp_{i,j,k,p,q}\\ dp_{i,j+1,k,p,0}+=dp_{i,j,k,p,q}

这是不走障碍的情况，如果下一个点是障碍，或者下一个点满足加障碍的条件，转移如下

dp_{i+1,j,k+(p_{i+1}!=j),1,1}-=dp_{i,j,k,p,q}\\ dp_{i,j+1,k+(p_i!=j+1),1,1}-=dp_{i,j,k,p,q}

因为容斥写在了转移里，所以是减法

答案即为

\sum_{i=cnt}^n{dp_{n+1,n+1,i,0,0}\times (n-i)!}

其中，cnt 是题目已给定的障碍数

初值 dp_{0,0,cnt,0,0}=1

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e2+10,Mod=998244353;
int n,Q,ans;
int a[maxn],dp[maxn][maxn][maxn][2][2],mul[maxn];
bool vis[maxn];
void add(int &x,int y)
{
    x+=y;
    if(x>=Mod) x-=Mod;
}
int read()
{
    int ret=0,w=1;char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+(ch^48);ch=getchar();}
    return ret*w;
}
void pre_all()
{
    mul[0]=1;
    for(int i=1;i<maxn;i++) mul[i]=1ll*mul[i-1]*i%Mod;
}
void inpu()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        if(a[i]!=-1) vis[a[i]]=1,Q++;
    }
}
void DP()
{
    dp[0][0][Q][0][0]=1;
    for(int i=0;i<=n+1;i++) for(int j=0;j<=n+1;j++) for(int k=Q;k<=n;k++)
        for(int p=0;p<=1;p++) for(int q=0;q<=1;q++) if(dp[i][j][k][p][q])
        {
            if(i<=n)
            {
                add(dp[i+1][j][k][0][q],dp[i][j][k][p][q]);
                if(!q&&1<=j&&j<=n&&i<n&&((a[i+1]==-1&&!vis[j])||a[i+1]==j))
                    add(dp[i+1][j][k+(a[i+1]!=j)][1][1],Mod-dp[i][j][k][p][q]);
            }
            if(j<=n)
            {
                add(dp[i][j+1][k][p][0],dp[i][j][k][p][q]);
                if(!p&&1<=i&&i<=n&&j<n&&((a[i]==-1&&!vis[j+1])||a[i]==j+1))
                    add(dp[i][j+1][k+(a[i]!=j+1)][1][1],Mod-dp[i][j][k][p][q]);
            }
        }
}
void cal() {for(int i=Q;i<=n;i++) add(ans,1ll*dp[n+1][n+1][i][0][0]*mul[n-i]%Mod);}
void solve()
{
    inpu();
    DP();
    cal();
    printf("%d",ans);
}
int main()
{
    pre_all();
    int t=1;
    while(t--) solve();
    return 0;
}