【解题报告】AGC026D - Histogram Coloring

题目链接

---

题目大意

给你一个有 $N$ 列 $1e9$ 行的直方图，对于第 $i$ 列只保留最下面下面的 $h[i]$ 行。现在你有黑白两种不同的颜色来对这张保留后的图涂色，要求满足对于每个 $2\times2$ 的大方格，必须满足每种颜色恰好占这个大方格的一半，求涂抹的方案总数。答案对1e9+7取模。
$$
1<=N<=100\text{且}0<=h[i]<=1e9
$$

仓鼠zzy题解:

首先考虑一个完整的矩形如何计数答案
假如已经决定了前面的行，要新增一行。首先可以把上面一行全部翻转当成新增一行；特殊地，当上面一行是黑白相间的，可以直接把上面一行复制下来
对于原问题考虑笛卡尔树dp，实际上就是每次把最低的一层给消掉。这样也构成了一个树的结构，然后从下往上dp，每次记录是否黑白相间的情况
转移需要把所有上面的层合并，讨论一些情况

自己的解释:

1.对于一个高为 $H$，宽为 $len$ 的完整矩形。

首先设 $ans1$ 表示涂抹方式为黑白相间合法的方案数，$ans0$ 为非黑白相间的合法涂抹方案数

我们考虑分两种情况考虑，如果第一行不是黑白相间的，那么对于后面行只有唯一的涂抹方式,即:
$$
ans0=2^{len}-2;
$$
如果第一行为黑白相间的涂抹方式，那么对于后面每一行都有两种涂抹方式,即
$$
ans1=2^{H}
$$
2.回到原问题，对于一个不规则的直方图，我们考虑将其划分成多个完整的矩形，并将每个完整小矩形离散化为一个点，然后构建出一棵树来转移。离散化代码:

void build(int l,int r,int id)
{
    int minheight=inf,top=0;
    int st[maxn];
    si[id]=r-l+1;
    for(register int i=l;i<=r;++i)
    {
        if(h[i]<=minheight)
        {
            if(h[i]<minheight)
            {
                top=0;
                minheight=h[i];
                st[++top]=i;
            }
            else
                st[++top]=i;
        }
    }
    st[++top]=r+1,a[id]=minheight;
    int lastgo=l;
    for(register int i=1;i<=top;++i)
    {
        if(st[i]==lastgo)
        {
            ++lastgo;
            continue;
        }
        ++tot;
        c[id].push_back(tot);
        build(lastgo,st[i]-1,tot);
        lastgo=st[i]+1;
    }
}

离散化完成后，我们就可以设 $dp[u][0]$ 为对于当前节点涂抹中为非黑白相间的合法涂抹方式，$dp[u][1]$ 为黑白相间的合法涂抹方式。

那么我们就可以推出转移方程:
$$
\begin{cases}
W=len_u-\sum_{v\in son_u}lenv\\
dp[u][0]=2^W\times\prod_{v\in son_u}(dp[v][0]+dp[v][1])+(2^W-2)\times\prod_{v\in son_u}dp[v][1]\\
dp[u][1]= 2^{H_u}\times\prod_{v\in son_u}dp[v
][1]
\end{cases}
$$

树上递归实现：

void dfs(int u,int lasth)
{
    int sum=si[u];
    int H=a[u]-lasth;
    f[u][1]=1,f[u][0]=1;
    for(register int i=0;i<c[u].size();++i)
    {
        int v=c[u][i];
        dfs(v,a[u]);
        f[u][0]=(f[u][0]*((f[v][1]+f[v][0])%p)%p+(f[u][0]*f[v][1])%p)%p;
        f[u][1]=(f[v][1]*f[u][1])%p;
        sum-=si[v];
    }
    f[u][0]=((f[u][0]*ksm(2,sum))%p+(p-2*f[u][1]%p)%p)%p;
    f[u][1]=(f[u][1]*ksm(2,H))%p;
}

$$
\text{the end}
$$