菜王的 blog

首先考虑原题咋做。考虑判断答案。

• 当且仅当 $a$ 序列全为 $0$ 时答案为 $0$；
• 序列 $a$ 没有 $0$ 时答案为 $2$ 的个数对 $2$ 取模的余数 $+1$；
• 否则，当且仅当在序列 $a$ 为“一段 $1$，$2, 0, 2$，一段 $1$”（左右两边的一段 $1$ 都可以为空）的形式时，答案为 $2$，其余情况为 $1$。

证明

前两个情况是显然的。先证明第三种情况的对应形式无法合成 $1$，可以发现如果 $0$ 不参与操作只是相当于减少了一个 $1$，还是该形式；而 $0$ 若参与操作，序列 $a$ 就会变为第二种情况，并且只有奇数个 $2$，显然答案为 $2$。所以该情况一定只能合成 $2$。

再证明非对应形式一定可以合成。考虑归纳，如果我们能找到一个 $0$，然后将其左右两边合成，只要左右两边不都是 $2$，最终就可以合出 $1$。

假设 $0$ 的个数大于两个，那么选择最左边的 $0$ 即可，右边至少有两个 $0$，一定可以得到 $1$；

假设 $0$ 的个数恰好有两个，那么序列 $a$ 一定是 $A0B0C$ 的形式，其中 $A, B$ 都是不存在 $0$ 的序列。如果 $B$ 为 $[2]$，那么先将 $B$ 和旁边一个 $0$ 合成即可得到 $A01C$ 的形式，该形式答案一定为 $1$；否则左右两个 $0$ 肯定有一个合法。

假设 $0$ 的个数只有一个。如果 $0$ 两边至少有一个不是 $2$，那么我们就有操作空间了：当 $2$ 有奇数个时，我们让最靠近 $0$ 的 $2$ 把经过的 $1$ 都干掉，与 $0$ 合并。否则我们直接让 $0$ 与它旁边的那个 $1$ 合并。假设这个 $0$ 的左右两边都不合法，那么一定有一边至少有三个 $2$，我们把最靠近 $0$ 的两个 $2$ 合并，$0$ 两边就至少有一个 $1$；否则可以直接合出 $1$。

这样所有情况都被考虑到了，证毕。

那么对于最小字典序，我们贪心从前往后枚举合并位置即可，如果一个位置合并时不影响答案就合并。

显然答案为 $0$ 或 $2$ 时合并序列均为全 $1$，那么我们只需要考虑答案为 $1$ 的情况。

那么我们肯定是一直合并第一个位置，直到某个临界位置时再合并第一个位置会导致答案变大。考虑这种临界情况会有若干种（其中第一个位置可能是一个前缀一直合并第一个位置得出的）：

1. $0111\dots1120211\dots11$；
2. $0211\dots1120211\dots11$；
3. $1011\dots1120211\dots11$；
4. $2011\dots1120211\dots11$；
5. $2211\dots1120211\dots11$；
6. $210211\dots11$；
7. $01s$，其中 $s$ 里只包含 $1, 2$，且 $2$ 的个数为奇数。
8. $10s$，其中 $s$ 里只包含 $1, 2$，且 $2$ 的个数为奇数。
9. $20s$，其中 $s$ 里只包含 $1, 2$，且 $2$ 的个数为奇数，且 $s \ne 211\dots11$。
10. $02s$，其中 $s$ 里只包含 $1, 2$，且 $2$ 的个数为奇数。

对于每一种分类讨论出它对应的序列并统计即可。计数是简单的，你可能需要预处理出 $f_{i, j}$ 表示长度为 $i$，一直合并首位得到 $j$ 的序列数，可能还需要处理 $2$ 的幂次。时间复杂度为 $\mathcal O(\sum n)$。