Codeforces #393 Div1 D. Bacterial Melee

普段のDiv1 Dよりは若干簡単。
http://codeforces.com/contest/759/problem/D

問題

文字列Sが与えられる。
この文字列に対し、1文字を選択し、それを左右どちらか隣の文字にコピーして上書きする、ということを任意回数繰り返すとする。
こうして得られる文字列Tは何通りか。

解法

得られる文字列は、Sの部分列のうち一部文字を繰り返して総長を|S|に戻したものである。

以下を考えよう。求めたいのはsum(dp(*,|S|-1))である。
dp(p,t) := 末尾にS[p]が来るようにしてT[0..(t-1)]までt文字構築した場合の組み合わせ

同じSの部分列を多重でカウントしないテクとして、Sの部分列としてS[p]を用いる場合、その直前はS[(q+1)]...S[(p-1)]のいずれかの文字である場合のみカウントするというテクがある。
(qはS[q]=S[p]となる最大のq)

よってdp(p,t)は以下のDPで求められる。前半のdp(p,t-1)は今ある末尾のS[p]を1文字余分に繰り返す場合である。
sumの部分はうまく累積和をとればO(1)で求められるので、全体でO(|S|^2)で済む。
dp(p,t) = dp(p,t-1) + sum_{q＜x＜p} dp(x,t-1)

int N;
string S;
int dp[5050][5050];
int sum[5050][5050];
int pre[28];
int mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	
	for(i=1;i<=N;i++) {
		sum[i][0]=1;
		int c = S[i-1]-'a';
		for(j=1;j<=N;j++) {
			dp[i][j]=((ll)dp[i][j-1]+sum[i][j-1]-sum[pre[c]][j-1]+mo)%mo;
			sum[i+1][j]=(sum[i][j]+dp[i][j])%mo;
		}
		pre[c]=i+1;
	}
	
	cout<<sum[N+1][N]%mo<<endl;
	
}

まとめ

最初O(w|S|^2) (wはアルファベット数)のコードを書いて見事にTLEした。