思路

求出cnt和len之后，直接乘起来即可

代码

#include 
    
     #include 
     
      #include 
      
       #define int long longusing namespace std;int Nodecnt,last,n,k;signed trans[1001000][26],fail[1001000];struct Node{    signed len,cnt;    bool operator < (const Node &b) const{        return len>b.len;    }}a[1001000];char s[1001000];const int MOD = 19930726;int pow(int a,int b){    int ans=1;    while(b){        if(b&1)            ans=(1LL*ans*a)%MOD;        a=(1LL*a*a)%MOD;        b>>=1;    }    return ans;}int New_state(int _len){    a[Nodecnt].len=_len;    return Nodecnt++;}int get_fail(int p,int n){    while(s[n]!=s[n-a[p].len-1])        p=fail[p];    return p;}void insert(int n){    int cur=get_fail(last,n);    if(!trans[cur][s[n]]){        int t=New_state(a[cur].len+2);        fail[t]=trans[get_fail(fail[cur],n)][s[n]];        trans[cur][s[n]]=t;    }    a[trans[cur][s[n]]].cnt++;    last=trans[cur][s[n]];}signed main(){    // freopen("test.in","r",stdin);    int ans=1;    scanf("%lld %lld",&n,&k);    scanf("%s",s+1);    s[0]=-1;    New_state(0);    fail[0]=1;    New_state(-1);    last=0;    for(int i=1;i<=n;i++){        s[i]-='a';        insert(i);    }    for(int i=Nodecnt-1;i>=0;i--)        a[fail[i]].cnt+=a[i].cnt;    sort(a,a+Nodecnt);    for(int i=0;i
       
        0;i++){        if(a[i].len%2){            ans=(1LL*ans*pow(a[i].len,min(1LL*a[i].cnt,k)))%MOD;            k-=a[i].cnt;        }    }    printf("%lld\n",ans);    return 0;}