P1659-[国家集训队]拉拉队排练
题目:
题目描述:
艾利斯顿商学院篮球队要参加一年一度的市篮球比赛了。拉拉队是篮球比赛的一个看点，好的拉拉队往往能帮助球队增加士气，赢得最终的比赛。所以作为拉拉队队长的楚雨荨同学知道，帮助篮球队训练好拉拉队有多么的重要。
拉拉队的选拔工作已经结束，在雨荨和校长的挑选下，n位集优秀的身材、舞技于一体的美女从众多报名的女生中脱颖而出。这些女生将随着篮球队的小伙子们一起，和对手抗衡，为艾利斯顿篮球队加油助威。
一个阳光明媚的早晨，雨荨带领拉拉队的队员们开始了排练。n个女生从左到右排成一行，每个人手中都举了一个写有26个小写字母中的某一个的牌子，在比赛的时候挥舞，为小伙子们呐喊、加油。
雨荨发现，如果连续的一段女生，有奇数个，并且他们手中的牌子所写的字母，从左到右和从右到左读起来一样，那么这一段女生就被称作和谐小群体。
现在雨荨想找出所有和谐小群体，并且按照女生的个数降序排序之后，前K个和谐小群体的女生个数的乘积是多少。由于答案可能很大，雨荨只要你告诉她，答案除以19930726的余数是多少就行了。
输入格式:
输入为标准输入。
第一行为两个正整数n和K，代表的东西在题目描述中已经叙述。
接下来一行为n个字符，代表从左到右女生拿的牌子上写的字母。
输出格式:
输出为标准输出。
输出一个整数，代表题目描述中所写的乘积除以19930726的余数，如果总的和谐小群体个数小于K，输出一个整数-1。
样例:
样例输入1:
样例输出1:
思路:
实现:
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
| // Problem: P1659 [国家集训队]拉拉队排练
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1659
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Author: Ybw051114
//
// Powered by CP Editor (https://cpeditor.org)
#include "ybwhead/ios.h"
int n;
long long k;
const int maxn = 1e6 + 10;
char s[maxn];
// char s[N << 1];
long long len, RL[maxn], mxxnum, sum, ans = 1;
const long long mod = 19930726;
long long MaxRight, center, tong[maxn];
long long ksm(long long x, long long y)
{
long long res = 1;
for (; y; y >>= 1, x = x * x % mod)
if (y & 1)
res = res * x % mod;
return res;
}
int main()
{
yin >> n >> k;
yin >> (s + 1);
for (int i = 1; i <= n; i++)
{
if (i <= MaxRight)
RL[i] = min(MaxRight - i, RL[2 * center - i]);
else
RL[i] = 1;
while (i + RL[i] <= n && i - RL[i] >= 0 && s[i + RL[i]] == s[i - RL[i]])
++RL[i];
if (i + RL[i] - 1 > MaxRight)
MaxRight = i + RL[i] - 1, center = i;
tong[2 * RL[i] - 1]++;
}
if (n % 2 != 1)
n--;
for (int i = n; i >= 1; i -= 2)
{
sum += tong[i];
if (sum > k)
{
ans = ans * ksm(i, k) % mod;
k = 0;
break;
}
else
{
ans = ans * ksm(i, sum) % mod;
k -= sum;
}
}
if (k > 0)
yout << -1 << endl;
else
yout << ans << endl;
return 0;
}
|