题解 P1659 【[国家集训队]拉拉队排练】

· · 题解

这道题是Manacher马拉车算法的一道题目。我们可以用马拉车算法求出最长的回文子串。马拉车算法是一种优秀的算法，它可以线性复杂度求出回文子串。我们利用p[i]表示以i为回文子串中心的最大子串长度。我们可以以 p[i]=mx>i?min(mx-i,p[id*2-i]):1;求出p数组。 其中mx表示能匹配到的最右边的坐标，id表示当前匹配中心。 由于本题的数据范围，我们需要用到前缀和和快速幂优化，我会在程序里讲解

#include<bits/stdc++.h>
#define ll long long
#define md 19930726
using namespace std;
ll n,m,k,p[5000005],mx,id,tot[1000005],ans=1;
string s,t;
ll read(){
    char c;ll x;while(c=getchar(),c<'0'||c>'9');x=c-'0';
    while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0';return x;
}
void manacher(){
    t="@#";   //这题也可以不插入'#'
    for(ll i=0;i<n;i++){
        t.push_back(s[i]);
        t.push_back('#');
    }
    for(ll i=1;i<t.size();i++){
        p[i]=mx>i?min(p[id*2-i],mx-i):1;
        while(t[i+p[i]]==t[i-p[i]]) p[i]++;
        if(mx<i+p[i]){
            mx=i+p[i];id=i;
        }
    }
}
ll pows(ll a,ll b){
    ll base=1;
    while(b){
        if(b&1) base=base*a%md;
        a=a*a%md;
        b/=2;
    }
    return base;
}
int main()
{
    n=read();k=read();
    cin>>s;
    manacher();
    for(ll i=1;i<t.size();i++){
        if(t[i]=='#') continue;
        /*for(ll j=1;j<=p[i];j++) if(j%2==1) tot[j]++;*/  //如果用for会超时
        tot[p[i]-1]++;
    }
    for(int i=n;i>=1;i--)
       if(i%2==1) tot[i]+=tot[i+2];  //前缀和优化，因为若其长度为l，那么长度为l-2,l-4……都行
    for(ll i=n;i>=1;i--){
        if(!tot[i]) continue;
        if(k-tot[i]>=0){
            k-=tot[i];ans=(ans*pows(i,tot[i]))%md;  //快速幂求解答案，不用一个一个乘
        }
        else{
            ans=(ans*pows(i,k))%md;break;
        }
    }
    printf("%lld",ans%md);
    return 0;
}