艾利斯顿商学院篮球队要参加一年一度的市篮球比赛了。拉拉队是篮球比赛的一个看点，好的拉拉队往往能帮助球队增加士气，赢得最终的比赛。所以作为拉拉队队长的楚雨荨同学知道，帮助篮球队训练好拉拉队有多么的重要。拉拉队的选拔工作已经结束，在雨荨和校长的挑选下，n位集优秀的身材、舞技于一体的美女从众多报名的女生中脱颖而出。这些女生将随着篮球队的小伙子们一起，和对手抗衡，为艾利斯顿篮球队加油助威。一个阳光明媚的早晨，雨荨带领拉拉队的队员们开始了排练。n个女生从左到右排成一行，每个人手中都举了一个写有26个小写字母中的某一个的牌子，在比赛的时候挥舞，为小伙子们呐喊、加油。雨荨发现，如果连续的一段女生，有奇数个，并且他们手中的牌子所写的字母，从左到右和从右到左读起来一样，那么这一段女生就被称作和谐小群体。现在雨荨想找出所有和谐小群体，并且按照女生的个数降序排序之后，前K个和谐小群体的女生个数的乘积是多少。由于答案可能很大，雨荨只要你告诉她，答案除以 19930726 的余数是多少就行了。
输入为标准输入。第一行为两个正整数n和K，代表的东西在题目描述中已经叙述。接下来一行为n个字符，代表从左到右女生拿的牌子上写的字母。
输出为标准输出。输出一个整数，代表题目描述中所写的乘积除以19930726的余数，如果总的和谐小群体个数小于K，输出一个整数-1。
首先我们建立回文自动机，求出每个回文串的长度和出现次数，然后遍历PAM内的节点，找到所有的长度为奇数的回文串，然后排序判断一下所有奇数回文的总数和k的关系即可，中间用快速幂优化。
A C AC AC代码：
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int MAXN = 1e6+50; const int MOD = 19930726; char s[MAXN]; LL n,k; struct Trie{ int nxt[MAXN][26],fail[MAXN],len[MAXN],cnt[MAXN]; int ans[MAXN]; int sz,lst; vector<pair<int,int> > v; inline void Init(){ fail[0] = fail[1] = 1; len[0] = 0,len[1] = -1; sz = lst = 1; s[0] = '#'; } inline void Insert(char ch,int en){ int root = lst; while(s[en]!=s[en-len[root]-1]) root=fail[root]; if(!nxt[root][ch-'a']){ len[++sz] = len[root] + 2; int tmp = fail[root]; while(s[en]!=s[en-len[tmp]-1]) tmp = fail[tmp]; fail[sz] = nxt[tmp][ch-'a']; nxt[root][ch-'a'] = sz; } lst = nxt[root][ch-'a']; cnt[lst]++; } inline LL qmi(LL a,LL b){ LL ans = 1; while(b){ if(b&1) ans = (ans*a)%MOD; a = (a*a)%MOD; b >>= 1; } return ans; } inline LL Solve(LL k){ LL sum = 0,res = 1; for(int i=sz;i>=2;i--) cnt[fail[i]] += cnt[i]; for(int i=2;i<=sz;i++) if(len[i]&1) v.push_back(make_pair(len[i],cnt[i])),sum += cnt[i]; if(sum < k) return -1; sort(v.begin(),v.end(),greater<pair<int,int> >()); for(int i=0;i<(int)v.size();i++){ if(k >= v[i].second){ k -= v[i].second; res = (res*qmi(v[i].first,v[i].second))%MOD; } else{ res = (res*qmi(v[i].first,k))%MOD; break; } } return res; } }PAM; int main(){ scanf("%lld%lld",&n,&k); scanf("%s",s+1); PAM.Init(); for(int i=1;s[i];i++) PAM.Insert(s[i],i); printf("%lld\n",PAM.Solve(k)); return 0; }