题解：P9151 计数题
Crescent_Rose_
·
·
题解
这里是对一种已有做法（就是洛谷题解区第一篇题解的做法）的一些详细解释。
珂怕人类智慧结论题。
需要先仔细读题理解。中位数是说排序后的中间；不是三个一起赋值而是变成一个数；（如果两边都还有）两边拼起来。
建议在纸上写写画画辅助理解。
明确自动机结构
首先注意到要算本质不同的串的个数，尝试建立自动机，在自动机上统计路径数。注意到生成的串是原串的子序列，这启发我们建立类似子序列自动机的结构。
- 对于 $3$ 个相邻相同的数，删除其中 $2$ 个。对应 $000,111$。
- 对于（相邻 $3$ 个数中）$2$ 个相邻不同的数，删除它们。对应 $110,001,100,011,101,010$。
发现它们对应且仅对应 $3$ 个数形成的这 $8$ 种情况，这说明这样的构造是可行的。
这也给我们的自动机提供了思路：$1$ 到 $n$ 每个位置作为一个结点，走到这个结点的边的边权（字符）为这个点上的数；每个点 $i$ 连向点 $j>i$，要求 $[i+1,j-1]$ 可以用上述两种操作删空（或本来就是空的）。
要在这个自动机上统计路径数，就要求每条路径和每个串一一对应，那么一个点连出同样字符的边最多一条。直接的想法是对每个点的每个“多边”字符新建一个点，让原先的点以该字符连向它，再将它连向 原先的点以此字符连向的所有点 连向的所有点；从后往前构建。（这样的正确性存疑）
然而可以不这样。我们尝试证明这个自动机有子序列自动机的某种性质（贪心）：不需要新建那个点，把原先的点连向的最近的点作为那个“新建的点”即可（对每个字符仅保留到最近的点的边）。也就是说最近的点要一步连向其他被忽略的点一步连向的点。
这里写一个显然的性质：一段能被删除的区间一定由偶数个点构成，那么自动机上相连的两点奇偶性一定不同。
于是写出命题：$\forall i,j,k$，满足 $i<j<k$ 且 $[j+1,k-1]$ 可被删除 且 $S_i=S_j$ 且 $(j-i)\bmod2=0$，那么 $[i+1,k-1]$ 也可被删除。
证明：先删除 $[j+1,k-1]$。接下来要删除 $[i+1,j]$，将 $[i+1,j-1]$（奇数个点）删除到只剩一个点，由于 $S_i=S_j$，不论这个点是 $0$ 还是 $1$ 都可以将它和 $j$ 一起删掉。
其中用了一个结论：一个奇数长度的区间一定可以被删为一个点。
证明：一旦有连续 $\leq 3$ 个相同的数就删到连续 $\leq 2$ 个，没有这样的就删除相邻的不同数；一开始有奇数个，每次删两个，一直保持奇数个；只要有不同的就可以继续删，只要有连续 $\leq 3$ 个相同的也可以继续删，于是直到只有 $\leq 2$ 个才会停止，而始终保持个数为奇数，所以最终只剩下 $1$ 个。
于是我们现在证明了自动机结构的正确性。
## 构建自动机
现在的问题是如何构建自动机。
显然 $0,1$ 等价（对称），于是这里仅考虑 $S_i=0$，看 $i$ 如何向后连边，记 $c$ 为边 $i\to j$ 上的字符。又因为 $i\to j$ 中 $i,j$ 奇偶性不同，这里仅考虑和 $i$ 奇偶性不同的 $j$（默认满足此条件）。
- 对于 $c=1$ 的出边，从左往右考虑每个 $S_j=1$。
- 因为 $[i+1,j-1]$ 长度为偶数且 $S_i=0$，第一个 $S_j=1$ 的 $j$ 就是合法的（此时 $[i+1,j-1]$ 中不会有连续的 $1$，一个 $1$ 前面必定是 $0$，那就把它们删掉。剩下的是偶数个连续的 $0$，又有 $S_i=0$，于是可以把这偶数个 $0$ 都删掉）。
- 对于 $c=0$ 的出边，从左往右考虑每个 $S_j=0$。
- 发现一个结论：若 $[l,r]$ 长度为偶数且 [ $S_l=0$ 或 $S_r=0$ ] 且 [ $S_{l-1}=0$ 或 $S_{r+1}=0$ ]，则 $[l,r]$ 可以被删除。
- 证明（对于 $S_l=S_{l-1}=0$ 的情况，另 $3$ 种同理）：先删 $[l+1,r]$（长度为奇数）直到只剩下一个数，然后不论它是 $0$ 还是 $1$ 都能删掉它和 $l$。
- 于是最靠左的 $j$ 满足 $S_j=S_{j-1}=0$ 是可行的（充分）。但还没说明它是最靠左的可行点。
- 那么就要说明它左边的都不行，即 $\forall k<j$ 且 $S_k=0$，$[i+1,k-1]$ 不能被删空。
- 证明：
- 首先有 $S_{k-1}=S_{i+1}=1$（形如“$0[1\ldots1]0$”），那么 $1$ 的段数一定比 $2$ 的段数多 $1$。
- 考虑各种删除方式，发现除了删除当前区间边界的情况，无论怎么删都要么两个段数都不变，要么两个段数都减 $1$；那这样是不能删空的。
- 再考虑区间边界被删除的情况。要让 $0$ 的段数相对 $1$ 的段数增加，就要让区间两端 $1$ 的段被删而被删的 $0$ 所在的段没被删。
- 为了拼尽全力（可能算贪心）实现这个目的，我们一旦遇到 $\geq3$ 个连续的 $1$ 就删到 $\leq2$ 个。然而 $0$ 的段长度不超过 $2$，且 $00$ 段的结尾不能和 $i$ 奇偶性不同（否则违背 $j$ 是最靠左的满足那个限制的点）。当前你要让 $1$ 的段减少且 $0$ 的段不变只能在区间开头将 $100$ 的 $10$ 删除，或在结尾将 $001$ 的 $01$ 删除。但这两种情况都违背了这条对奇偶性的限制。也就是说这样的两种 $00$ 都不会在初始情况中存在。
- 那会不会里面删除后的拼接致使左边的 $10$ 接上一个 $0$ 呢？那就是左侧为 $101001\ldots$ 这种样子（$1011001\ldots$ 和 $10101\ldots$ 都没法把更靠右的那两个或一个 $0$ 接过来）。但同样由于奇偶性的限制，更靠右的那两个 $0$ 不能共存。于是你只能继续写成 $10101\ldots$，递归下去继续处理。但一直都有奇偶性的限制，于是无法在左边完成任务。右边同理。这里是左右分开分析的，合起来也不可能在左 或/和 右完成任务。
- 于是我们证明了这个 $j$ 就是 $i$ 的 $c=0$ 边要连向的点。
总结一下，对于 $i$：
- $c=S_i$ 的边连向 $\min j$ 满足 $j>i,(j-i)\bmod2=1,S_j=S_{j-1}=c$。
- $c\neq S_i$ 的边（另一条边）连向 $\min j$ 满足 $j>i,(j-i)\bmod2=1,S_j=c$。
于是你可以直接写一个 DP，$f_{i,0/1}$ 表示 $\min j, j\geq i,j\equiv i{\pmod2},S_j=S_{j-1}='0'/'1'$，$g_{i,0/1}$ 表示 $\min j, j\geq i,j\equiv i{\pmod2},S_j='0'/'1'$。没有满足条件的 $j$ 时统一赋值为 $n+1$，$f$ 在 $i=1$ 时 $j$ 不考虑 $i$。从 $i+2$ 转移而来。
那么 $i$ 的出边就分别连向 $f_{i+1,S_i-'0'},f_{i+1,(S_i-'0')\oplus1}$，为 $n+1$ 就表示没有这条出边。
## 在自动机上 DP
构建完自动机，我们考虑如何 DP。转移是显然的（计算路径数），关键是初值和答案。
设 $dp_i$ 表示以结点（位置）$i$ 结尾的路径条数。转移就是传统的 DAG 上路径数统计。
我们并没有给自动机建立空的出发结点，也并未建立终止结点。这是因为上面自动机连边的结论建立在被删除区间两边都有数的前提下，而位置 $0$ 和 $n+1$ 上并没有数。也正因为此，我们需要仔细考虑 DP 的初值和答案。
初值：
- 考虑将位置 $0$ 作为起点，为两个字符分别寻找起点。我们回到关于连边最初的想法，要找夹着的那段能被删（或为空）的点。$0$ 上面没有数并不会对那个子序列的性质造成任何影响，即我们仍可以搬用上面的结论，只取最近的点。
- 首先 $1$ 一定作为一个字符的起点（它和 $0$ 夹着的段为空），那么另一个字符的起点就要从 $3$ 开始继续向后寻找。$0$ 上面没有数同样不会造成影响，与上面的结论同理，我们取最靠左的 $j$ 满足 $j\geq3,j \bmod 2 = 1,S_j=S_{j-1},S_j\neq S_1$ 即可。
答案：
- $i$ 能更新答案当且仅当 $[i+1,n]$ 可被删除。
- 那首先要求 $i,n$ 奇偶性相同（就保证了 $[i+1,n]$ 长度为偶数）。
- 若 $S_i=S_n$，则由“构建自动机”中的结论，$[i+1,n]$ 可以删空。
- 若 $S_i\neq S_n$，则可以将 $[i+1,n]$ 删空当且仅当 $i$ 存在自动机上字符为 $S_i$ 的出边。证明（记这条出边连向 $j$）：
- 充分性：先将 $[i+1,j-1]$ 删空。接下来要删 $[j,n]$（长度为偶数），且 $S_j\neq S_n$。一定可以先将 $[j+1,n-1]$（长度为偶数）删到只剩 $2$ 个数（证明类似长度为奇数的区间一定可以删到只剩一个数），然后分类讨论这 $2$ 个数（$0001,0011,0101,0111$），发现每种情况都可以删空。当然也可以在删除 $[i+1,j-1]$ 后把 $[j,n]$ 接到 $i$ 后面，然后利用 $S_i=S_j$ 来套用“构建自动机”中的结论。
- 必要性：证明逆否命题：若没有这条出边则无法将 $[i+1,n]$ 删空。我们在 $n+1$ 处强行填一个 $S_i$，$n+1$ 与 $i$ 奇偶性不同。由于 $S_{n+1}\neq S_{n}$，前面又不能有满足条件的出边，那就可以搬用“构建自动机”中的结论，说明在 $n+1$ 上填 $0$ 的情况下 $[i+1,n]$ 无法删空。填了 $0$ 不会变得更难删空，于是在 $n+1$ 上没有数时更是无法删空。
## 总结
理解题目想干什么，难点在哪里，从而摸清思考的方向。
多画多写。
神秘操作可以先转换一下。
对于满足某种限制的本质不同子序列的计数，不妨建立类似子序列自动机的自动机。
扩展一下，对于满足某种限制的本质不同字符串的计数，也不妨建立对应的自动机。
## 代码
```cpp
#include <bits/stdc++.h>
#define gc getchar
using namespace std;
int rd() {
int x = 0, f = 1; char c = gc();
while(c < '0' || c > '9') { if(c == '-') f = (- 1); c = gc(); }
while(c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
return (x * f);
}
const int N = 5000000, P = 998244353;
int n;
int a[N + 1], nx1[N + 1][2], nx2[N + 1][2], f[N + 1];
string s;
inline void add(int & x, int y) { x = x + y >= P ? x + y - P : x + y; }
void Solve() {
cin >> s; n = ((int)s.size()); s = "0" + s;
for(int i = 1; i <= n; ++ i) f[i] = 0; // 多测清空
for(int i = 1; i <= n; ++ i) a[i] = s[i] - '0';
f[1] = 1;
for(int i = 3; i <= n; i += 2) { if(a[i] != a[1] && a[i] == a[i - 1]) { f[i] = 1; break; } }
nx1[n + 1][0] = nx1[n + 1][1] = nx2[n + 1][0] = nx2[n + 1][1] = nx1[n + 2][0] = nx1[n + 2][1] = nx2[n + 2][0] = nx2[n + 2][1] = n + 1;
for(int i = n; i >= 1; -- i) {
nx1[i][0] = nx1[i + 2][0]; nx1[i][1] = nx1[i + 2][1];
nx2[i][0] = nx2[i + 2][0]; nx2[i][1] = nx2[i + 2][1];
nx1[i][a[i]] = i;
if(i > 1 && a[i] == a[i - 1]) nx2[i][a[i]] = i;
}
int ans = 0;
for(int i = 1; i <= n; ++ i) {
if(nx1[i + 1][a[i] ^ 1] <= n) add(f[nx1[i + 1][a[i] ^ 1]], f[i]);
if(nx2[i + 1][a[i]] <= n) add(f[nx2[i + 1][a[i]]], f[i]);
if(((n - i) & 1) == 0 && (a[i] == a[n] || nx2[i + 1][a[i]] <= n)) add(ans, f[i]);
}
printf("%d\n", ans);
}
int main() {
int T = rd();
while(T --) Solve();
return 0;
}
// 参考：
// https://www.luogu.com.cn/article/n4ytnmoj
// https://shijiuwan.github.io/P9151/
// https://www.cnblogs.com/zltzlt-blog/p/18047850
```
## 参考
- https://www.luogu.com.cn/article/n4ytnmoj
- https://shijiuwan.github.io/P9151/
- https://www.cnblogs.com/zltzlt-blog/p/18047850
2025.5.6 & 2025.5.7