AGC 027E
有个字符串(s)，由'a'和‘b'组成。
可以如此操作：
- 将一个’aa'改成'b'。
- 将一个'bb'改成‘a'。
问这样形成的本质不同的字符串个数。
(nle 10^5)
离正解差一步。
按照套路，先考虑如何判定：即枚举一个字符串(t)，判定它是否能够被(s)操作得到。
先手玩一下单个字符能被哪些字符串操作得到。
假如这个字符是(a)。它被操作了(c)次，那么(cnt_bequiv -c pmod 3)。
归纳一下就可以证出来了。
但这个条件不充分。于是加上：这个字符串至少拥有一对相邻的相同的字符。发现有了这个之后就充分了。
回到判定问题。现在对于(t_i)，让它匹配([x,x+c])这段区间。那么就要满足(cnt_b[x,x+c]+cequiv 0 pmod 3)
如果要把这个判定方法变成计数，那么一定要让这个判定的过程唯一。
猜想一下：找到一个满足这个条件的最小的(c)，然后直接匹配过去。
可以证明：只考虑这个条件，如果存在同样满足条件的(c<c')，那么区间([x+c+1,x+c'])可以被接到后面的区间中。
于是就这样一直匹配，最后一个特殊处理一下（匹配剩下的区间）。
但是如果只考虑这个结论，可能不满足有相同的相邻的字符这个条件。这个只会在最后一个区间出现，因为前面的区间选的都是尽量小的长度，用a匹配形如ababa的区间，不如匹配a。所以只需要考虑最后一个区间。假设最后一个区间长成ababa，在它前面找到最靠右的a或bb（也就是长成a/bb+abab...ab+ababa），由于(aab o a,bbab o bb)，所以一定存在一个操作消掉一些ab，最后的影响是最后一个区间消得只剩a。
因此做法就出来了：先特判一定完全是不同字符交替的情况，剩下的情况直接对每个字符匹配最小区间，按照这样做个DP。
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100010
#define ll long long
#define mo 1000000007
int n;
char s[N];
int sum[N][2];
int nxt[N][2][3];
int f[N];
int main(){
freopen("in.txt","r",stdin);
scanf("%s",s+1);
n=strlen(s+1);
for (int i=1;i<=n;++i)
s[i]-='a';
bool spj=1;
for (int i=1;i<n && spj;++i)
spj&=(s[i]!=s[i+1]);
if (spj){
printf("1
");
return 0;
}
for (int i=1;i<=n;++i){
sum[i][0]=sum[i-1][0]+(s[i]==0);
sum[i][1]=sum[i-1][1]+(s[i]==1);
}
nxt[n+1][0][0]=nxt[n+1][0][1]=nxt[n+1][0][2]=
nxt[n+1][1][0]=nxt[n+1][1][1]=nxt[n+1][1][2]=n+1;
for (int i=n;i>=1;--i){
memcpy(nxt[i],nxt[i+1],sizeof nxt[i]);
nxt[i][0][(sum[i][0]+i)%3]=i;
nxt[i][1][(sum[i][1]+i)%3]=i;
}
f[0]=1;
ll ans=0;
for (int i=0;i<n;++i)
for (int c=0;c<2;++c){
int d=(sum[i][c^1]+i+1)%3,j=nxt[i+1][c^1][d];
if (j<=n)
(f[j]+=f[i])%=mo;
if ((sum[n][c^1]+n)%3==(sum[i][c^1]+i+1)%3)
(ans+=f[i])%=mo;
}
printf("%lld
",ans);
return 0;
}