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