记录编号	295102	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2011] 拉拉队排练	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.442 s
提交时间	2016-08-13 13:51:16	内存使用	18.40 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2000010;
int n,i,j,p[N],Ws[N];
char s[N],t[N];
long long ans,k;
void Manacher(){
	int mx=0,id=0;p[0]=1;
	long long sum=0;
	for (int i=1;i<=n;i++){
		if (mx>i) p[i]=min(p[2*id-i],mx-i);
		while (s[i+p[i]]==s[i-p[i]]) p[i]++;
		if (i+p[i]>mx) mx=i+p[i],id=i;
		sum+=p[i];
	}
	if (sum<k){
		puts("-1");exit(0);
	}
}
int erfen(int l,int r){
	if (l==r) return l;
	long long sum=0;
	int mid=(l+r)/2;
	for (int i=1;i<=n;i++)
	if (p[i]>=mid+1) sum+=p[i]-mid;
	return sum>=k?erfen(mid+1,r):erfen(l,mid);
}
const int P=19930726;
long long mi(long long x,long long y){
	long long ans=1;
	while (y){
		if (y&1) ans=(ans*x)%P;
		x=(x*x)%P;y/=2;
	}
	return ans;
}

int main()
{
	freopen("rehearse.in","r",stdin);
	freopen("rehearse.out","w",stdout);
	scanf("%d%lld",&n,&k);
	scanf("%s",s+1);
	s[0]=' ';
	Manacher();
	int level=erfen(1,n);
	long long sum=0;
	for (int i=1;i<=n;i++)
	if (p[i]>level){
		sum+=p[i]-level;
		Ws[p[i]]++;
	}
	ans=mi(level*2-1,k-sum);
	for (int i=n;i>level;i--){
		Ws[i]+=Ws[i+1];
		ans=(ans*mi(i*2-1,Ws[i]))%P;
	}
	printf("%lld\n",ans);
	return 0;
}