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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
#include<cstring>
#include<iostream>
#define CK 19930726
using namespace std;
int n,i,cnt;
long long k;
char P;
char a[2000010],b[2000010];
int p[2000010],d[2000010],c[2000010];
struct {
int l,r,d,z;
}t[5000020];
inline int min(int a,int b){return (a<b)?a:b;}
inline void Manacher(){
int i=0,mx=0,id=0;
for (i=1;i<=cnt-1;i++){
if (i<mx) p[i]=min(p[2*id-i],mx-i); else p[i]=1;
while (a[i+p[i]]==a[i-p[i]]) p[i]++;
if (p[i]+i>mx) mx=p[i]+i,id=i;
}
return;
}
void Maketree(int x,int low,int high){
int Mid=(low+high)>>1;
t[x].l=low; t[x].r=high; t[x].d=0; t[x].z=0;
if (low==high) return;
Maketree(x*2,low,Mid); Maketree(x*2+1,Mid+1,high);
return;
}
void Add(int x,int low,int high){
int Mid=(t[x].l+t[x].r)>>1;
if (t[x].l==t[x].r) {t[x].d++; return;}
if (t[x].l==low&&t[x].r==high) {t[x].z++; return;}
if (high<=Mid) Add(x*2,low,high); else
if (low>Mid) Add(x*2+1,low,high); else {
Add(x*2,low,Mid); Add(x*2+1,Mid+1,high);
}
return;
}
int Query(int x,int low){
int Mid=(t[x].l+t[x].r)>>1;
if (t[x].l==t[x].r) return t[x].d+t[x].z;
if (t[x].z!=0) {
t[x*2].z+=t[x].z; t[x*2+1].z+=t[x].z;
t[x].z=0;
}
if (low<=Mid) return Query(x*2,low); else
return Query(x*2+1,low);
}
inline long long EF(int x){
int i=0; long long q=0;
for (i=1;i<=n;i++) if (c[i]>=x) q+=c[i]-x+1;
return q-k;
}
inline long long Solve(int g){
long long i=0,Ans=1,x=0,s=0;
for (i=g;i<=n/2+2;i++) s+=d[i];
if (s>k) d[g]-=s-k;
for (i=g;i<=n/2+2;i++)
if (d[i]!=0) {
x=i*2-1; if (x==1) continue;
while (d[i]){
if (d[i]&1) Ans=(Ans*x)%CK;
x=(x*x)%CK; d[i]/=2;
}
}
return Ans;
}
inline void Work(){
int i=0,low=0,high=0,mid=0,ans=0;
for (i=1;i<=cnt;i++) if (a[i]!='%') c[++c[0]]=p[i]-1;
for (i=1;i<=n;i++) c[i]=(c[i]+1)/2;
low=1; high=1000000;
while (low<=high) {
mid=(low+high)>>1;
if (EF(mid)>=0) ans=mid,low=mid+1; else high=mid-1;
}
Maketree(1,1,n/2+10);
for (i=1;i<=n;i++)
if (c[i]>=ans) Add(1,ans,c[i]);
for (i=1;i<=n/2+1;i++) d[i]+=Query(1,i);
printf("%lldn",Solve(ans));
return;
}
int main(){
freopen("rehearse.in","r",stdin);
freopen("rehearse.out","w",stdout);
scanf("%d%lld",&n,&k);
for (i=1;i<=n;i++){
P=getchar(); while (P<97) P=getchar();
b[i]=P;
}
for (i=1;i<=n;i++) a[++cnt]='%',a[++cnt]=b[i];
a[++cnt]='%'; a[0]='$'; Manacher();
Work();
return 0;
}
|
近期评论