考察が足りなかった…。
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文字も回文であるものはである。
よって以下を考える。
- f(i) = K^ceil(i/2) : i文字の文字列の回文の種類
- g(i) : i文字の回文であり、2~(i-1)文字のprefixが回文でないようなもの
- 求める解はg(N)である。
このときとなる。
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; }
まとめ
回文苦手。