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://acxblog.site/archives/sol-luogu-1659.html
本文采用 CC BY-NC-SA 3.0 协议进行许可