概述
容斥题总是很玄妙
题目描述
让我们考虑一个 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
1≤N≤400,1≤hi≤N
题解
先考虑一个这样的容斥,钦定一个不被覆盖的位置集合
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}
2len−p
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
T⊆S,容斥系数为
(
−
1
)
∣
T
∣
(-1)^{|T|}
(−1)∣T∣
1.
1.
1.不钦定位置不被覆盖,除
p
p
p个位置外,其他地方都可以随意放棋子,方案数为
2
l
e
n
−
p
2^{len-p}
2len−p
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=1p−q(ip−q)(−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所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复