自动搬运

查看原文

来自洛谷，原作者为

	C1942huangjiaxu 我将终究顺流入大海

搬运于2025-08-24 22:45:50，当前版本为作者最后更新于2024-03-13 20:46:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目中的操作可以看做：

• 选择 2 个相邻的不同的数并删除。
• 选择 3 个相邻且相同的数，删掉其中 2 个。

那么最终对答案有贡献的 $T$ 一定是 $S$ 的子序列。

考虑构建这样一个自动机，每个点 $i$ 有 $0,1$ 两条出边，出边 $c$ 连向最小的 $j\gt i,S_j=c$ 满足 $S[i+1,j-1]$ 可以被删除的位置 $j$。

假如 $S[j+1,n]$ 可以被删除，那么所有起点为 $0$ 终点为 $j$ 的路径都是一个答案。

但这样不够，我们还要证明，每一个答案串 $T$ 都可以被自动机匹配上。

考虑构建自动机的过程其实是一个贪心的过程，我们只要证明， $\forall i\lt j$ 满足 $S_i=S_j$ 且 $i,j$ 奇偶性相同，那么对于所有 $k$ 满足 $S[j+1,k]$ 可以被删除，则 $S[i+1,k]$ 可以被删除。

证明也很简单，只要证明 $S[i+1,j]$ 可以删除，先把 $S[i+1,j-1]$ 删到只剩下一个数 $c$，然后删除 $c$ 和 $S_j$ 即可。

自动机的边数是 $O(n)$ 的，我们只要建出这个自动机就行了。

以 $S_i=0$ 为例，出边 $j$ 一定满足 $i,j$ 奇偶性不同，下面只考虑奇偶性与 $i$ 不同的位置是否满足条件。

对于 $c=1$ 的出边，找到第一个 $S_j=1$ 即可，中间显然能删完。

对于 $c=0$ 的出边，上面已经说明了，若 $S_{j-1}=0$ 则 $S[i+1,j-1]$ 可以被删除，所以找到第一个 $j$ 满足 $S_j=S_{j-1}=0$ 的 $j$。

我们要证明所有 $k\lt j,S_k=0$，$S[i+1,k-1]$ 都不可以删完。

首先 $S[i+1,k-1]$ 中不存在连续的 $3$ 个 $0$，我们把连续的 $1$ 也都删除到不超过 $2$ 个，那么相当于是一个 $1$,$0$,$11$,$00$ 交替序列，并且序列的开头和末尾都是 $1$ 段。

注意到不存在奇偶不同的 $p,q$ 满足 $S_p=S_{p+1}=S_q=S_{q+1}=0$，否则 $j$ 不是第一个，那么，删除过程中始终会是一个满足不存在 $p,q$ 的 $1$,$0$,$11$,$00$ 交替序列。

证明考虑归纳：

删除过程中产生 $1$ 段的合并，直接贪心把个数减小到不超过 $2$。

删除过程中产生 $0$ 段的合并，因为不存在 $p,q$ ，即不存在 $00100$ 串，所以一定是 $2$ 个 $0$ 的合并，设原先的串为 $10xx01$，我们删除了 $xx$，$xx$ 是 $01$ 或 $10$ 。
可以发现，不论 $xx$ 是什么，删除后的 $00$ 串奇偶性与原先的 $00$ 串奇偶性相同，仍然不存在 $p,q$。

因为 $1$ 段个数比 $0$ 段多 $1$，所以最后剩下的一定是 $11$，即 $S[i+1,k-1]$ 不能被删除。

时间复杂度 $O(n)$。

代码很好写：

#include<bits/stdc++.h>
using namespace std;
const int N=5e6+5,P=998244353;
int T,n,f[N],nx[N][2],to[N][2],ans;
char s[N];
inline void Add(int &x,int y){
	if((x+=y)>=P)x-=P;
}
void solve(){
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;++i)f[i]=0,s[i]-=48;
	f[1]=1;
	for(int i=3;i<=n;i+=2)if(s[i]!=s[1]&&s[i]==s[i-1]){
		f[i]=1;
		break;
	}
	for(int i=1;i<3;++i)for(int j=0;j<2;++j)nx[n+i][j]=to[n+i][j]=n+1;
	for(int i=n;i;--i){
		nx[i][0]=nx[i+2][0],nx[i][1]=nx[i+2][1];
		to[i][0]=to[i+2][0],to[i][1]=to[i+2][1];
		nx[i][s[i]]=i;
		if(i<n&&s[i]==s[i+1])to[i][s[i]]=i+1;
	}
	ans=0;
	for(int i=1;i<=n;++i)if(f[i]){
		Add(f[nx[i+1][s[i]^1]],f[i]);
		Add(f[to[i][s[i]]],f[i]);
		if(!(n-i&1)&&(s[i]==s[n]||to[i][s[i]]<=n))Add(ans,f[i]);
	}
	printf("%d\n",ans);
}
int main(){
	scanf("%d",&T);
	while(T--)solve();
	return 0;
}