记录编号	533009	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2011] 拉拉队排练	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	1.439 s
提交时间	2019-06-11 18:24:57	内存使用	115.99 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e6+100,P=19930726;
struct node{
    int len,fail,son[26],siz;
};
node prt[maxn]; 
int n,last,len,num;
ll ans=1,k;
char s[maxn];
ll ksm(ll x,ll y)
{
	ll res=1;
	for (;y;y>>=1,x=x*x%P)
	if (y&1) res=res*x%P;
	return res;
}
bool cmp(node x,node y)
{
    return x.len>y.len;
}
int getfail(int x)
{
    while(s[n-prt[x].len-1]!=s[n]) x=prt[x].fail;
    return x;
}
void extend(int x)
{
    int cur=getfail(last);
    if(!prt[cur].son[x])
	{
        int now=++num;
        prt[now].len=prt[cur].len+2;
        prt[now].fail=prt[getfail(prt[cur].fail)].son[x];
        prt[cur].son[x]=now;
    }
    prt[prt[cur].son[x]].siz++;
    last=prt[cur].son[x];
}
int main()
{
    freopen("rehearse.in","r",stdin);
    freopen("rehearse.out","w",stdout);
	scanf("%d%d",&len,&k);
    scanf("%s",s);
    last=num=1,prt[1].len=-1;
    prt[0].fail=prt[1].fail=1;
    for(n=0;n<len;n++) extend(s[n]-'a');
    for(int i=num;i>=2;i--)
    prt[prt[i].fail].siz+=prt[i].siz,prt[prt[i].fail].siz%=P;
    sort(prt+1,prt+num+1,cmp);
    int now=1;
    while(k){
        if(now>num){printf("-1\n");return 0;}
        if(prt[now].len%2==0){now++;continue;}
        if(prt[now].siz<k)
		{
            k-=prt[now].siz;
            ans*=ksm(prt[now].len,prt[now].siz)%P;
            ans%=P;
            now++;
        }
        else
		{
            ans*=ksm(prt[now].len,k)%P;
            ans%=P;
            k=0;
        }
    }
    printf("%lld\n",ans);
    return 0;
}