LP1659 拉拉队排练
Problem
艾利斯顿商学院篮球队要参加一年一度的市篮球比赛了。拉拉队是篮球比赛的一个看点,好的拉拉队往往能帮助球队增加士气,赢得最终的比赛。所以作为拉拉队队长的楚雨荨同学知道,帮助篮球队训练好拉拉队有多么的重要。
拉拉队的选拔工作已经结束,在雨荨和校长的挑选下,n 位集优秀的身材、舞技于一体的美女从众多报名的女生中脱颖而出。这些女生将随着篮球队的小伙子们一起,和对手抗衡,为艾利斯顿篮球队加油助威。
一个阳光明媚的早晨,雨荨带领拉拉队的队员们开始了排练。n 个女生从左到右排成一行,每个人手中都举了一个写有 26 个小写字母中的某一个的牌子,在比赛的时候挥舞,为小伙子们呐喊、加油。
雨荨发现,如果连续的一段女生,有奇数个,并且他们手中的牌子所写的字母,从左到右和从右到左读起来一样,那么这一段女生就被称作和谐小群体。
现在雨荨想找出所有和谐小群体,并且按照女生的个数降序排序之后,前 K 个和谐小群体的女生个数的乘积是多少。由于答案可能很大,雨荨只要你告诉她,答案除以 19930726 的余数是多少就行了。
Solution
先用 manacher 处理出回文子串的最长长度,即 p 数组,将回文子串长度统计。
然后对于一个以 x 为中心的长度为奇数的回文串,将两边删去,仍然以 x 为中心,因此是唯一的。
以此,做前缀和统计就行。假设某中心回文子串最长长度为 x,则 1~x 的长度为奇数的回文子串的个数都 +1。由于是省选题,不做过多的赘述。
由于没看清题面,所以我把偶数也算上了,其实只要分开统计就行了。
以及要用上快速幂。
Code
// Code by ajcxsu
// Problem: laladui
#include<bits/stdc++.h>
#define MOD (19930726ll)
using namespace std;
typedef long long ll;
const int N=1000010;
ll cnta[N],cntb[N]; // 奇偶分开计数
int p[2*N];
string str;
string y;
ll dpow(ll x,ll y) {
ll ret=1;
while(y) {
if(y&1ll) ret=(ret*x)%MOD;
x=(x*x)%MOD, y>>=1ll;
}
return ret;
}
int main() {
ios::sync_with_stdio(false);
ll n,k;
cin>>n>>k;
cin>>str;
y="#";
for(int i=0;i<n;i++) y+='#', y+=str[i];
y+='#';
int mid=0,mr=0,x;
p[0]=1;
for(int i=1,len=y.size();i<len-1;i++) {
p[i]=mr>i?min(p[2*mid-i],mr-i):1;
while(y[i+p[i]]==y[i-p[i]]) p[i]++;
if(i+p[i]>mr) mr=i+p[i], mid=i;
x=p[i]-1;
if(x&1) cnta[x]++;
else cntb[x]++;
}
ll cnt=0,ans=1,a=0,b=0;
for(ll i=n;i>=0;i--) {
if(!i) cout<<-1<<endl, exit(0);
if(i&1ll) {
if(cnt+a+cnta[i]>k) { ans=(ans*dpow(i,k-cnt)) % MOD; break; }
else {
a+=cnta[i], cnt+=a;
ans=(ans*dpow(i,a)) % MOD;
}
}
// else {
// if(cnt+b+cntb[i]>k) { ans=(ans*dpow(i,k-cnt)) % MOD; break; }
// else {
// b+=cntb[i], cnt+=b;
// ans=(ans*dpow(i,b)) % MOD;
// }
// } 没看清题导致多加了一个偶数情况,其实如果有偶数情况分开统计就行
}
cout<<ans<<endl;
return 0;
}
本文链接:https://pst.iorinn.moe/archives/sol-luogu-1659.html
许可: https://pst.iorinn.moe/license.html若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆