记录编号	479059	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2011] 拉拉队排练	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	0.719 s
提交时间	2017-12-15 23:34:52	内存使用	268.30 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define mod 19930726
using namespace std;
const int maxn=1000100;
int n;
long long k;
struct poi{
	long long a,b;
	bool operator < (const poi&d)const{
		return b<d.b;
	}
};
long long fastpow(long long a,long long b){
	long long ans=1;a%=mod;
	while(b){
		if(b%2)ans*=a%mod,ans%=mod;
		a*=a%mod,a%=mod,b/=2;
	}
	return ans%mod;
}
struct PAM{
	char s[maxn];
	poi tmp[maxn];
	long long ch[maxn][30],fail[maxn],len[maxn],cnt[maxn],last,now,p;
	void newnode(int w){
		cnt[now]=0,len[now]=w,now++;
	}
	void init(){
		now=0,newnode(0),newnode(-1);
		last=p=0,s[0]=-1,fail[0]=1;
	}
	int getfail(int x){
		while(s[p-len[x]-1]!=s[p])x=fail[x];
		return x;
	}
	void extend(int x){
		p++;
		int cur=getfail(last);
		if(!ch[cur][x]){
			newnode(len[cur]+2);
			fail[now-1]=ch[getfail(fail[cur])][x];
			ch[cur][x]=now-1;
		}
		last=ch[cur][x];
		cnt[last]++;
	}
	void count(){
		for(int i=now-1;i>=0;i--){
			cnt[fail[i]]+=cnt[i],tmp[i].a=cnt[i],tmp[i].b=(len[i]%2)?len[i]:0;
		}
	}
	long long work(){
		long long ans=1;
		count();
		sort(tmp,tmp+now);
		for(int i=now-1;i>=2&&k;i--){
			int tt=min(k,tmp[i].a);
			ans*=fastpow(tmp[i].b,tt);
			ans%=mod;
			k-=tt;
		}
		if(k)ans=-1;
		return ans;
	}
}pam;
int main(){
	freopen("rehearse.in","r",stdin);
	freopen("rehearse.out","w",stdout);
	pam.init();
	scanf("%d%lld",&n,&k);
	scanf("%s",pam.s+1);
	for(int i=1;i<=n;i++)pam.extend(pam.s[i]-'a');
	printf("%lld\n",pam.work());
	return 0;
}