kmjp's blog

競技プログラミング参加記です

CSAcademy Round #33 : E. Free Palindromes

考察が足りなかった…。
https://csacademy.com/contest/round-33/task/free-palindromes/

問題

K種類の文字があるとする。
これらで構成されるN文字の回文を成す文字列で、2~(N-1)文字の部分文字列が回文でないものは何通りあるか。

解法

N文字の回文中で、2文字以上のprefix x文字が回文である場合、xはceil(N/2)以下である。
以下Nが偶数の時を考える。y=x-N/2を考えると、N文字全体は回文なので中心2y文字は回文である。
また先頭x文字は回文なので先頭2y文字も回文である。よって先頭x文字が回文なら先頭2y文字も回文であるはずなので、xが最小ではないことになってしまう。

z≦ceil(N/2)の時、N文字が回文でかつprefix z文字も回文であるものは K^{\lceil \frac{z}{2} \rceil} \times K^{\lceil \frac{N - 2z}{2} \rceil}である。

よって以下を考える。

  • f(i) = K^ceil(i/2) : i文字の文字列の回文の種類
  • g(i) : i文字の回文であり、2~(i-1)文字のprefixが回文でないようなもの
    • 求める解はg(N)である。


このとき \displaystyle g(i) = f(i) - \sum_{j=2}^{N-1} g(j) \times K^{\lceil \frac{i-2j}{2} \rceil}となる。
sumの部分を累積和を使っていけばg(i)が順次O(1)で計算できるので、g(N)がO(N)で計算できる。

int N,K;
ll mo=1000000007;
ll dp[101010];
ll S[101010];
ll pk[101010];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N>>K;
	
	pk[0]=1;
	FOR(i,101000) pk[i+1]=pk[i]*K%mo;
	
	for(i=1;i<=N;i++) {
		dp[i]=(mo+pk[(i+1)/2]-S[(i+1)/2]*pk[(i+1)/2]%mo)%mo;
		if(i>=2) S[i]= (S[i-1] + dp[i]*modpow(pk[i]))%mo;
	}
	cout<<dp[N]%mo<<endl;
	
	
}

まとめ

回文苦手。