P9151 计数题

· · 题解

题目中的操作可以看做：

那么最终对答案有贡献的 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;
}