CSAcademy Round #57 : D. Distinct Palindromes

Eに手こずってちょっと順位が下がった。
https://csacademy.com/contest/round-57/task/distinct-palindromes/

問題

文字列Sが与えられる。
Sの部分文字列のうち、uniqueな回文は何通りあるか。

解法

uniqueな部分列の数え上げ問題はO(|S|w) (wは文字種類数)で解ける典型DP問題。
S[i]=S[j]のとき、以下を考える。
f(i.j) := S[i],S[j]を両端とする部分文字列のうちuniqueな回文の数

ある文字cについて、S[i]の後ろにある最も近い物をS[x]、S[j]の前にある最も近い物をS[y]とすると
f(i,j) += 1 + f(x,y)
となるので、これを用いて計算していこう。(1足すは中央が1文字の場合)
最初にダミーの文字を先頭と末尾に追加しておくと、f(0,|S|-1)が解となるのでわかりやすい。

ll memo[1010][1010];
ll mo=1000000007;

int ri[1010][27];
int le[1010][27];

int N;
string S;

ll hoge(int L,int R) {
	if(memo[L][R]>=0) return memo[L][R];
	
	ll ret=1;
	int i;
	FOR(i,26) if(ri[L][i]<R && le[R][i]>L) {
		ret++;
		if(ri[L][i]<le[R][i]) ret+=hoge(ri[L][i],le[R][i]);
	}
	return memo[L][R]=ret%mo;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	S=(char)('a'+26)+S+(char)('a'+26);
	N=S.size();
	
	MINUS(memo);
	
	FORR(c,S) c-='a';
	FOR(i,27) ri[N-1][i]=N, le[0][i]=-1;
	for(i=N-2;i>=0;i--) {
		FOR(j,27) {
			if(S[i+1]==j) ri[i][j]=i+1;
			else ri[i][j]=ri[i+1][j];
		}
	}
	for(i=1;i<N;i++) {
		FOR(j,27) {
			if(S[i-1]==j) le[i][j]=i-1;
			else le[i][j]=le[i-1][j];
		}
	}
	
	cout<<(hoge(0,N-1)+mo-1)%mo<<endl;
}

まとめ

部分列の数え上げな時点で解法は割とすぐ思いつけた。