CSAcademy Round #9 : F. 101 Palindromes

変に考えすぎた。
https://csacademy.com/contest/round-9/#task/101-palindromes

問題

最大S=200桁の整数Dが与えられる。
この整数からいくつかの桁を相対的なな順序を変えず抜き取って別の整数を作った場合、以下を満たすものは何通りか。

• leading zeroは許可される。
• 回文を成している。
• M=101の倍数である。

解法

中心となる要素を定めて、左右に同じ数字を連結して回文を作ることを考えよう。
回文が奇数長なら中心は1要素、偶数長なら同じ数字の2要素とする。

以下のdpを考える。
dp(L,R,len,m) := Dの(L+1)～(R-1)桁目のうち回文となるようにlen個数字を選んだところ、それらを連結した整数を101で割った余りがmであるとき、残りDのL桁目より左側、R桁目より右側の数字を回文となるように連結する組み合わせ数。

• D[L]==D[R]なら、D[L],D[R]を回文に取り込めばよいので、dp(L-1,R-1,len+2,(m*10+D[L]*10^(len+1)+D[R])%101)を答えに加算する。
• D[L]とD[R]の少なくとも片方を回文に取り込まない場合を足しこむ。
  • dp(L-1,R,len,m)とdp(L,R+1,len,m)の和を取ると、D[L]とD[R]どちらも取り込まない場合を二重カウントするのでdp(L-1,R+1,len,m)を引く。

解法としてはこれで良いが、このままでは計算量がO(S^3*M)でTLEする。
ここで101という数字は10^4%101=1であることに留意すると、lenは実際には4で剰余を取った値だけ考えればいいので計算量を減らすことができる。

int N;
string S;
ll dp[201][201][4][101];
ll mo=1000000007;
ll momo[4] = {1,10,100,91};

ll dpdp(int L,int R,int len,int m) {
	if(L<0 || R>=N) return 0;
	len %= 4;
	ll& ret =dp[L][R][len][m];
	if(ret>=0) return ret;
	ret=0;
	
	// take
	if(S[L]==S[R]) {
		int m2=(m*10+S[R]+S[L]*momo[(len+1)%4])%101;
		if(m2==0) ret++;
		ret += dpdp(L-1,R+1,len+2,m2);
	}
	
	ret += dpdp(L-1,R,len,m);
	ret += dpdp(L,R+1,len,m);
	ret += mo-dpdp(L-1,R+1,len,m);
	ret %= mo;
	return ret;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(dp);
	
	cin>>N>>S;
	ll ret=0;
	FORR(c,S) c-='0';
	
	FOR(y,N) {
		FOR(x,y) if(S[x]==S[y]) {
			if(S[x]==0) ret++;
			ret += dpdp(x-1,y+1,2,S[x]*10+S[y]);
		}
		if(S[y]==0) ret++;
		ret += dpdp(y-1,y+1,1,S[y]);
	}
	cout<<ret%mo<<endl;
}

まとめ

違う方法でやろうとしていつまでも微妙に解が合わなかった。