AtCoder AGC #027 : E - ABBreviate

解説見るとすんなり解けるんだけどね。
https://beta.atcoder.jp/contests/agc027/tasks/agc027_e

問題

'a''b'で構成された文字列Sが与えられる。
文字列中任意のaaをb、またはbbをaに置き換えるという処理を任意回数行ったとき、生成できる文字列は何通りか。

解法

Sがaaやbbを含まない場合、Sを変更できないので解は1。

以下そうでないケースを考える。
文字列Tに対し、
f(T) := aを1、bを2の重みづけで文字数をカウントした値を3で割った剰余
とする。
f(aa)=f(b)=2、f(bb)=f(a)=1なので、処理を行う前後でf(T)の値は変わらない。
もしTに1箇所でも同じ文字が連続している場所があり、かつf(T)=1または2なら、Tは処理を繰り返しa,bに変換できる。

g(n) := S[0..(n-1)]を変換してできる文字列の数
とする。
S[0..(n-1)]を変換してできる文字列に対し、以後何もない文字列を生成するには、f(S[0..(n-1)])=f(S)であればよい。
f(S[n..(|S|-1)])=0ならば、これができることが証明できる(Editorial参照)。
よってその場合g(n)を解に加算する。

S[0..(n-1)]を変換してできる文字列に、'a'または'b'を加えることを考える。
これは先ほどのf(T)の理屈を元に、S[n...(m-1)]をaまたはb1文字にできる最小のmがあれば、g(m)+=g(n)と値を更新して以降。

int N;
string S;
int nex[101010][2];
int F[101010];
int tmp[3];
ll dp[101010];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	FOR(i,N-1) if(S[i]==S[i+1]) break;
	if(i==N-1) return _P("1\n");
	
	FOR(i,N) {
		S[i]-='a'-1;
		F[i+1]=(F[i]+S[i])%3;
	}
	nex[N][0]=nex[N][1]=N+1;
	tmp[0]=tmp[1]=tmp[2]=N+1;
	int pn=N;
	for(i=N-1;i>=0;i--) {
		if(i<N-1 && S[i]==S[i+1]) {
			while(pn>i) tmp[F[pn]]=pn, pn--;
		}
		if(S[i]==1) {
			nex[i][0]=i+1;
			nex[i][1]=tmp[(F[i]+2)%3];
		}
		else {
			nex[i][1]=i+1;
			nex[i][0]=tmp[(F[i]+1)%3];
		}
	}
	dp[0]=1;
	FOR(i,N) {
		if(nex[i][0]<=N) (dp[nex[i][0]]+=dp[i])%=mo;
		if(nex[i][1]<=N) (dp[nex[i][1]]+=dp[i])%=mo;
	}
	ll ret=0;
	for(i=1;i<=N;i++) if(F[i]==F[N]) ret+=dp[i];
	cout<<ret%mo<<endl;
	
	
}

まとめ

よく問題が考え付くよね。