bzoj 2160 拉拉队排练

Posted on | Views:

$Manacher$ + 差分维护数列.

首先将字符串添加特殊字符,利用 $Manacher$ 算法求出每个位置的回文半径 $R(i)$ .

维护一个 $cnt(i)$ 表示原串中长度为 $i$ 的回文串数目.

由于只考虑奇回文串,所以枚举时只处理字母作为回文中心的贡献.

若第 $i$ 个位置是字母,则它在原串中对应的奇回文串的长度分别是 $1,3,5,\dots,R(i)-1$ .

给 $1\sim R(i)-1$ 的所有 $cnt$ 都 $+1$ ,可以用差分来维护.

最后统计答案时,从大到小枚举长度,只将奇数长度计入贡献.

时间复杂度 $O(n\log n)$ .

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
	ll out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=19930726;
int mul(int a,int b)
{
	return 1LL * a * b % P;
}
int fpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=mul(res,a);
		a=mul(a,a);
		b>>=1;
	}
	return res;
}
const int MAXN=2e6+10;
char s[MAXN],buf[MAXN];
int n,R[MAXN],cnt[MAXN];
void Manacher()
{
	buf[0]='$';
	for(int i=1;i<=n;++i)
	{
		buf[2*i-1]='#';
		buf[2*i]=s[i];
	}
	buf[2*n+1]='#';
	buf[2*n+2]='@';
	//1~2n+1
	int mx=1,p=1;
	R[1]=1;
	for(int i=2;i<=2*n+1;++i)
	{
		int f=1;
		int j=2*p-i;
		if(mx<i)
			R[i]=1;
		else if(mx-i>R[j])
			R[i]=R[j],f=0;
		else
			R[i]=mx-i+1;
		if(f)
			while(buf[i+R[i]]==buf[i-R[i]])
				++R[i];
		if(i+R[i]-1>mx)
			mx=i+R[i]-1,p=i;
		if('a'<=buf[i] && buf[i]<='z')
			++cnt[1],--cnt[R[i]];
	}
}
ll k;
int main()
{
	n=read(),k=read();
	scanf("%s",s+1);
	Manacher();
	int ans=1;
	for(int i=1;i<=n;++i)
		cnt[i]+=cnt[i-1];
	for(int i=n;i>=1;--i)
		if(cnt[i] && (i&1))
		{
			if(k>cnt[i])
			{
				ans=mul(ans,fpow(i,cnt[i]));
				k-=cnt[i];
			}	
			else
			{
				ans=mul(ans,fpow(i,k));
				printf("%d\n",ans);
				return 0;
			}
		}
	puts("-1");
	return 0;
}