题目描述
艾利斯顿商学院篮球队要参加一年一度的市篮球比赛了。拉拉队是篮球比赛的一个看点，好的拉拉队往往能帮助球队增加士气，赢得最终的比赛。所以作为拉拉队队长的楚雨荨同学知道，帮助篮球队训练好拉拉队有多么的重要。
拉拉队的选拔工作已经结束，在雨荨和校长的挑选下，n位集优秀的身材、舞技于一体的美女从众多报名的女生中脱颖而出。这些女生将随着篮球队的小伙子们一起，和对手抗衡，为艾利斯顿篮球队加油助威。
一个阳光明媚的早晨，雨荨带领拉拉队的队员们开始了排练。n个女生从左到右排成一行，每个人手中都举了一个写有26个小写字母中的某一个的牌子，在比赛的时候挥舞，为小伙子们呐喊、加油。
雨荨发现，如果连续的一段女生，有奇数个，并且他们手中的牌子所写的字母，从左到右和从右到左读起来一样，那么这一段女生就被称作和谐小群体。
现在雨荨想找出所有和谐小群体，并且按照女生的个数降序排序之后，前K个和谐小群体的女生个数的乘积是多少。由于答案可能很大，雨荨只要你告诉她，答案除以19930726的余数是多少就行了。
输入格式
输入为标准输入。
第一行为两个正整数 $n$ 和 $K$，代表的东西在题目描述中已经叙述。
接下来一行为 $n$ 个字符，代表从左到右女生拿的牌子上写的字母。
输出格式
输出为标准输出。
输出一个整数，代表题目描述中所写的乘积除以 $19930726$ 的余数，如果总的和谐小群体个数小于$K$，输出一个整数$-1$。
样例 #1
样例输入 #1
5 3
ababa
样例输出 #1
45
提示
样例说明
和谐小群体女生所拿牌子上写的字母从左到右按照女生个数降序排序后为ababa, aba, aba, bab, a, a, a, b, b，前三个长度的乘积为 。
数据范围与约定
测试点
n
K
1
10
10
2-3
100
100
4-7
1,000
1,000
8
100,000
= 1
9-11
100,000
100,000
12-14
100,000
1,000,000,000,000
15-17
500,000
1,000,000,000,000
18
1,000,000
= 1
19
1,000,000
1,000,000
20
1,000,000
1,000,000,000,000
分析
由题意可知我们要求出字符串中的所有奇回文串的长度，并且计算出前 $K$ 大的数的乘积
我们使用 Manacher 算法计算出每一个位置的回文半径，然后考虑如何找出这前 $K$ 大个数
我们使用一个桶数组 $bucket[i]$ 记录长度为 $i$ 的回文的个数。在我们前面计算回文半径时，每次计算出一个点的回文半径时，将以该点为中心的最长的回文的长度加入到桶数组中（由于只需要求奇回文串，所以 Manacher 没有添加特殊字符，每个中心点的最长回文长度为 $d[i] * 2 - 1$，即 $bucket[d[i] * 2 - 1]++$)
最后计算时，只要从从大到小遍历桶数组，维护前缀和（因为我们加入的是每个点的最长的回文的长度 $n$，该点还存在 $n-2, n-4 \cdots 1$ 长的回文串），使用快速幂计算乘积即可（$k$ 太大了）
代码实现
/*
* @FileName: P1659.cpp
* @Author: Foresc
* @Date: 2022/09/10 21:34:31
*/
// manacher, 快速幂
#include <iostream>
#include <algorithm>
#define ll long long
#define Max(x, y) ((x) > (y) ? (x) : (y))
#define Min(x, y) ((x) > (y) ? (y) : (x))
const int MOD = 19930726;
using namespace std;
const int N = 1e6 + 10;
char s[N];
int bucket[N], d[N], n;
ll k = 0, sum = 0, ans = 1;
ll qpow(ll x, ll y) // 快速幂
{
ll r = 1;
while (y)
{
if (y & 1)
r = (x * r) % MOD;
x = (x * x) % MOD;
y >>= 1;
}
return r % MOD;
}
void manacher() // Manacher算法，由于只求奇回文串，所以不用添加特殊字符
{ // 相应的，d[i]数组的长度为原来的 1/2，所以计算长度使用 d[i] * 2 - 1
for (int i = 0, l = 0, r = -1; i < n; ++i)
{
int sp = l + r - i;
d[i] = Max(Min(d[sp], r - i + 1), 1);
if (sp - d[sp] < l)
{
while (i - d[i] >= 0 && i + d[i] < n && s[i + d[i]] == s[i - d[i]])
++d[i];
l = i - d[i] + 1, r = i + d[i] - 1;
}
bucket[2 * d[i] - 1]++;
}
}
void getAns() // 计算答案
{
for (int i = n - !(n % 2); i > 0; i -= 2)
{
sum += bucket[i]; // 取前缀和，因为只有记录每个中点的最长回文长度
if (sum > k) // 所以该点还有 n-2 到 1 长度的回文
{
ans = (ans * qpow(i, k)) % MOD;
break;
}
else
{
ans = (ans * qpow(i, sum)) % MOD;
k -= sum;
}
}
}
void solve()
{
cin >> n >> k;
getchar();
scanf("%s", s);
manacher();
getAns();
if (sum < k)
cout << -1 << endl;
else
cout << ans << endl;
}
int main()
{
#ifdef ONLINE_JUDGE
// ios::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
#endif
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
