AT_abc435_g [ABC435G] Domino Arrangement 题解

Phoenix_2010 · 2025-12-15 22:17:13 · 题解

题目限制相当于每一个极长同色连续段（不包括无色）长度都是 2。

显然是一个划分子段问题。考虑 dp。设 dp_i 表示前 i 个格子的方案数。显然 dp_0=1。考虑转移：

首先，第 i 格可以不涂颜色，dp_i \leftarrow dp_{i-1}。

然后，第 i 格和 i-1 格可以涂上相同颜色，dp_i \leftarrow dp_i+dp_{i-2} \times cnt_{i-1,i}，其中 cnt_{i,j} 表示可以给 [i,j] 上色的有几种。

但是这样会考虑到一种颜色同时给 [i-3,i] 上色的情况，需要减去，dp_i \leftarrow dp_i-dp_{i-4} \times cnt_{i-3,i}。

但是当 [i-5,i] 为同种颜色时，第一次没有考虑这种情况，因为 [i-5,i-2] 同色是不合法的。而第二次考虑了这种情况，因为 [i-5,i-4] 同色是合法的。所以又需要加回来。

所以此时就有容斥的影子了。具体的，

考虑优化。

首先 dp_{i-2j} 这一项直接分最后一段的奇偶性前缀和维护即可。考虑怎么维护这个 cnt。

一个常见套路是维护以 i 为结尾的 cnt，并考虑 i 移动时的贡献。当 i \rightarrow i+1 时，我们会新加入一个 cnt_{i+1,i+1}，即 i+1 被覆盖次数，这个差分即可。然后对于每个以 i 为结尾的 [l,r]，将不再包含以 i+1 结尾的区间，失去贡献，使得 \forall j \in [l,i], cnt_{j,i+1} \leftarrow cnt_{j,i}-1。

把上述二者结合一下，设 c_0,c_1 表示以 i 为结尾，最后一段长度为偶数，奇数时的总贡献。当 i \rightarrow i+1 时：

最后一段长度奇偶性改变，交换 c_0,c_1。

加入了 cnt_{i+1,i+1}，此时 c_1 中所有的贡献需要变为原来的相反数（因为多了一段），即 c_1 \leftarrow cnt_{i+1,i+1} \times dp_{i-1}

对于每个以 i 为结尾的 [l,r]，由于分了奇偶性，而且同奇偶性中分正负，所以要按照长度除以 4 的余数分类讨论。

由于 cnt 是成段减一的，不妨设前缀和数组 s_{i,0/1}：