Problem

艾利斯顿商学院篮球队要参加一年一度的市篮球比赛了。拉拉队是篮球比赛的一个看点，好的拉拉队往往能帮助球队增加士气，赢得最终的比赛。所以作为拉拉队队长的楚雨荨同学知道，帮助篮球队训练好拉拉队有多么的重要。

拉拉队的选拔工作已经结束，在雨荨和校长的挑选下，n 位集优秀的身材、舞技于一体的美女从众多报名的女生中脱颖而出。这些女生将随着篮球队的小伙子们一起，和对手抗衡，为艾利斯顿篮球队加油助威。

一个阳光明媚的早晨，雨荨带领拉拉队的队员们开始了排练。n 个女生从左到右排成一行，每个人手中都举了一个写有 26 个小写字母中的某一个的牌子，在比赛的时候挥舞，为小伙子们呐喊、加油。

雨荨发现，如果连续的一段女生，有奇数个，并且他们手中的牌子所写的字母，从左到右和从右到左读起来一样，那么这一段女生就被称作和谐小群体。

现在雨荨想找出所有和谐小群体，并且按照女生的个数降序排序之后，前 K 个和谐小群体的女生个数的乘积是多少。由于答案可能很大，雨荨只要你告诉她，答案除以 19930726 的余数是多少就行了。

Solution

先用 manacher 处理出回文子串的最长长度，即 p 数组，将回文子串长度统计。

然后对于一个以 x 为中心的长度为奇数的回文串，将两边删去，仍然以 x 为中心，因此是唯一的。

以此，做前缀和统计就行。假设某中心回文子串最长长度为 x，则 1~x 的长度为奇数的回文子串的个数都 +1。由于是省选题，不做过多的赘述。

由于没看清题面，所以我把偶数也算上了，其实只要分开统计就行了。

以及要用上快速幂。

Code

// Code by ajcxsu
// Problem: laladui

#include<bits/stdc++.h>
#define MOD (19930726ll)
using namespace std;
typedef long long ll;

const int N=1000010;
ll cnta[N],cntb[N]; // 奇偶分开计数
int p[2*N];
string str;
string y;

ll dpow(ll x,ll y) {
    ll ret=1;
    while(y) {
        if(y&1ll) ret=(ret*x)%MOD;
        x=(x*x)%MOD, y>>=1ll;
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    ll n,k;
    cin>>n>>k;
    cin>>str;
    y="#";
    for(int i=0;i<n;i++) y+='#', y+=str[i];
    y+='#';
    int mid=0,mr=0,x;
    p[0]=1;
    for(int i=1,len=y.size();i<len-1;i++) {
        p[i]=mr>i?min(p[2*mid-i],mr-i):1;
        while(y[i+p[i]]==y[i-p[i]]) p[i]++;
        if(i+p[i]>mr) mr=i+p[i], mid=i;
        x=p[i]-1;
        if(x&1) cnta[x]++;
        else cntb[x]++;
    }
    ll cnt=0,ans=1,a=0,b=0;
    for(ll i=n;i>=0;i--) {
        if(!i) cout<<-1<<endl, exit(0);
        if(i&1ll) {
            if(cnt+a+cnta[i]>k) { ans=(ans*dpow(i,k-cnt)) % MOD; break; }
            else {
                a+=cnta[i], cnt+=a;
                ans=(ans*dpow(i,a)) % MOD;
            }
        }
        // else {
        //     if(cnt+b+cntb[i]>k) { ans=(ans*dpow(i,k-cnt)) % MOD; break; }
        //     else {
        //         b+=cntb[i], cnt+=b;
        //         ans=(ans*dpow(i,b)) % MOD;
        //     }
        // } 没看清题导致多加了一个偶数情况，其实如果有偶数情况分开统计就行
    }

    cout<<ans<<endl;
    return 0;
}