题目链接：https://www.luogu.com.cn/problem/P1659
思路：
首先跑一遍Manacher，用$cnt_i$记录长为$i$的回文串有多少个。
所记录的$cnt$并不是最终的$cnt$，如$cnt_1$在$cnt_2$中也有，可用$sum=cnt_1+cnt_2$，然后长度为$i$的回文串实际有$sum$个，这就是下文中是$i^{sum}$的原因。
然后我们从$n$~$1$枚举（降序）：
如果$cnt_i$中的$i$是偶数，则continue
如果是奇数，那么更新答案$ans=ans imes i^{sum}$，注意判断$sum$与$k$的大小关系，并用快速幂
AC代码：
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 typedef long long ll; 7 const int N=1100000; 8 const ll mod=19930726; 9 10 char str[N],s[N*2]; 11 int r[N*2]; 12 ll cnt[N]; 13 14 void manacher(int len){ 15 int t=0; 16 s[0]='$'; s[++t]='#'; 17 for(int i=1;i<=len;i++){ 18 s[++t]=str[i]; 19 s[++t]='#'; 20 } 21 int pos=0,mx=0; 22 for(int i=1;i<=t;i++){ 23 if(i>mx) r[i]=1; 24 else r[i]=min(r[2*pos-i],mx-i); 25 while(i-r[i]>=1&&i+r[i]<=t&&s[i-r[i]]==s[i+r[i]]) r[i]++; 26 if(i+r[i]>mx){ 27 pos=i; 28 mx=i+r[i]; 29 } 30 cnt[r[i]-1]++; 31 } 32 } 33 34 ll qsm(ll a,ll b){ 35 ll ans=1; 36 while(b){ 37 if(b%2) ans=ans*a%mod; 38 a=a*a%mod; 39 b=b/2; 40 } 41 return ans; 42 } 43 44 int main(){ 45 int n; 46 ll k; 47 scanf("%d%lld",&n,&k); 48 scanf("%s",str+1); 49 manacher(strlen(str+1)); 50 ll sum=0,ans=1; 51 for(int i=n;i>=1;i--){ 52 if(i%2==0) continue; 53 sum+=cnt[i]; 54 if(sum<=k){ 55 ans=ans*qsm(ll(i),sum)%mod; 56 k-=sum; 57 } 58 else{ 59 ans=ans*qsm(ll(i),k)%mod; 60 k=0; break; 61 } 62 } 63 if(k>0) printf("-1 "); 64 else printf("%lld ",ans); 65 return 0; 66 }