AGC027E ABBreviate | Arahc's Home

题面

简化题意

给定一个 ab 串，每次可以选择两个相邻的 a 换成一个 b；或者把相邻两个 b 换成 a，求可以构造出多少个不同的字符串。

$n\leq 10^5$ 。

题解

显然，形如 $\texttt{ababab}\cdots$ 这样的字符串是无法进行任何操作的，答案为 $1$ 。进一步地，对于一对连续的 a 或者 b 都可以进行操作。因此一个无法操作的序列一定是 ab 交替的。且任何可以操作的序列一定可以转化为一个不可操作的序列。

对于一个可操作序列，考虑求出其是否能转化为一个不可操作序列 $t$ 。

因为 $t$ 不可操作， $s$ 可操作，不妨认为 $s$ 的若干不重叠的子串，分别操作后得到了 $t$ 的一个字符。

随意提取 $s$ 的一个子串，只要其可操作，就一定能被缩成一个字符。

$\quad$

证明

对于不可操作且长度大于 $1$ 的字符串，一定不能被缩。而对于一个可操作的字符串，操作一次后长度会减小 $1$ 。若此时仍可以继续操作则继续。

若可操作的字符串操作一次后长度没有变成 $1$ 且不可操作，说明本处操作后变成的字符和两边都不同。即 $\texttt{aaaa}$ 操作中间两个 a，然而可以先操作左右两侧的 a，就可以消除这种情况。

下面考虑如何确定一个子串会被缩成什么字符：将 a 看作 $1$ ，b 看作 2，则每次操作相当于把两个连续且相同的数加起来模 $3$ 。

维护模三意义下的前缀和就可以快速算出一个子串会变成什麼字符。注意到如果子串的权值为 $0$ ，说明 ab 数量相等，此时要么这个子串不可操作，要么可以划分为权值不同的两个子串。

进一步解决如何判断把 $s$ 变成 $t$ 合法。不妨假设 $t$ 是任意字符串。

记 $s_{l...r}$ 为 $s$ 的子串 $[l,r]$ 模三意义下的数字和， $t$ 同理。设 $\left|s\right|=n,\left|t\right|=m$ 。显然第一个需要满足 $s_{1...n}=t_{1...m}$ 。然后考虑从左到右给 $s$ 分段，使得 $s$ 的第 $i$ 段对应 $t_i$ 。

不妨做一个贪心，每次分段的长度尽量小，例如 $s=\texttt{abaabbaba},t=\texttt{aab}$ ：

$s_1=t_1$ ，分段： $\texttt{a|baabbaba}$ 。
$s_{2...4}=t_2$ ，分段： $\texttt{a|baa|bbaba}$ 。
$s_5=t_3$ ，分段： $\texttt{a|aba|b|baba}$ 。

考虑 $s$ 的剩余部分是一个不可操作序列，有 $s_{6...9}=0$ ，因此显然 $s_{5...9}=0$ ，把最后两端合成一段即可。

将 $s$ 按照最短原则分段，如果最后有剩余，则剩余部分的权值和一定是 $0$ 。

$\quad$

证明

设 $s$ 被分成 $m+1$ 段，且最后一段的权值不为 $0$ 。

由于分段按最短原则，无法拆分一个段为两个，而合并两个段是不合法的（段数与 $m$ 不匹配）。因此只能合并最后一段和倒数第二段，由于最后一段权值和不为 $0$ ，但是倒数第二段已经和 $t_m$ 匹配了，合并就会导致权值部匹配。因此这种情况一定不合法。

得到上述结论后就可以 DP 了。设 $f_i$ 表示考虑到 $s_{1...i}$ ，能匹配到多少个 $t$ 。

$t$ 的对应段可以是 $1$ 或 $2$ ，根据最短原则，预处理每个 $i$ 下一个最近的位置 $j_1,j_2$ 满足 $s_{i...j_1}=1, s_{i...j_2}=2$ 。

转移时快速找到以 $i$ 为上一段的末尾，下一段的区间是什么即可。设 $i$ 为开头时，一段的结尾为 $R_i,1, R_i,2$ ：

f_i\to\begin{cases} f_{R_{i+1,1}} \\ f_{R_{i+1,2}} \end{cases}

初始状态 $f_0=1$ 。

按照这种方法 DP，得到的 $f_n$ 为分段后恰好和 $t$ 匹配的数量，还要加上可能多出来一段的情况。需要判断如果 $s_{i+1...n}=0$ ，则最后答案还要加上 $f_i$ 的值。特判 $s_{1...n}=0$ 。

代码

if(a[n]==1){
    R[n][1]=n,
    R[n][2]=R[n][0]=n+1;
}
else{
    R[n][2]=n,
    R[n][1]=R[n][0]=n+1;
}
for(register int i=n-1;i>=1;--i){
    if(a[i]==1){
        R[i][0]=R[i+1][2],
        R[i][1]=i,
        R[i][2]=R[i+1][1];
    }
    else{
        R[i][0]=R[i+1][1],
        R[i][1]=R[i+1][2],
        R[i][2]=i;
    }
}
f[0]=1;
for(register int i=0;i<n;++i){
    f[R[i+1][1]]+=f[i],f[R[i+1][1]]%=mod,
    f[R[i+1][2]]+=f[i],f[R[i+1][2]]%=mod;
    if((s[n]-s[i])%3==0 && i)
        ans+=f[i],ans%=mod;
}