「BZOJ2160」拉拉队排练

Description

艾利斯顿商学院篮球队要参加一年一度的市篮球比赛了。拉拉队是篮球比赛的一个看点,好的拉拉队往往能帮助球队增加士气,赢得最终的比赛。所以作为拉拉队队长的楚雨荨同学知道,帮助篮球队训练好拉拉队有多么的重要。

拉拉队的选拔工作已经结束,在雨荨和校长的挑选下,nn位集优秀的身材、舞技于一体的美女从众多报名的女生中脱颖而出。这些女生将随着篮球队的小伙子们一起,和对手抗衡,为艾利斯顿篮球队加油助威。

一个阳光明媚的早晨,雨荨带领拉拉队的队员们开始了排练。nn个女生从左到右排成一行,每个人手中都举了一个写有2626个小写字母中的某一个的牌子,在比赛的时候挥舞,为小伙子们呐喊、加油。

雨荨发现,如果连续的一段女生,有奇数个,并且他们手中的牌子所写的字母,从左到右和从右到左读起来一样,那么这一段女生就被称作和谐小群体。

现在雨荨想找出所有和谐小群体,并且按照女生的个数降序排序之后,前K个和谐小群体的女生个数的乘积是多少。由于答案可能很大,雨荨只要你告诉她,答案除以1993072619930726的余数是多少就行了。

Input

第一行为两个正整数nnKK,代表的东西在题目描述中已经叙述。

接下来一行为nn个字符,代表从左到右女生拿的牌子上写的字母。

Output

输出一个整数,代表题目描述中所写的乘积除以1993072619930726的余数,如果总的和谐小群体个数小于KK,输出一个整数1-1

Sample Input

1
2
5 3
ababa

Sample Output

1
45

HINT

总共2020个测试点,数据范围满足:

nK1101023100100471,0001,0008100,000=1911100,000100,0001214100,0001,000,000,000,0001517500,0001,000,000,000,000181,000,000=1191,000,0001,000,000201,000,0001,000,000,000,000\begin{array}{|c|c|c|} \hline 测试点 & n & K \\ \hline 1&10&10 \\ \hline 2\sim3&100&100 \\ \hline 4\sim7&1,000&1,000\\ \hline 8&100,000&= 1\\ \hline 9\sim11&100,000&100,000\\ \hline 12\sim14&100,000&1,000,000,000,000\\ \hline 15\sim17&500,000&1,000,000,000,000\\ \hline 18&1,000,000&= 1\\ \hline 19&1,000,000&1,000,000\\ \hline 20&1,000,000&1,000,000,000,000 \\\hline \end{array}

Solution

直接manachar求出所有回文串,最后按照长度后缀和。因为最后的kk大,所以快速幂算统一长度的个数。

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 2100000;
int n;
ll m;

char s[N], str[N];
int tot;
int p[N];
ll c[N];
void manachar() {
int id = 0, mx = 0;
for(int i = 1; i <= tot; ++i) {
if(i < mx) p[i] = min(p[2 * id - i], mx - i - 1);
while(s[i - p[i]] == s[i + p[i]]) {
++p[i];
}
if(s[i - p[i] + 1] == '#') ++c[p[i] - 1];
else ++c[p[i]];
if(i + p[i] > mx) {
mx = i + p[i];
id = i;
}
}
}
const ll md = 19930726;
ll ksm(ll x, ll y) {
ll res = 1;
for(; y; y >>= 1, x = x * x % md)
if(y &1) res = res * x %md;
return res;
}
int main() {
n = read(), m = read();
scanf("%s", str + 1);
s[0] = '$';
for(int i = 1; i <= n; ++i) {
s[++tot] = str[i];
s[++tot] = '#';
}
s[tot] = '\n';
manachar();
ll res = 1, sum = 0;
for(int i = n; i; --i) c[i] += c[i + 2];
for(int i = (n % 2 ? n : n - 1); i >= 1&& sum < m; i -= 2) if(c[i]){
res = res * ksm(i, min(c[i], m - sum)) % md;
sum += c[i];
}
writeln(res);
return 0;
}