【BZOJ4175】小G的电话本

2016.03.18 17:53 Fri | 47次阅读 | 旧日oi | 固定链接 | 源码

题解

后缀自动机+多项式快速幂

考虑如何统计出出现过x次的串有多少个,后缀自动机裸上即可。
考虑如何算出选k个,和恰为m的的方案数。
生成函数+多项式快速幂即可……
最近感觉这种俩东西拼在一起的题好无聊……

my code

#include <bits/stdc++.h>
using namespace std;
#define N 200005
#define mod 1005060097
#define G 5
int k,m;
int b[262144],a[262144];
char s[N];
int qpow(int x,int k)
{
    int ret=1;
    while(k)
    {
        if(k&1) ret=ret*1ll*x%mod;
        k>>=1;x=x*1ll*x%mod;
    }
    return ret;
}
void dft(int *a,int len,int type)
{
    int i,j,k,t=0;
    for(i=0;i<len;i++)
    {
        if(i>t) swap(a[i],a[t]);
        for(j=len>>1;(t^=j)<j;j>>=1);
    }
    for(t=1,k=2;k<=len;t=k,k<<=1)
    {
        int wn=qpow(G,(mod-1)/k);
        for(i=0;i<len;i+=k)
        {
            int w=1,tmp;
            for(j=0;j<t;j++,w=w*1ll*wn%mod)
            {
                tmp=w*1ll*a[i+j+t]%mod;
                a[i+j+t]=(a[i+j]-tmp+mod)%mod;
                a[i+j]=(a[i+j]+tmp)%mod;
            }
        }
    }
    if(type==-1)
    {
        int inv=qpow(len,mod-2);
        for(i=1;i<len>>1;i++) swap(a[i],a[len-i]);
        for(int i=0;i<len;i++) a[i]=a[i]*1ll*inv%mod;
    }
}
struct SAM{
    int tot,last;
    int son[N][26],fa[N],len[N],siz[N],v[N],id[N];
    void init(){tot=last=1;}
    void insert(int x)
    {
        int p=last,np=++tot;last=np;
        len[np]=len[p]+1;
        for(;p&&!son[p][x];p=fa[p]) son[p][x]=np;
        if(!p) fa[np]=1;
        else
        {
            int q=son[p][x];
            if(len[q]==len[p]+1) fa[np]=q;
            else
            {
                int nq=++tot;len[nq]=len[p]+1;
                fa[nq]=fa[q];fa[q]=fa[np]=nq;
                memcpy(son[nq],son[q],sizeof(son[q]));
                for(;p&&son[p][x]==q;p=fa[p]) son[p][x]=nq;
            }
        }
    }
    void solve(int L)
    {
        for(int p=1,i=1;i<=L;i++)
        {
            p=son[p][s[i]-'a'];
            siz[p]=1;
        }
        for(int i=1;i<=tot;i++) v[len[i]]++;
        for(int i=1;i<=tot;i++) v[i]+=v[i-1];
        for(int i=tot;i;i--) id[v[len[i]]--]=i;
        for(int i=tot;i;i--)
        {
            if(siz[id[i]]<=m) 
                (b[siz[id[i]]]+=1ll*siz[id[i]]*(len[id[i]]-len[fa[id[i]]])%mod)%=mod;
            siz[fa[id[i]]]+=siz[id[i]];
        } 
    }
}sam;
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    cin>>k>>m;
    scanf("%s",s+1);
    sam.init();
    int len=strlen(s+1),tl=1;
    for(int i=1;i<=len;i++) sam.insert(s[i]-'a');
    sam.solve(len);
    for(;tl<=(m+1)*2;tl<<=1);
    a[0]=1;
    int tmp=k;
    while(tmp)
    {
        dft(b,tl,1);
        if(tmp&1) 
        {
            dft(a,tl,1);
            for(int i=0;i<tl;i++) a[i]=a[i]*1ll*b[i]%mod;
            dft(a,tl,-1);
            for(int i=m+1;i<tl;i++) a[i]=0;
        }
        tmp>>=1;
        for(int i=0;i<tl;i++) b[i]=b[i]*1ll*b[i]%mod;
        dft(b,tl,-1);
        for(int i=m+1;i<tl;i++) b[i]=0;
    }
    printf("%d\n",a[m]);
}