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

#include<bits/stdc++.h>
using namespace std;
const long long N=1000010,MOD=19930726;
long long n,k;
string s;
long long d[N];
long long t[N];
long long ans=1;
long long qpow(long long a,long long b)
{
    long long x=1;
    while(b)
    {
        if(b&1) x=(x*a)%MOD;
        a=(a*a)%MOD;
        b>>=1;
    }
    return x;
}
int main()
{
    freopen("rehearse.in","r",stdin);
    freopen("rehearse.out","w",stdout);
    scanf("%lld%lld",&n,&k);
    cin>>s;
    for(long long i=0,l=0,r=-1;i<n;i++)
    {
        long long k=i>r?1:min(d[l+r-i],r-i+1ll);
        while(i-k>=0&&i+k<n&&s[i-k]==s[i+k]) k++;
        d[i]=k--;
        if(i+k>r)
        {
            l=i-k;
            r=i+k;
        }
        t[2*d[i]-1]=t[2*d[i]-1]+1;
    }
    for(long long i=n%2?n:n-1;i>=1;i-=2)
    {
        if(k<=t[i])
        {
            ans=(ans*qpow(i,k))%MOD;
            printf("%lld",ans);
            return 0;
        }
        ans=(ans*qpow(i,t[i]))%MOD;
        k-=t[i];
        t[i-2]+=t[i];
    }
    if(k) printf("-1");
    return 0;
}