题解：AT_agc026_d [AGC026D] Histogram Coloring

jycjycjyc · 2026-10-22 16:49:18 · 题解

牛逼题。

我们首先观察一下这个所谓的四方格里有 2 个 1 的结构是什么样子。

考虑第 i 列和第 i+1 列，它们的状态从下至上分别是 a_1,a_2,\cdots,a_{h_i} 和 b_1,b_2,\cdots,b_{h_{i+1}}。

令 c_i = a_i+b_i，那么合法条件实际上就是 \forall j \in [1,\min(h_i,h_{i+1})),c_j+c_{j+1} = 2。

那么实际上，我们可以发现：要么有

要么 c_j 在 0,2,0,2 \cdots 之间交替。

也就是说，两个相邻列合法，当且仅当在共同高度以下，出现两种情况之一：

1. 两列逐格取反；
2. 两列逐格相同，且在共同高度内 0,1 交替出现。

于是，我们可以考虑把“上下交替”看做一种会被强制传播的性质。

我们设 dp_{i,j} 为已经考虑完了前 i 列，并且第 i 列被左侧强制成 0,1 交替的最大高度为 j 的方案数，而 j 以上的位置还未完全统计（或者说不确定）。并且在 1 \sim j 中，虽然结构已经确定，但具体以 1 开头还是以 0 开头，尚未确定。

先不用管“强制”指什么，我们待会再看。

这里，我们使用一个 trick：我们将 dp 的转移方法由“从后面接取前面的贡献”，转换为“将前面已经处理好的贡献转移到后面”。

我们考虑如何将 dp_i 的贡献放到 dp_{i+1} 中。

首先，画个图：

我们设 H = \min(h_i,h_{i+1}),mn = \min(H,j),mx = \max(H,j)。

首先，我们观察到有一些“自由格”，也就是不受限制的格子。它们是 (mx,h_i] 之间的格子。

它们在参与转移的时候，贡献永远是一个 2 的次幂，于是我们设 w = 2^{h_i-mx}。

我们刚刚已经把两相邻列的合法情况分成了两类：相同型与取反型，即逐格相同或逐格取反。

我们一个一个考虑。

• 相同型

  我们考虑如果第 i 列和第 (i+1) 列在 H 内逐格相同，那么有如下情形：

  我们观察到，相同型本身具有一个性质：由于每个四方格内都恰有两个 1，且对于相同高度的格，它们的值也相同。那么，如果第 i 列的高度 j 及以下是 0,1 交替出现的，那么第 (i+1) 列在 H 以内也是 0,1 交替出现的。

  我们思考这个东西该怎么转移：

  对于前 (i-1) 列，它们已经把第 i 列的前 j 个格子限制为 0,1 交替，而 (i+1) 和 i 在 H 内又逐格相同，那么这相当于：**第 i 列把第 (i+1) 列的前 H 个格子限制为了 0,1 交替。

  所以，有

  dp_{i+1,H} \leftarrow dp_{i,j} \times w

  这里的 \leftarrow 是 += 的意思。

• 相反型

  我们考虑如果第 i 列和第 (i+1) 列在前 H 格内逐格相反，那么第 (i+1) 列被强制取反的位置应该是 [1,mn]。那么有

  dp_{i+1,mn} \leftarrow dp_{i,j} \times w

然后解释一下 j=0 的特殊情形。