[国家集训队]拉拉队排练

「爱情、让人受尽委屈。」 2021-11-11 14:50 295阅读 0赞

# 题意 #

将给定字符串S的奇数长度回文串按长度排序，求前k长的回文子串长度乘积，对19930726取模。

对于100%的数据n<=1e6，k<=1e12

# 题解 #

若有长度为i的回文子串，就有长度为i-2的回文子串；

manacher求的是以一个点为中心的最长回文子串，当求到一个长度为len（奇数）的子串，就得到1,3,...len的回文子串，考虑差分。

先预处理出长度为i的回文子串的个数（长度不超过n），倒着遍历数组，统计答案，用快速幂。

没什么本质难度，主要在于第一步的性质和差分。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    
    #define ll long long
    const int maxn=2000005;
    const int mod=19930726;
    int n;
    ll k,ans=1;
    char s[maxn],t[maxn];
    int pl[maxn];
    int cx[maxn];//存长度为i的回文串有几个
    
    ll fast_pow(ll a,ll b){
        ll ret=1;
        while(b){
            if(b&1) ret=ret*a%mod;
            a=a*a%mod;
            b>>=1;
        }
        return ret;
    }
    
    void manacher(){
        s[0]='+';
        for(int i=1;i<2*n;i+=2){
            s[i]='#';
            s[i+1]=t[i/2];
        }
        s[2*n+1]='#';
        s[2*n+2]='-';
        s[2*n+3]='\0';
        int mx=0,id=0;
        n=2*n+1;
        for(int i=1;i<=n;i++){
            if(mx>=i) pl[i]=min(mx-i+1,pl[2*id-i]);
            else pl[i]=1;
            while(s[i+pl[i]]==s[i-pl[i]]) pl[i]++;
            if(mx<i+pl[i]-1) mx=i+pl[i]-1,id=i;
            if(i&1) continue;
            cx[1]++;cx[pl[i]]--;
        }
    }
    
    int main(){
        scanf("%d%lld%s",&n,&k,t);
        manacher();
        for(int i=1;i<=n;i++) cx[i]+=cx[i-1];
        //for(int i=1;i<=n;i++) printf("%d ",cx[i]);
        for(int i=n;i>=0&&k;i-=2)
         if(cx[i]){
             if(cx[i]>=k) ans=ans*fast_pow(i,k)%mod,k=0;
             else ans=ans*fast_pow(i,cx[i])%mod,k-=cx[i];
        }
        if(k) printf("-1");
        else printf("%lld",ans);
    }

转载于:https://www.cnblogs.com/sto324/p/11228045.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211109/504434db3efd4fecbfcfea91ec8737f4.png