ARC118E Avoid Permutations 题解

直接做有点困难，因此考虑钦定一些尚未确定的障碍点在路径上。设被钦定的障碍点的集合为

T

时，满足条件的路径数为

c(T)

，则根据容斥原理可知答案可以表示为

\sum_{T} (-1)^{|T|} c(T)

。

设

f_{i,j,k,0/1,0/1}

表示，考虑到第

i

行第

j

列的格子，此时一共钦定了

k

个障碍点，第

i

行没有 / 有障碍点，第

j

列没有 / 有障碍点时的方案数。初始时

f_{0,0,0,1,1}=1

。

设

x_i=0/1

表示第

i

行没有 / 有确定的障碍点，

y_j=0/1

表示第

j

列没有 / 有确定的障碍点。对于

f_{i,j,k,a,b}

，考虑转移：

如果 $(i,j)$ 处有障碍点，则不做转移；
如果 $(i,j)$ $(i, j)$ 处没有障碍点：
- 如果 $i \le n$ $i \leq n$ ：
  - 不在 $(i,j)$ 处钦定障碍点， $f_{i+1,j,k,x_{i+1},b} \leftarrow f_{i+1,j,k,x_{i+1},b}+f_{i,j,k,a,b}$ 。
  - 如果 $a=0$ 且 $b=0$ ：在 $(i,j)$ 处钦定障碍点， $f_{i+1,j,k+1,x_{i+1},1} \leftarrow f_{i+1,j,k+1,x_{i+1},1}+f_{i,j,k,a,b}$ 。
- 如果 $j \le n$ $j \leq n$ ：
  - 不在 $(i,j)$ 处钦定障碍点， $f_{i,j+1,k,a,y_{j+1}} \leftarrow f_{i,j+1,k,a,y_{j+1}}+f_{i,j,k,a,b}$ 。
  - 如果 $a=0$ 且 $b=0$ ：在 $(i,j)$ 处钦定障碍点， $f_{i,j+1,k+1,1,y_{j+1}} \leftarrow f_{i,j+1,k+1,1,y_{j+1}}+f_{i,j,k,a,b}$ 。

设

m

表示初始时

-1

的数量，答案即为：

\sum_{k=0}^m (-1)^k \times f_{n+1,n+1,k,0,0} \times (m-k)!

其中乘

(m-k)!

是因为没有被钦定的

p

可以在剩余的

(m-k)

个位置任意排列。

时间复杂度

\mathcal O(n^3)

。

const int N=205,mod=998244353;
int n,m,a[N],fac[N],f[N][N][N][2][2],ans;
bool vis[N][N],x[N],y[N];
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod;
}
void solve(){
	cin>>n,fac[0]=1,f[0][0][0][1][1]=1;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]!=-1) vis[i][a[i]]=1,x[i]=1,y[a[i]]=1;
		else m++;
	}
	for(int i=1;i<=m;i++) fac[i]=1ll*fac[i-1]*i%mod;
	for(int i=0;i<=n+1;i++){
		for(int j=0;j<=n+1;j++){
			if(vis[i][j]) continue;
			for(int k=0;k<=min(i,j);k++){
				for(int a=0;a<=1;a++){
					for(int b=0;b<=1;b++){
						if(i<=n){
							add(f[i+1][j][k][x[i+1]][b],f[i][j][k][a][b]);
							if(!a&&!b) add(f[i+1][j][k+1][x[i+1]][1],f[i][j][k][a][b]);
						}
						if(j<=n){
							add(f[i][j+1][k][a][y[j+1]],f[i][j][k][a][b]);
							if(!a&&!b) add(f[i][j+1][k+1][1][y[j+1]],f[i][j][k][a][b]);
						}
					}
				}
			}
		}
	}
	for(int k=0;k<=m;k++){
		if(k&1) add(ans,mod-1ll*f[n+1][n+1][k][0][0]*fac[m-k]%mod);
		else add(ans,1ll*f[n+1][n+1][k][0][0]*fac[m-k]%mod);
	}
	cout<<ans<<endl;
}

ARC118E Avoid Permutations 题解

文章操作

相关推荐

评论

ARC118E Avoid Permutations 题解