解析
- 题意简单来说就是找所有回文串,按长度从大到小排序后将前K个长度乘起来
- 看到回文串问题,由于我太菜了,只会Manacher算法,所以只能用Manacher来做这道题了
- 注意K的数据范围 1e12,long long !!!
- 快速幂求结果
Code
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
const int N=1000005;
const int mod=19930726;
int n,t,len,r[2*N];
char la[N],law[2*N];
LL k,sum,ans=1,p[N],bar[N];
void pre_deal()
{
law[0]='!';
law[1]='#';
len=2;
for(int i=1;i<=n;i++)
{
law[len++]=la[i];
law[len++]='#';
}
law[len]='?';
return;
}
void manacher()
{
pre_deal();
int id,mx=0;
for(int i=1;i<len;i++)
{
if(i>=mx) r[i]=1;
else r[i]=min(r[2*id-i],mx-i);
while(law[i-r[i]]==law[i+r[i]]) r[i]++;
if(mx<i+r[i])
{
id=i;
mx=i+r[i];
}
if(law[i]!='#') p[++t]=r[i]-1;
}
return;
}
LL quick_pow(LL a,LL b)
{
LL ret=1;
while(b)
{
if(b&1) ret=ret*a%mod;
a=a*a%mod;
b>>=1;
}
return ret;
}
int main()
{
scanf("%d%lld",&n,&k);
cin>>(la+1);
manacher();
LL lat=0;
for(int i=1;i<=t;i++)
{
sum+=p[i]/2+1;
bar[p[i]]++;
lat=max(lat,p[i]);
}
if(sum<k)
{
puts("-1");
return 0;
}
LL num=0;
while(1)
{
if(num+bar[lat]>=k)
{
ans=(ans*quick_pow(lat,k-num))%mod;
break;
}
ans=(ans*quick_pow(lat,bar[lat]))%mod;
num+=bar[lat];
bar[lat-2]+=bar[lat];
lat-=2;
}
printf("%lld\n",ans);
return 0;
}