[ARC118E] Avoid Permutations

[ARC118E] Avoid Permutations

题目大意

一个排列 \(P=(P_1,\cdots,P_N),\;(1\le N\le 200)\),定义 \(f(P)\) 为:从一个 \((N+2)\times(N+2)\) 的网格的左上角 \((0,0)\) 走到右下角 \((N+1,N+1)\) ,每次只能向右或向下走一步,且不能经过 \((i,P_i)\) ,符合要求的路径数量为 \(f(P)\) 。

给定一个序列 \(A_1,\cdots,A_N\) ,其中 \(A_i=-1\)(表示 \(P_i\) 可以任意取值)或者 \(1\le A_i\le N\)(表示必须 \(P_i=A_i\))。求所有符合条件的排列 \(P\) 的 \(\sum f(P) \bmod 998244353\)。

思路

考虑对每一条路径求有多少不同的 \(P\) 使得此路径合法,即路径上不能有障碍物。

考虑容斥,只讨论不经过已有障碍物的路径,钦定了 \(k\) 个障碍物在此路径上(只能在没被钦定的行和列中选),剩下没钦定到的任选,方案为阶乘。

定义状态 \(f_{i,j,k,0/1,0/1}\),表示从 \((0,0)\) 走到 \((i,j)\),中途钦定了 \(k\) 个障碍,且当前第 \(i\) 行和第 \(j\) 列是否有障碍的路径总数。决策当前点是否放障碍来转移。

直接转移即可,时间复杂度 \(O(n^3)\)。

代码

点击查看代码
#include<bits/stdc++.h>
#define I inline
#define R register int
#define ll long long
using namespace std;
const int N=203,P=998244353;
I void pls(int &a,const int &b){a+=b;if(a>=P)a-=P;}
I void mns(int &a,const int &b){a-=b;if(a<0)a+=P;}
I int add(const int &a,const int &b){return a+b>=P?a+b-P:a+b;}
int f[N][N][N][4],fc[N];
int a[N];bool b[N];
int main()
{
	f[0][0][0][0]=1;
	int n,m;
	scanf("%d",&n);fc[0]=1;m=n;
	for(R i=1;i<=n;i++)
	{
		fc[i]=1ll*fc[i-1]*i%P;
		int x;scanf("%d",&x);
		if(x==-1)continue;
		a[i]=x;b[x]=1;--m;
	}
	for(R i=0;i<=n+1;i++)
		for(R j=0;j<=n+1;j++)
		{
			if(i==n+1&&j==n+1)break;
			if(b[j]&&a[i]==j)continue;
			for(R k=0;k<=m;k++)
			{
				R *t=f[i][j][k];
				if(a[i]&&b[j])pls(t[3],add(t[0],add(t[1],t[2]))),t[0]=t[1]=t[2]=0;
				else if(a[i])pls(t[3],t[2]),pls(t[1],t[0]),t[2]=t[0]=0;
				else if(b[j])pls(t[3],t[1]),pls(t[2],t[0]),t[1]=t[0]=0;
				if(i>=1&&i<=n&&j>=1&&j<=n)pls(f[i][j][k+1][3],t[0]);
				pls(f[i][j+1][k][0],add(t[0],t[2]));
				pls(f[i][j+1][k][1],add(t[1],t[3]));
				pls(f[i+1][j][k][0],add(t[0],t[1]));
				pls(f[i+1][j][k][2],add(t[2],t[3]));
			}
		}
	int ans=0;
	for(R i=0;i<=m;i++)ans=(ans+(i&1?-1ll:1ll)*fc[m-i]*f[n+1][n+1][i][0])%P;
	if(ans<0)ans+=P;
	printf("%d\n",ans);
	return 0;
}
上一篇:翻转二叉树


下一篇:题解-CF468E Permanent