[BZOJ2160] 拉拉队排练 PAM

题意简述

询问一个串中所有奇回文按照长度降序排列，前k个奇回文的长度乘积。

做法

回文自动机(PAM)模板题。

维护每个回文自动机的结点回文串出现次数，跳fail得到每个长度的出现次数，双关键字排序后用快速幂统计答案。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register int
#define db double
#define in inline
namespace fast_io
{
    char buf[1<<12],*p1=buf,*p2=buf,sr[1<<23],z[23];int C=-1,Z=0;
    in char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}
    in ll read()
    {
        ll x=0,y=1;char c;while(c=gc(),(c<48||c>57)&&c!=-1) if(c==45) y=-1;
        x=c-48;while(c=gc(),47<c&&c<58) x=(x<<3)+(x<<1)+(c^48);return x*y;
    }
    in db gf() {int a=read(),b=read(),c=ceil(log10(b));return (b?a+(db)b/pow(10,c):a);}
    in void gs(char *s) {char c;while(c=gc(),c<32);*s++=c;while(c=gc(),c>32) *s++=c;}
    template <typename T>
    in void write(T &x,char t)
    {
        re y=0;if(x<0) y=1,x=-x;while(z[++Z]=x%10+48,x/=10);
        if(y) z[++Z]='-';while(sr[++C]=z[Z],--Z);sr[++C]=t;
    }
    in void write(char *s) {re l=strlen(s);for(re i=0;i<l;i++,*s++)sr[++C]=*s;sr[++C]='\n';}
    in void ot() {fwrite(sr,1,C+1,stdout);C=-1;}
};
using namespace fast_io;
const int N=1e6+5,mod=19930726;
int n,m,tot,ch[N][26],len[N],sum[N],fail[N],f[N],lst,q[N],h,t;
ll k,ans=1;
char s[N];
in int new_node(re x) 
{
    len[++tot]=x,fail[tot]=sum[tot]=0;
    ch[tot][0]=ch[tot][1]=ch[tot][2]=ch[tot][3]=0;
    return tot;
}
in void init() {tot=-1;new_node(0),new_node(-1);fail[0]=fail[1]=1;lst=0;}
in void ins(re c,re pos)
{
    re p=lst;
    while(s[pos-len[p]-1]!=s[pos]) p=fail[p];
    if(!ch[p][c])
    {
        re np=new_node(len[p]+2),q=fail[p];
        while(s[pos-len[q]-1]!=s[pos]) q=fail[q];
        fail[np]=ch[q][c];ch[p][c]=np;
    }
    sum[lst=ch[p][c]]++;
}
in ll qpow(ll x,re y) {ll z=1;for(;y;y>>=1,x=x*x%mod) if(y&1) z=z*x%mod;return z;}
int main()
{
    n=read(),k=read();gs(s+1);init();
    for(re i=1;i<=n;i++) ins(s[i]-'a',i);
    for(re i=tot;i;i--) sum[fail[i]]+=sum[i];
    vector<pair<int,int> >v;
    for(re i=2;i<=tot;i++) v.emplace_back(len[i],sum[i]);
    sort(v.begin(),v.end());reverse(v.begin(),v.end());
    for(auto x:v) if(x.first&1)
    {
        ll mi=min(k,(ll)x.second);k-=mi;
        ans=(ll)ans*qpow(x.first,mi)%mod;
        if(!k) break;
    }
    if(k) write("-1");else write(ans,'\n');
    return ot(),0;
}
//Author: disangan233

[BZOJ2160] 拉拉队排练 PAM

原文：https://www.cnblogs.com/disangan233/p/11296829.html