AGC027E ABBreviate

https://atcoder.jp/contests/agc027/tasks/agc027_e

话说把一个 AGC 的 E 放 noip 模拟赛是什么居心（

比较神奇的一题，用 1 表示 a，2 表示 b，那么无论怎么操作，用数字表示字符串的和总是在模 3 意义下不变
用 (P(S)) 表示这个和
( exttt{ababab...}) 这种答案是 1，先特判
然后观察发现能将 (s) 变成 a 或 b 的充要条件是 (P(s)=1) 或 (P(s)=2)，且 (s) 中有至少两个连续的相同字符

再考虑 (t) 能不能变成 (s)，就是能不能成功的把 (s) 分成 (|t|) 或 (|t|+1) 段，使得第 (i) 段的 P 和 (P(t_i)) 相等
如果有第 (|t|+1) 段，它的 P 应为 0
如果能，且 (s) 中有至少两个相连的相同字符，则 (t) 合法
那么设 (f(i)) 前 i 个字符为一段的方式，从后往前递推，(f(i)) 由 (f(next(1/2))) 转移而来，分别代表往后面加一个 A 或 B
其中 (next(i)) 表示当前下一个 (P) 的前缀和为 (i) 的位置

更详细的证明和说明，懒得自己再写了：
https://www.cnblogs.com/wyxwyx/p/agc027e.html
https://www.luogu.com.cn/blog/PinkRabbit/solution-at4379

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<cstring>
#include<iostream>
#define reg register
inline int read(){
	register int x=0;register int y=0;
	register char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')y=1;c=getchar();}
	while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
	return y?-x:x;
}
#define mod 1000000007
char s[100006];
int nex[3];
int sum[100006],f[100006];
int n;
inline int no(){
	for(reg int i=1;i<n;i++)if(s[i]==s[i+1]) return 0;
	return 1;
}
int main(){
	scanf("%s",s+1);n=std::strlen(s+1);
	if(no()) return puts("1"),0;
	for(reg int i=1;i<=n;i++) sum[i]=sum[i-1]+(s[i]-'a'+1),sum[i]%=3;
	f[n]=1;f[n+1]=0;
	for(reg int j=0;j<3;j++) nex[j]=j==sum[n]?n:(n+1);
	for(reg int i=n;i;i--){
		f[i]=sum[i]==sum[n];
		for(reg int j=1;j<3;j++) f[i]+=f[nex[(sum[i]+j)%3]],f[i]%=mod;//在后面加一个 A 或 B
		nex[sum[i]]=i;
	}
	printf("%d
",(f[nex[1]]+f[nex[2]])%mod);
	return 0;
}