AT_arc110_e

这种小清新题真是太有趣啦！

如果你做过 AGC027E，看到这种两个字符合成一个，最后还要计数的问题，可以构造一个关于 $S$ 的简单函数 $f(S)$，使得不管怎么操作 $f(S)$ 都不变，然后从这个不变中寻找性质。

对于 AGC027E，这个构造的方法就是令 $a\to 1,b\to 2$，$f(S)=\sum S_i \bmod 3$。于是这题我一开始也想的是模意义下的东西，但是一直没想出来。直到想到异或，瞬间有如醍醐灌顶：令 $a\to 1,b\to 2,c\to 3$，设 $f(S)=\bigoplus S_i$，这样就成功构造出来了一个不变的 $f(S)$ 了。

于是，此时知道一个区间的异或和，就能知道这个区间可能合成什么字符。但是什么时候可以什么时候不能合成一个字符呢？显然异或和为 $0$ 和区间长度 $>1$ 且区间内 $S_i$ 全相等时不行。

其他情况是否一定可行？感性理解，可以归纳地证明：若一个区间不是上两种情况，一定就能分成两个不是上面两种区间的区间。

然后考虑进行一个最简单的 dp：设 $dp_i$ 表示 $S[1,i]$ 的方案数。求 $dp_i$ 时，先枚举最后一位是什么。根据对应的异或和，就可以知道可以从哪里转移过来。

此时就会有一个结论：对于一个位置 $i$ 和一个异或和 $x$，大部分情况下只会从最大的 $j$ 满足 $\bigoplus_{j<k\le i}S_k=x$ 转移过来。这是因为 $[1,j]$ 的答案会包含 $[1,j'](k<j')$ 的答案。

证明：设另一个 $[1,j']$ 也满足 $\bigoplus_{j'<k\le i}S_k=x$。令 $[1,j']$ 能拼出来长为 $m$ 的串 $t$，若 $t_m$ 和 $S[j+1,i]$ 不全相同，根据上面的结论，$t_m$ 拼上 $S[j+1,i]$ 一定能合成一个和 $t_m$ 相同的字符。否则，考虑先将 $S[j+1,i]$ 拼到 $t$ 后面，再找到从后往前第一个不同的位置记为 $p$，则反复合并 $p,p+1$，一定也能得到和 $t$ 相同的串。

为什么说大部分情况下呢？你可能已经想到了：如果找不到上述 $p$ 呢？那么此时 $i$ 就是会从这些 $j'$ 转移过来的。但是发现会有这种情况当且仅当 $[1,j]$ 全部相同且 $[1,i]$ 不全部相同。即 $j$ 是固定的。所以可以找到每一个 $j'$ 并记录下来，后面再从这里转移。

做完了。时间复杂度 $O(n)$。

code：

int n,a[N],b[N],c[N],d[N],dp[N],pre[N],lst[4];
char s[N];
il int Mod(int x,int y){
	return x+y>=mod?x+y-mod:x+y;
}
void Yorushika(){
	read(n),scanf("%s",s+1);
	rep(i,1,n){
		a[i]=s[i]-'A'+1;
		b[i]=a[i];
	}
	dp[1]=lst[a[1]]=1;
	bool fl=1;
	rep(i,2,n){
		a[i]^=a[i-1];
		fl&=b[i]==b[i-1];
		c[i]=fl,pre[i]=lst[a[i]];
		dp[i]=!fl&&a[i];
		rep(j,1,3){
			int p=lst[a[i]^j];
			dp[i]=Mod(dp[i],dp[p]);
			if(!c[i]&&c[p]){
				if(d[p]){
					dp[i]=Mod(dp[i],d[p]);
					continue;
				}
				int tmp=p;
				p=pre[p];
				while(p){
					dp[i]=Mod(dp[i],dp[p]);
					d[tmp]=Mod(d[tmp],dp[p]);
					p=pre[p];
				}
			}
		}
		lst[a[i]]=i;
	}
	printf("%d\n",dp[n]);
}
signed main(){
	int t=1;
	//read(t);
	while(t--){
		Yorushika();
	}
}

题外话：at 数据有点水啊，我一开始每次都暴力找所有 $j'$ 居然给我过了，事实上 AAAAA...AABBBBBB...BBB 就能叉掉。