题解：P9151 计数题
山田リョウ
·
·
题解
P9151. 计数题
Statement
给定一个仅由 0,1 构成的序列 s，每次操作可以选择连续三项替换为它们的众数（长度减少 2），求有多少种不同的可以通过若干次操作达到的序列，对 998\;244\;353 取模。
## Solution
不难发现对序列操作若干次相当于将序列划分为若干个奇数长度区间，每个区间操作若干次变为恰一个数然后拼起来，因此我们先考虑判定一个序列是否能进行若干次操作变成一位 $1$。这个当然是经典原题 [AGC022 E. Median Replace](https://www.luogu.com.cn/problem/AT_agc022_e)，它告诉我们可以建出一个 DFA 来判定这件事，这个 DFA 是这样的：
第一个字符是 $0$ 则在 $0$ 结点起始，否则在 $1$ 结点起始，一个长为 $2l+1$ 的字符串从起始点开始，每次跳接下来两个字符对应的转移边，跳 $l$ 次后跳到 $1,3$ 结点当且仅当其可以被删为恰好一个 $1$。
那你再观察一下这个转移，可以发现有一个偏序关系是 $0\prec2\prec1\prec3$。
因此如果我们想要凑出一个 $1$，这个 $0$ 状态无疑是要避免的，因此我们希望我们的起始点尽可能是 $1$，当然序列的第一个区间起始点是无法调整的，但是我们手玩一下可以发现对于其他的区间，利用到刚才提到的偏序关系以及从 $2$ 状态走一步第二位是 $1$ 的转移边一定会走到 $1$ 状态的性质，足以证明一定能调整到一个起始点是最终变化到的字符的划分，因此直接写一个序列 dp，从一个区间的起始点决策下一个区间的 $0,1$ 并转移到第一个合法的转移点即可，第一个合法转移点可以倒着预处理出来，要特殊处理下合法开头和合法结尾。时间复杂度 $O(\lvert s\rvert)$。