题目
回文串，当然想到manacher。俗称马拉车233。 先用manacher处理出长度为奇数的回文串有几个，再用快速幂来处理答案，算半道数学题吧233。
#include<bits/stdc++.h> #define mod 19930726 #define N 2000000 #define LL long long using namespace std; int pal[N+1]; int A[N+1]; char s[N+1]; int n; LL sum[N+1]; LL k; LL Ans; LL ksm(LL A,LL B) { LL Ans=1; while(B) { if(B&1)Ans=Ans*A%mod; A=A*A%mod; B>>=1; } return Ans; } int main() { scanf("%d%lld\n",&n,&k); scanf("%s",s); char tmp[N+1]; for(int i=0;i<n;i++) tmp[i+1]=s[i]; tmp[0]='-',tmp[n+1]='+'; int mx=0,id; for(int i=1;i<=n;i++) { if(mx>=i)pal[i]=min(pal[2*id-i],mx-i); else pal[i]=1; while(tmp[i-pal[i]]==tmp[i+pal[i]])pal[i]++; if(i+pal[i]>mx) { mx=i+pal[i]; id=i; } } for(int i=1;i<=n;i++)A[i]=pal[i]*2-1; for(int i=1;i<=n;i++)sum[A[i]]++; for(int i=2*n;i>=1;i--)sum[i-1]+=sum[i]; LL j=2*n; Ans=1; while(k) { if(j%2==0) { j--; continue; } if(k>sum[j]) { k-=sum[j]; Ans=Ans*ksm(j,sum[j])%mod; j--; } else { Ans=Ans*ksm(j,k)%mod; k=0; break; } } if(k==0)printf("%lld",Ans); else printf("-1"); return 0; }