题解 AT5697【[AGC041F] Histogram Rooks】

· · 题解

AT5697 [AGC041F] Histogram Rooks解题报告：

更好的阅读体验

题意

给定一个n列的棋盘，每一列高度为h_i，可以放置若干个車（不用考虑車之间会不会影响），需要把整个棋盘覆盖，求方案数。（1\leqslant n\leqslant 400）

分析

容斥毒瘤题，代码10分钟，思维10小时。

首先看到这一种棋盘的模型（可见P6453 [COCI2008-2009#4] F）果断建出笛卡尔树，然后考虑在上面dp（就是按照最小值分治，把棋盘分成类似下面这样）。

看到这个覆盖满很容易想到容斥，那么很容易第一时间定义f_{i,j}为笛卡尔树上结点i有至少k个格子没有被覆盖（下文称这些点为关键点）的方案数乘上容斥系数(-1)^k。

但是这个状态定义的就是O(n^3)，空间会炸，因此我们改变定义：f_{i,j}为笛卡尔树上结点i一共有j列不能放車（注意，这里是不能放車，这些列有可能是没有关键点的）的方案数乘上容斥系数(-1)^j，那么我们只需要关注每一个极长行连续段上是否有关键点。

我们设不能放車的列集合为S_0，不难发现S_0是无法约束关键点的，因此再次容斥，设关键点所在的列集合S_1(S_1\subseteq S_0)，容斥系数为(-1)^{|S_1|}，通过容斥简化问题后，我们讨论当前节点的决策：

设当前节点为x，区间长度（列数）为len_x，|S_0|=k，那么：

那么可以发现我们并不关心t，而是只关心t是否等于k了，直接开一维枚举t是否等于k。

具体操作就是类似树形背包，合并左右儿子的信息并进行当前结点的决策：枚举左儿子有i列不能放車，右儿子有j列不能放車，那么当前结点有i+j或i+j+1列不能放車。设a为左子树和右子树均没有贡献满的方案数，b为左子树和右子树至少有一个贡献满的方案数，那么经过讨论不难发现：

a\rightarrow f_{x,k,0},b\rightarrow f_{x,k,1},-a\rightarrow f_{x,k+1,0},a\rightarrow f_{x,k+1,1} 
int p=lc[x],q=rc[x];
for(int i=0;i<=size[p];i++)
    for(int j=0;j<=size[q];j++){
        int k=i+j;
        int a=1ll*f[p][i][0]*f[q][j][0]%mod;
        int b=(1ll*f[p][i][0]*f[q][j][1]%mod+1ll*f[p][i][1]*f[q][j][0]%mod+1ll*f[p][i][1]*f[q][j][1]%mod)%mod;
        f[x][k][0]=(f[x][k][0]+a)%mod,f[x][k][1]=(f[x][k][1]+b)%mod;
        f[x][k+1][0]=(f[x][k+1][0]-a)%mod,f[x][k+1][1]=(f[x][k+1][1]+a)%mod;
    }

记得dp完乘上没有讨论的所有点贡献的2的次幂，当然求幂的地方可以直接预处理代替快速幂优化掉\log。

复杂度：O(n^2)。

代码

#include<stdio.h>
const int maxn=405,mod=998244353;
int n,rt,top,ans;
int a[maxn],stk[maxn],lc[maxn],rc[maxn],f[maxn][maxn][2],bin[maxn],size[maxn],mul[maxn][maxn][2];
void dfs(int x,int last){
    if(x==0)
        return ;
    int p=lc[x],q=rc[x];
    dfs(p,a[x]),dfs(q,a[x]);
    for(int i=0;i<=size[p];i++)
        for(int j=0;j<=size[q];j++){
            int k=i+j,a=1ll*f[p][i][0]*f[q][j][0]%mod,b=(1ll*f[p][i][0]*f[q][j][1]%mod+1ll*f[p][i][1]*f[q][j][0]%mod+1ll*f[i][i][1]*f[q][j][1]%mod)%mod;
            f[x][k][0]=(f[x][k][0]+a)%mod,f[x][k][1]=(f[x][k][1]+b)%mod;
            f[x][k+1][0]=(f[x][k+1][0]-a)%mod,f[x][k+1][1]=(f[x][k+1][1]+a)%mod;
        }
    size[x]=size[p]+size[q]+1;
    for(int i=0;i<=size[x];i++){
        f[x][i][0]=1ll*f[x][i][0]*mul[size[x]-i][a[x]-last][0]%mod;
        f[x][i][1]=1ll*f[x][i][1]*mul[size[x]-i][a[x]-last][1]%mod;
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    bin[0]=1;
    for(int i=1;i<=n;i++)
        bin[i]=(bin[i-1]<<1)%mod;
    for(int i=0;i<=n;i++){
        mul[i][0][0]=mul[i][0][1]=1;
        for(int j=1;j<=n;j++){
            mul[i][j][0]=1ll*mul[i][j-1][0]*bin[i]%mod;
            mul[i][j][1]=1ll*mul[i][j-1][1]*(bin[i]-1)%mod;
        }
    }
    for(int i=1;i<=n;i++){
        int k=top;
        while(k>0&&a[stk[k]]>a[i])
            k--;
        if(k>0)
            rc[stk[k]]=i;
        if(k<top)
            lc[i]=stk[k+1];
        stk[++k]=i,top=k;
    }
    rt=stk[1],f[0][0][0]=1,dfs(rt,0);
    for(int i=0;i<=n;i++)
        ans=(ans+(f[rt][i][0]+f[rt][i][1])%mod)%mod;
    printf("%d\n",(ans+mod)%mod);
    return 0;
}