记录编号	589751	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	游戏	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	0.036 s
提交时间	2024-07-07 16:33:20	内存使用	7.63 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const long long mod=19930726;
char s[2000010];
long long ans=1,sum,k,c[2000010],p[2000010],mx,n,id;
long long fpow(long long a,long long b)
{
    long long zx=1;
    while(b)
    {
        if(b&1) zx=zx*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return zx;
}
void Manacher()
{
    for(int i=1;i<=n;i++)
    {
        if(i<mx) p[i]=min(p[id*2-i],(long long)mx-i);
        else p[i]=1;
        while(s[i+p[i]]==s[i-p[i]])
        {
            p[i]++;
        }
        if(i+p[i]>mx)
        {
            mx=i+p[i];
            id=i;
        }
        c[p[i]*2-1]++;
    }
}
int main()
{
    freopen("rehearse.in","r",stdin);
    freopen("rehearse.out","w",stdout);
    scanf("%lld%lld",&n,&k);
    s[0]='~';
    scanf("%s",s+1);
    Manacher();
    if(n%2!=1) n--;
    for(int i=n;i>=1;i-=2)
    {
        sum+=c[i];
        if(sum>k)
        {
            ans*=fpow(i,k);
            ans%=mod;
            break;
        }
        else
        {
            ans*=fpow(i,sum);
            ans%=mod;
            k-=sum;
        }
    }
    if(sum<k) printf("-1");
    else printf("%lld",ans);
    return 0;
}