[ARC118E] Avoid Permutations

本文主要是介绍[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;
}

这篇关于[ARC118E] Avoid Permutations的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

C/C++教程