【[国家集训队]拉拉队排练】

这是一道大水题

首先这里只需要统计奇回文串，所以连插入特殊字符都不需要

之后我们跑一边(Manacher)的板子

搞一个后缀和数组(pre[i])，先把所有的回文半径对应过去，之后求后缀和

之后我们倒着统计就好了，每次(ans imes=i^{pre[i]})

没了

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#define re register
#define maxn 1000005
#define LL long long
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
const LL mod=19930726;
int n;
LL K;
int r[maxn];
char S[maxn];
LL pre[maxn];
inline LL quick(LL a,LL b)
{
	LL s=1;
	while(b) {if(b&1) s=s*a%mod;b>>=1,a=a*a%mod;}
	return s;
}
int main()
{
	scanf("%d%lld",&n,&K);scanf("
");
	scanf("%s",S+1);
	int R=1,mid=1;
	for(re int i=1;i<=n;i++)
	{
		if(i<=R) r[i]=min(r[(mid<<1)-i],R-i);
		for(re int j=r[i]+1;j<=i&&j+i<=n&&S[i+j]==S[i-j];j++) r[i]=j;
		if(i+r[i]>R) mid=i,R=i+r[i];
	}
	for(re int i=1;i<=n;i++) pre[r[i]]++;
	for(re int i=n;i;i--) pre[i]=pre[i+1]+pre[i];
	LL ans=1;
	for(re int i=n;i>=0;i--)
	{
		if(!pre[i]) continue;
		if(K-pre[i]>0) K-=pre[i],ans=(ans*quick(2*i+1,pre[i])%mod);
			else { ans=(ans*quick(2*i+1,K)%mod); K=0; break; }
	}
	if(K) puts("-1");
		else std::cout<<ans;
	return 0;
}