记录编号	589729	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	游戏	最终得分	100
用户昵称	wdsjl	是否通过	通过
代码语言	C++	运行时间	0.816 s
提交时间	2024-07-07 15:27:50	内存使用	177.40 MiB

#include <bits/stdc++.h>
using namespace std;

const int Mod = 19930726;
const int N = 10000010;

char s[N],t[N];
long long n,k,maxx,cnt[N],ans;

long long mi(long long a,long long b){
    long long res=1,base=a,x=b;
    while(x){
        if(x&1)res=res*base%Mod;
        base=base*base%Mod;
        x/=2;
    }
    return res;
}

int main(){
    freopen("rehearse.in","r",stdin); 
    freopen("rehearse.out","w",stdout);
//    freopen
    scanf("%lld%lld",&n,&k);
    scanf("%s",&s);
    int l=strlen(s),len=0;
    t[len++]='$';
    t[len++]='#';
    for(int i=0;i<l;i++){
        t[len++]=s[i];
        t[len++]='#';
    }
    t[len]='&';
    vector<long long> d1(N);
//    for(int i=0;i<=len;i++)cout<<t[i]<<" ";
//    cout<<endl;
    for(long long i=0,l=0,r=-1;i<len;i++){
        long long k=(i>r)?1:min(d1[l+r-i],r-i+1);
        while(0<=i-k&&i+k<len&&t[i-k]==t[i+k]){
            k++;
        }
        d1[i]=k--;
        if(i+k>r){
            l=i-k;
            r=i+k;
        }
    }
    for(int i=1;i<len;i++){
        cnt[d1[i]-1]++;
//    cout<<d1[i]-1<<" ";
        maxx=max(maxx,d1[i]-1);            
    }
//    for(int i=1;i<=5;i++)cout<<cnt[i]<<" ";
//    cout<<endl;
//    cout<<maxx<<" "<<cnt[maxx]<<endl;
   ans=1;
   
   for(int i=maxx;i;i--){
       if(i%2){   
       cnt[i-2]+=cnt[i];
       long long num=cnt[i];
       if(k>num){
         ans=(ans*mi(i,num))%Mod;
         k-=num;  
       }else{
           ans=(ans*mi(i,k))%Mod;
           k=0;
           break;
       }
       }
   }
   if(k)cout<<"-1";
   else cout<<ans%Mod;
   return 0;
}