[DP记录]ARC110E Shorten ABC

**题意** ： 给出长为 $n$ 的字符串 $S$ ，字符集为 $\{\texttt{A},\texttt{B},\texttt{C}\}$ 。 可执行下列操作任意次（包括零次）： - 选定 $1\leq i\leq |S|-1$ 使得 $S_i\neq S_{i+1}$ ，将 $S_i$ 换成和原来的 $S_i,S_{i+1}$ 均不同的字符（这个字符是确定的），并删除 $S_{i+1}$。 求你能获得的不同的 $S$ 的个数。 $n\leq 10^6$ ，时限$\texttt{2s}$。 ------------ 可以发现，最终一定是一段段的字符合并在了一起。 记 $\texttt{A},\texttt{B},\texttt{C}$ 的权值分别为 $1,2,3$ ，每次合并相当于将两者的权值 xor 。这告诉我们，区间确定了，合成出的字符就确定了。 但这没有考虑相邻不同的限制。 - 若区间异或和为 $0$ ，显然有异常。 - 若非 $0$ ，区间清一色是显然无法合成。 - 否则，必能找到一对能合成的字符，且合成之后仍然满足“区间异或和非0”，“区间并非清一色”，归纳即可。 具体地，随便找一对相邻不等字符 $a,b$，若合成后区间清一色，说明其余字符都为与 $a,b$ 不同的 $c$ ，那么可以让 $b,c$ 合并（谁不是边界用谁）。 综上，除非区间异或和为 $0$ 或清一色（称这样的区间是好的），总有合并方案。（单个字符也可以看做有合并方案） 现在就相当于，将 $S$ 划分为若干好段，且统计好段们的异或和序列数目。 思考如何判定一个 $T$ 能否被生成，考虑贪心（简化方案原则）。 首先 $T$ 的异或和要等于 $S$ 的异或和。 $T$ 可能有许多的生成方案，我们考虑其中最“靠前”的一个，即每个好段的右边界都尽量靠前。 每次选一个最短的可行的段进行转移，到 $T$ 的最后一个字符，直接选完 $S$ 剩下的所有字符。 为了说明正确性，我们需要证明对于任意存在方案的 $T$ ，必然可以被上述算法构造出一种方案。 对于 $T$ 的某种方案，选出第一个好段的一个异或和为 $0$ 的后缀，满足去除之后第一个好段仍然是好的，将其转接到第二个好段前方，如此重复，不难发现，正得到了最“靠前”的方案。（调整法） 于是我们只需要计算“靠前”的方案数目。 记 $f_i$ 为 $S[1:i]$ 的“靠前”的好段划分数目。 每次向前枚举上一个字符 $\texttt{A},\texttt{B},\texttt{C}$ ，找出最小段进行转移。 注意最后一段（必须是异或和为 $0$）要补掉，故答案不仅仅是 $f_n$。特殊地，当整个串清一色时不能补 $0$ ，此时答案必为 $1$ ，特判。 复杂度 $O(n)$。 ```cpp #include<algorithm> #include<cstdio> #define MaxN 1005000 using namespace std; const int mod=1000000007; int n,f[MaxN],nxt[MaxN][4],las[4]; char s[MaxN],o[MaxN]; int main() { scanf("%d%s",&n,s+1); bool fl=1; for (int i=1;i<n;i++)fl&=(s[i]==s[i+1]); if (fl){puts("1");return 0;} for (int i=1;i<=n;i++) o[i]=o[i-1]^(s[i]=='A' ? 1 : s[i]=='B' ? 2 : 3); for (int k=0;k<=3;k++)las[k]=n+1; for (int i=n;i>=0;i--){ las[o[i]]=i; for (int k=0;k<=3;k++)if (k!=o[i]) nxt[i][o[i]^k]=las[k]; nxt[i][o[i]^o[i+1]]=i+1; } f[0]=1; for (int i=0;i<n;i++) for (int k=1;k<=3;k++) f[nxt[i][k]]=(f[nxt[i][k]]+f[i])%mod; int ans=0; for (int i=1;i<=n;i++) if (o[i]==o[n])ans=(ans+f[i])%mod; printf("%d",ans); return 0; } ```