r[i]是处理后每个字符的回文半径
r[i]-1即为处理前回文子串长度
P3805
【模板】manacher算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include<iostream>
#include<cstdio>
using namespace std;
const int P=19930726;
typedef long long LL;
char str[2000005];
int r[2000005],a[1000005];
LL sum[1000005];
int n,len;
LL k,ans=1;
void fast_pow(LL base,LL x) {
base%=P;
while (x>0) {
if (x&1) ans=ans*base%P;
base=base*base%P;
x>>=1;
}
}
void read() {
char ch;
len=1;str[1]='#';
while (ch<'a'||ch>'z') ch=getchar();
while (ch<='z'&&ch>='a') {
str[++len]=ch;
str[++len]='#';
ch=getchar();
}
str[0]='$';str[len+1]='@';
}
void manacher() {
int p=0,mx=0;
for (int i=1;i<=len;i++) {
if (mx>i) r[i]=min(r[2*p-i],mx-i);
else r[i]=1;
while (str[i+r[i]]==str[i-r[i]]) r[i]++;
if (i+r[i]>mx) p=i,mx=i+r[i];
}
}
int main() {
scanf("%d%lld",&n,&k);
read();
manacher();
for (int i=2;i<len;i+=2) a[1]++,a[r[i]]--;
for (int i=1;i<=(len>>1);i++) sum[i]=sum[i-1]+a[i];
if (!(n&1)) n--;
for (int i=n;i>0;i-=2) {
if (!sum[i]) continue;
LL tmp=min(k,sum[i]);
fast_pow(i,tmp);
k-=tmp;
if (k<=0) break;
}
if (k>0) cout<<-1;
else printf("%lld",ans);
return 0;
}
|
