题目链接
思路：先记录一下每种回文串出现了几次，这是pam的常规操作，然后按长度sort一下，找前k个奇数长度的回文串，快速幂算一下就行了
#include<bits/stdc++.h> using namespace std; const int N = 1e6+100; typedef long long ll; char in[N]; int fail[N],len[N],ch[N][26]; int last,j,n,cnt=1;//cnt从1开始 ll k,ans=1,num[N]; const ll mod = 19930726; struct node{ ll num; int len,id; }s[N]; bool cmp(node a,node b){ return a.len>b.len; } ll qpow(ll a,ll b){ ll ret = 1; while(b){ if(b&1) ret = (a%mod)*(ret%mod)%mod; a = (a%mod)*(a%mod)%mod; b>>=1; } return ret%mod; } int main(){ scanf("%d%lld",&n,&k); scanf("%s",in+1); in[0]='#'; fail[0]=1;len[1]=-1;//初始化 for(int i=1;i<=n;i++) { while(in[i-len[last]-1]!=in[i]) last=fail[last];//匹配（后面会详细解说） //printf("last = %d\n",last); if(!ch[last][in[i]-'a'])//新建节点 { len[++cnt]=len[last]+2;//长度比原来多2 j=fail[last]; while(in[i-len[j]-1]!=in[i]) j=fail[j]; fail[cnt]=ch[j][in[i]-'a']; ch[last][in[i]-'a']=cnt; } num[last=ch[last][in[i]-'a']]++; } for(int i = cnt; i >= 2; i--) num[fail[i]]+=num[i]; for(int i = 2; i <= cnt; i++) s[i].num = num[i],s[i].id = i,s[i].len = len[i]; sort(s+2,s+cnt+1,cmp); for(int i = 2; i <= cnt; i++){ //printf("i = %d len[i] = %d num[i] = %lld\n",i,s[i].len,s[i].num); if(s[i].len&1){ //printf("i = %d s[i].num = %lld s[i].len = %d k = %lld\n",i,s[i].num,s[i].len,k); if(k>s[i].num*1LL) ans=ans*qpow(s[i].len*1LL,s[i].num)%mod,k-=s[i].num*1LL; else ans=ans*qpow(s[i].len*1LL,k)%mod,k = 0; if(k==0) break; } } printf("%lld\n",k>0?0:ans); return 0; }
