题目

给定一个字符串 $s$,每次可以执行以下两种操作:

  • 选取一个子串 $\mathtt {aa}$,替换为 $\mathtt b$.
  • 选取一个子串 $\mathtt {bb}$,替换为 $\mathtt a$.

求能得到的本质不同的字符串 $t$ 的个数,对 $10^9 + 7$ 取模。

$1\le n\le 10^5$.

分析

设 $f(\mathtt a) = x$,$f(\mathtt b) = y$,$f(s) = \prod f(s_i)$.

考虑选取合适的 $x,y$ 使得操作后 $f(s)$ 不变,故有方程 $x^2=y,y^2=x$,解得 $x=1,\omega_3,\omega_3^2$,$x = 1$ 的意义不大,故不妨设 $x = \omega_3,y=\omega_3^2$.

容易注意到 $s\to t$ 后,$t$ 的每个字符对应着 $s$ 的一个区间,于是自然地考虑到什么样的 $s$ 能变为一个字符。

首先注意到有一个必要条件为 $f(s)\neq 1$,但不是充要条件,因为有反例 $\mathtt {abababa}\cdots$。

假如加上一个条件是必须存在相邻的相同字符呢?发现构造不出反例,仔细一想我们可以每次删去相邻相同字符连续段中,在边界上的两个字符,仍能保持条件不变并且长度减小,于是就可以证明了。

考虑对于一个 $t$,什么样的 $s$ 能够表示为 $t$,注意到可以使用类似子序列自动机的贪心匹配,最后剩下一段 $f(\operatorname{suf}(s,i)) = 1$.

于是就可以 dp 了,每次匹配某个点开始的第一段可以变成 $\mathtt a/\mathtt b$ 的区间即可。

注意特判 $s = (\mathtt a)\mathtt {bababab}\cdots$ 的情况。

时间复杂度 $\mathcal O(n)$.

代码

const int kN = 5e5 + 5;
const ll kMod = 1e9 + 7;

int n, s[kN], nxt[kN];
char str[kN];
ll f[kN];


int main() { 
    scanf("%s", str + 1);
    n = strlen(str + 1);
    nxt[n + 1] = n + 1;
    for(int i = n; i; --i) {
        s[i] = (s[i + 1] + str[i] - 'a' + 1) % 3;
        nxt[i] = nxt[i + 1];
        if(str[i] == str[i + 1])
            nxt[i] = i + 1;
    }
    if(nxt[1] == n + 1) {
        printf("1\n");
        return 0;
    }
    f[n + 1] = 1;
    for(int i = n; i; --i) {
        int j;
        for(j = nxt[i]; j <= n && (s[i] - s[j + 1] + 3) % 3 != 2 * (str[i] - 'a' + 1) % 3; ++j);
        f[i] = (f[i] + f[j + 1]) % kMod;
        f[i] = (f[i] + f[i + 1]) % kMod;
        if(s[i] == 0) f[i] = (f[i] + 1) % kMod;
    }
    if(s[1] == 0) f[1] = (f[1] - 1 + kMod) % kMod;
    printf("%lld\n", f[1]);
    return 0;
}
最后修改:2021 年 03 月 11 日 03 : 05 PM