yukicoder : No.1171 Runs in Subsequences

最近yukicoder毎週あるなぁ。
https://yukicoder.me/problems/no/1171

問題

N文字の文字列Sが与えられる。
Sの部分列(2^N-1)通りにおける連の数の総和を(10^9+7)で割った余りを求めよ。

解法

Sが部分列Tを作ることを考える。
Sを1文字ずつ、Tに加えるかどうかを見ていくことにしよう。

今i文字目をどうするか考える。
加える場合、Tの末尾と同じ文字を加える場合連は増えず、そうでない場合は連が増える。
後者の場合、(i-1)文字目までの内容が連として確定するので、そこまでの組み合わせに対し、それ以降の文字の選択の有無(2^(N-i))通りを解として適宜形状しよう。
DPの際は、「Tの末尾」を状態として持つので、時間・空間計算量はアルファベットの種類をw種としてO(Nw)となる。

ll dp[202020][27];
const ll mo=1000000007;
string S;
ll p2[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	dp[0][26]=1;
	
	p2[0]=1;
	FOR(i,201010) p2[i+1]=p2[i]*2%mo;
	
	ll ret=0;
	
	cin>>S;
	FOR(i,S.size()) {
		FOR(j,27) {
			// keep
			(dp[i+1][j]+=dp[i][j])%=mo;
			// add
			(dp[i+1][S[i]-'a']+=dp[i][j])%=mo;
			if(j!=S[i]-'a' && j!=26) {
				(ret+=dp[i][j]*p2[S.size()-1-i])%=mo;
			}
		}
	}
	FOR(i,26) ret+=dp[S.size()][i];
	cout<<ret%mo<<endl;
}

まとめ

連ってあんまり出てこない印象。