PAM练习

题：https://www.luogu.com.cn/problem/P1659

题意：问前k大的奇数长度的回文串的长度乘积；

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=1e6+6;
const int maxn=26;
const int mod=19930726;
char s[M];
struct node{
    ll val,num;
    bool operator<(const node &b)const{
        return val>b.val;
    }
}b[M];

struct pam{
    int  son[M][maxn],cnt[M],num[M],fail[M],len[M];
    char s[M];
    int tot,last;
    int newnode(int Len){
        for(int i=0;i<maxn;i++)
            son[tot][i]=0;
        cnt[tot]=0;
        num[tot]=0;
        fail[tot]=0;
        len[tot]=Len;
        return tot++;
    }
    void init(){
        s[0]='#';
        tot=0;
        last=0;
        newnode(0);
        newnode(-1);
        fail[0]=1;
    }
    int getfail(int p,int i){
        while(s[i-len[p]-1]!=s[i])
            p=fail[p];
        return p;
    }
    void solve(const char *buf){
        init();
        int n=strlen(buf+1);
        for(int i=1;i<=n;i++){
            s[i]=buf[i]-'a';
            int cur=getfail(last,i);
            if(!son[cur][s[i]]){
                int now=newnode(len[cur]+2);
                fail[now]=son[getfail(fail[cur],i)][s[i]];
                son[cur][s[i]]=now;
                num[now]=num[fail[now]]++;
            }
            cnt[last=son[cur][s[i]]]++;
        }
        for(int i=tot-1;i>=0;i--)
            cnt[fail[i]]+=cnt[i];
    }
}PAM;
ll ksm(ll a,ll b){
    ll t=1ll;
    while(b){
        if(b&1){
            t=(t*a)%mod;
        }
        b>>=1ll;
        a=(a*a)%mod;
    }
    return t;
}
int main(){
    ll n,k;
    scanf("%lld%lld",&n,&k);
    scanf("%s",s+1);
    PAM.solve(s);
    int m=0;
    for(int i=0;i<PAM.tot;i++){
    //    cout<<PAM.len[i]<<"!!"<<PAM.cnt[i]<<endl;
        if(PAM.len[i]&1){
            b[m].val=PAM.len[i];
            b[m].num=PAM.cnt[i];
            m++;
        }
        
    }
    sort(b,b+m);
    ll ans=1ll;
    for(int i=0;i<m;i++){
        ans=(1ll*ans*ksm(b[i].val,min(1ll*b[i].num,k)))%mod;
    //    cout<<ans<<endl;
        k-=b[i].num;
        if(k<=0)
            break;
    }
    printf("%lld
",ans);
    return 0;
}

View Code

题：https://codeforces.com/contest/17/problem/E

题意：求不相交回文串的对数

分析：先求整体对数减去相交对数即可

注意：内存限制，fail改成邻接表形式

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define MAX 2000020
#define MOD 51123987
int n,p1[MAX],p2[MAX],ans,dep[MAX];
char s[MAX];
struct Line{int v,next,w;}e[MAX];
int cnt=1;
int h[MAX];
inline void Add(int u,int v,int w){e[cnt]=(Line){v,h[u],w};h[u]=cnt++;}
struct PT
{
    struct Node
    {
        int ff,len;
    }t[MAX];
    int tot,last;
    void init()
    {
        for(int i=0;i<=tot;++i)
        {
            h[i]=0;
            t[i].ff=t[i].len=0;
        }
        cnt=1;
        last=0;
        t[tot=1].len=-1;
        t[0].ff=t[1].ff=1;
    }
    int nt(int k,int c)
    {
        for(int i=h[k];i;i=e[i].next)
            if(e[i].w==c)return e[i].v;
        return 0;
    }       
    void extend(int c,int n,char *s)
    {
        int p=last;
        while(s[n-t[p].len-1]!=s[n])p=t[p].ff;
        if(!nt(p,c))
        {
            int v=++tot,k=t[p].ff;
            while(s[n-t[k].len-1]!=s[n])k=t[k].ff;
            t[v].len=t[p].len+2;
            t[v].ff=nt(k,c);
            dep[v]=dep[t[v].ff]+1;
            Add(p,v,c);
        }
        last=nt(p,c);
    }
}pt1;
int main()
{
    scanf("%d",&n);
    scanf("%s",s+1);
    pt1.init();
    for(int i=1;i<=n;++i)
    {
        pt1.extend(s[i]-97,i,s);
        ans=(ans+(p1[i]=dep[pt1.last]))%MOD;
    }
    ans=1ll*ans*(ans-1)/2%MOD;
    reverse(&s[1],&s[n+1]);
    memset(dep,0,sizeof(dep));
    pt1.init();
    for(int i=1;i<=n;++i)
    {
        pt1.extend(s[i]-97,i,s);
        p2[n-i+1]=dep[pt1.last];
    }
    for(int i=n;i;--i)(p2[i]+=p2[i+1])%=MOD;
    for(int i=1;i<=n;++i)ans=(ans-1ll*p1[i]*p2[i+1]%MOD+MOD)%MOD;
    printf("%d
",ans);
    return 0;
}

View Code

题：http://www.lydsy.com/JudgeOnline/problem.php?id=2565

题意：求俩个回文组成的最长串长度。

分析：正方跑一遍PAM就可以计数了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=1e5+6;
const int maxn=26;
char s[M],s1[M];
int a[M];
struct pam{
    int  son[M][maxn],cnt[M],fail[M],len[M],sum[M];
    char s[M];
    int tot,last;
    int newnode(int Len){
        for(int i=0;i<maxn;i++)
            son[tot][i]=0;
        cnt[tot]=0;
        fail[tot]=0;
        len[tot]=Len;
        return tot++;
    }
    void init(){
        s[0]='#';
        tot=0;
        last=0;
        newnode(0);
        newnode(-1);
        fail[0]=1;
    }
    int getfail(int p,int i){
        while(s[i-len[p]-1]!=s[i])
            p=fail[p];
        return p;
    }
    void solve(char buf[]){
        init();
        int n=strlen(buf+1);
        for(int i=1;i<=n;i++){
            s[i]=buf[i]-'a';
            int cur=getfail(last,i);
            if(!son[cur][s[i]]){
                int now=newnode(len[cur]+2);
                fail[now]=son[getfail(fail[cur],i)][s[i]];
                son[cur][s[i]]=now;
            }
            cnt[last=son[cur][s[i]]]++;
            sum[i]=len[last];
        }
        for(int i=tot-1;i>=0;i--)
            cnt[fail[i]]+=cnt[i];
    }
}PAM;
 
int main(){
    int n;
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=n;i>=1;i--)
        s1[i]=s[n-i+1];
    PAM.solve(s);
    for(int i=1;i<=n;i++)
        a[i]=PAM.sum[i];
    PAM.solve(s1);
    int ans=2;
    for(int i=1;i<=n;i++)
        if(PAM.sum[i]>=1&&a[n-i]>=1)
            ans=max(ans,PAM.sum[i]+a[n-i]);
    printf("%d
",ans);
    return 0;
}

View Code