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$，那么：

• 如果$|S_1|=0$，方案数为$2^{len_x-k}$。
• 如果$|S_1|>0$，我们枚举$|S_1|$的大小为$t$，然后枚举$S_0$除了$S_1$的部分有多少列真正被覆盖了，那么可知道算上容斥系数后贡献之和为$\sum_{i=1}^{k-t}(-1)^k{k\choose i}$，这个东西可以化简成$-[k\ne t]$。

那么可以发现我们并不关心$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;
}