#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;
int N,K;
string S;
const long long MOD=19930726;
long long pow(long long x,long long k)
{
long long res=1;
while(k){
if(k&1)res=res*x%MOD;
x=x*x%MOD;
k>>=1;
}
return res;
}
string Ne;
int f[2000015];
int sum[1000005];
void Manacher()
{
Ne+="?!";
for(int i=0;i<S.size();i++)
Ne+=S[i],Ne+='!';
Ne+='~';
int mx=0,id=0;
for(int i=1;i<Ne.size()-1;i++){
f[i]=i<=mx?min(f[id*2-i],mx-i):1;
while(Ne[i-f[i]]==Ne[i+f[i]])
f[i]++;
if(mx<i+f[i]){
id=i;
mx=i+f[i];
}
}
for(int i=1;i<Ne.size()-1;i++)
if(Ne[i]!='!')sum[f[i]-1]++;
for(int i=N;i>0;i--)
sum[i]+=sum[i+2];
return ;
}
int main()
{
cin>>N>>K>>S;
Manacher();
long long ans=1;
for(int i=N;i>0;i--){
if(K<=0)break;
if(sum[i]){
if(K>sum[i])ans=(ans*pow(i,sum[i]))%MOD;
else ans=(ans*pow(i,K))%MOD;
K-=sum[i];
}
}
printf("%lld",ans);
return 0;
}
by Cptraser @ 2018-04-03 10:02:04
```cpp
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;
int N,K;
string S;
const long long MOD=19930726;
long long pow(long long x,long long k)
{
long long res=1;
while(k){
if(k&1)res=res*x%MOD;
x=x*x%MOD;
k>>=1;
}
return res;
}
string Ne;
int f[2000015];
int sum[1000005];
void Manacher()
{
Ne+="?!";
for(int i=0;i<S.size();i++)
Ne+=S[i],Ne+='!';
Ne+='~';
int mx=0,id=0;
for(int i=1;i<Ne.size()-1;i++){
f[i]=i<=mx?min(f[id*2-i],mx-i):1;
while(Ne[i-f[i]]==Ne[i+f[i]])
f[i]++;
if(mx<i+f[i]){
id=i;
mx=i+f[i];
}
}
for(int i=1;i<Ne.size()-1;i++)
if(Ne[i]!='!')sum[f[i]-1]++;
for(int i=N;i>0;i--)
sum[i]+=sum[i+2];
return ;
}
int main()
{
cin>>N>>K>>S;
Manacher();
long long ans=1;
for(int i=N;i>0;i--){
if(K<=0)break;
if(sum[i]){
if(K>sum[i])ans=(ans*pow(i,sum[i]))%MOD;
else ans=(ans*pow(i,K))%MOD;
K-=sum[i];
}
}
printf("%lld",ans);
return 0;
}
```
by Cptraser @ 2018-04-03 10:02:23
同问
by 阑珊念经 @ 2018-06-12 20:42:08
k最后一个点爆int 了。。。
by swhsz @ 2018-06-23 17:23:09