LG 1659 -- 拉拉队排练

发表于 | 更新于 | 分类于 ， | 评论数：

摘要

给出字符串求前 $K$ 长奇长回文子串长之积

是不是很简单啊

题面

BZOJ

洛谷

解

回文自动机模板

这个东西形式上和AC自动机很像，比较特殊的一点是它不判后继而是判可不可以拓展

Size 求起来也不太舒服，是沿着fail一路加上去的，理解起来就是每个末尾分开考虑

下面乱讲一波回文自动机

先说我们的目标是什么

构建一个类似Trie的东西，使得每个根到节点表示一个回文串的一半

这里就要奇偶分开，奇串要计入中间的字符

考虑尾后加一个字符，我们需要找到把它接到哪个节点的下面

就是找到以这个字符为结尾的最长回文串

容易发现回文串扣掉两端字符后还是回文串

于是我们从长到短尝试以前一个字符为结尾的回文串

类比AC自动机，这就是跳 Fail 的过程

那么只要求一下新节点的Fail就好了，就是再找一次可以拓展的位置

Code

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 <cstdio>
#include <algorithm>

using std::sort;

const int MAXN=1000011;
const int MOD=19930726;

inline int mul(const int &a, const int &b){
	return (int)((1LL*a*b)%(long long)(MOD));
}

inline int pow(int a, int k){
	int r=1;
	while(k){
		if(k&1)	r=mul(r, a);
		a=mul(a, a);
		k>>=1;
	}
	return r;
}

int N;
long long K;
char input[MAXN];
int A[MAXN];

struct Node{
	int s[26];
	int f, l, c;
} T[MAXN];

int Tcnt, Last;

int Fail(int x, const int &p){
	while(A[p-T[x].l-1]!=A[p])	x=T[x].f;
	return x;
}

struct Data{
	int l, c;
};

inline bool cmpl(const Data &A, const Data &B){
	return A.l>B.l;
} 

Data D[MAXN];
int Dc;

int main(){
	
	scanf("%d%lld", &N, &K);
	scanf("%s", input);
	for(int i=1;i<=N;++i)	A[i]=input[i-1]-'a';
	A[0]=-1;
	
	T[1].l=-1;
	T[0].f=T[1].f=1;
	Last=++Tcnt;
	for(int i=1;i<=N;++i){
		int &p=Last, &h=A[i];
		p=Fail(p, i);
		if(!T[p].s[h]){
			++Tcnt;
			T[Tcnt].f=T[Fail(T[p].f, i)].s[h];
			T[Tcnt].l=T[p].l+2;
			T[p].s[h]=Tcnt;
		}
		p=T[p].s[h];++T[p].c;
	}
	
	for(int i=Tcnt;i>=0;--i)	T[T[i].f].c+=T[i].c;
	
	for(int i=0;i<=Tcnt;++i)	if(T[i].l>0 && (T[i].l&1))	D[++Dc]=(Data){T[i].l, T[i].c};
	
	//for(int i=1;i<=Dc;++i)	printf("%d %d\n", D[i].l, D[i].c);
	
	sort(D+1, D+Dc+1, cmpl);
	
	int Ans=1;
	
	for(int i=1;i<=Dc && K>0LL;++i){
		if(K>(long long)(D[i].c)){
			Ans=mul(Ans, pow(D[i].l, D[i].c));
			K-=(long long)(D[i].c);
		}
		else{
			Ans=mul(Ans, pow(D[i].l, (int)(K)));
			K=0LL;
		}
	}
	
	if(K>0LL)	puts("-1");
	else	printf("%d\n", Ans);
	
	return 0;
}