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

CPP

#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;
}

文章操作

相关推荐

评论

2025_7_3 T4