我是靠谱客的博主 爱听歌刺猬,最近开发中收集的这篇文章主要介绍AGC041F Histogram Rooks,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

容斥题总是很玄妙

题目描述

让我们考虑一个 N N N N N N 列的正方形棋盘。Arbok切除了棋盘的某些部分使得对于每一个 i = 1 , 2 , 3 , … , N i=1,2,3,ldots ,N i=1,2,3,,N;在第 i i i 列中只有自最底部往上数 h i h_i hi 个格子仍存在于棋盘之中。现在,他想把棋子放入到剩余的棋盘中。

是一种棋子,占据一个方格。如果一个方格所在的同一行或同一列中有一个而且方格与之间没
有已被切除的格子,那么这个方格就被所覆盖。特别的,若方格上就是,那么该方格也被覆盖

请找出所有可以使剩余的棋盘的全部方格均被覆盖的棋子放置方案数。答案可能很大,请对 998244353 998244353 998244353取模。
1 ≤ N ≤ 400 , 1 ≤ h i ≤ N 1 le N le 400,1 le h_i le N 1N400,1hiN

题解

先考虑一个这样的容斥,钦定一个不被覆盖的位置集合 s s s,容斥系数即为 ( − 1 ) ∣ s ∣ (-1)^{|s|} (1)s,研究题目性质,列肯定是连续地,我们可以选择一个列集合 S S S,使得 ∣ S ∣ |S| S中每个位置都至少钦定一个位置不被覆盖,然后计算方案数
对于一个长度为 l e n len len的行的连续段,假设有 S S S p p p个位置在这里
1. 1. 1.不钦定位置不被覆盖,除 p p p个位置外,其他地方都可以随意放棋子,方案数为 2 l e n − p 2^{len-p} 2lenp
2. 2. 2.钦定位置不被覆盖,方案数为 ∑ i = 1 p ( p i ) ( − 1 ) i = − [ p > 0 ] sum_{i=1}^pbinom{p}{i}(-1)^i=-[p>0] i=1p(ip)(1)i=[p>0]
但是发现这会算多,因为无法保证 S S S中每列都至少有一个不被覆盖的位置,那就继续容斥,钦定不能有不被覆盖的位置的集合为 T ⊆ S Tsubseteq S TS,容斥系数为 ( − 1 ) ∣ T ∣ (-1)^{|T|} (1)T
1. 1. 1.不钦定位置不被覆盖,除 p p p个位置外,其他地方都可以随意放棋子,方案数为 2 l e n − p 2^{len-p} 2lenp
2. 2. 2.钦定位置不被覆盖,方案数为 ∑ i = 1 p − q ( p − q i ) ( − 1 ) i = − [ p > q ] sum_{i=1}^{p-q}binom{p-q}{i}(-1)^i=-[p>q] i=1pq(ipq)(1)i=[p>q]
然后做法就比较显然了,可以在笛卡尔树上 d p dp dp,设 f u , p , k f_{u,p,k} fu,p,k表示在第 u u u个结点上, S S S大小为 p p p k k k表示 [ p > q ] [p>q] [p>q],时间复杂度就是树上背包的复杂度 O ( n 2 ) O(n^2) O(n2),算上快速幂,时间复杂度就是 O ( n 2 log ⁡ n ) O(n^2log n) O(n2logn)

code text{code} code

#include<cstdio>
#define ll long long
using namespace std;
void read(int &res)
{
	res=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while('0'<=ch&&ch<='9') res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
}
const int N=4e2+100;
const ll mod=998244353;
ll ksm(ll a,ll b)
{
	if(b==0) return 1;
	ll tmp=ksm(a,b>>1);
	if(b&1) return tmp*tmp%mod*a%mod;
	else return tmp*tmp%mod;
}
int n,h[N+10],cnt;
ll Pow[N+10],f[N+10][N+10][2],g[N+10][2];
void dfs(int &x,int l,int r,int fah)
{
	if(l>r)
	{
		x=0;
		return;
	}
	x=++cnt,f[x][0][1]=1,f[x][1][0]=1,f[x][1][1]=mod-1;
	if(l==r)
	{
		for(int p=0;p<=1;p++)
			for(int q=0;q<=1;q++)
				f[x][p][q]*=ksm((Pow[r-l+1-p]+mod-(q==0))%mod,h[l]-fah),f[x][p][q]%=mod;
		return;
	}
	int maxi=l;
	for(int i=l+1;i<=r;i++)
		if(h[i]<h[maxi])
			maxi=i;
	int ls=0,rs=0;
	dfs(ls,l,maxi-1,h[maxi]),dfs(rs,maxi+1,r,h[maxi]);
	for(int i=0;i<=r-l+1;i++) g[i][0]=g[i][1]=0;
	for(int i=0;i<=maxi-l;i++)
		for(int j=0;j<=1;j++)
			for(int p=0;p<=1;p++)
				for(int q=0;q<=1;q++)
					g[i+p][j&q]+=f[ls][i][j]*f[x][p][q]%mod,g[i+p][j&q]%=mod;
	for(int i=0;i<=maxi-l+1;i++)
		for(int j=0;j<=1;j++)
			f[x][i][j]=g[i][j],g[i][j]=0;
	for(int i=0;i<=maxi-l+1;i++)
		for(int j=0;j<=1;j++)
			for(int p=0;p<=r-maxi;p++)
				for(int q=0;q<=1;q++)
					g[i+p][j&q]+=f[x][i][j]*f[rs][p][q]%mod,g[i+p][j&q]%=mod;
	for(int i=0;i<=r-l+1;i++)
		for(int j=0;j<=1;j++)
			f[x][i][j]=g[i][j],g[i][j]=0;
	for(int p=0;p<=r-l+1;p++)
		for(int q=0;q<=1;q++)
			f[x][p][q]*=ksm((Pow[r-l+1-p]+mod-(q==0))%mod,h[maxi]-fah),f[x][p][q]%=mod;
}
int main()
{
	f[0][0][1]=1;
	read(n);
	Pow[0]=1;for(int i=1;i<=n;i++) Pow[i]=(Pow[i-1]<<1)%mod;
	for(int i=1;i<=n;i++) read(h[i]);
	int rt=0;
	dfs(rt,1,n,0);
	ll ans=0;
	for(int i=0;i<=n;i++)
		for(int j=0;j<=1;j++)
			ans+=f[rt][i][j],ans%=mod;
	printf("%lld",ans);
	return 0;
}

最后

以上就是爱听歌刺猬为你收集整理的AGC041F Histogram Rooks的全部内容,希望文章能够帮你解决AGC041F Histogram Rooks所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(50)

评论列表共有 0 条评论

立即
投稿
返回
顶部