hihoCoder1457 后缀自动机四·重复旋律7

http://hihocoder.com/problemset/problem/1457

后缀自动机

在后缀自动机上拓扑，计算每个节点的答案即可

然而我凉了很久……

原因：建图数组开小了！

注意：后缀自动机节点数开\(2n\)，边的条数开\(3n\)

C++ Code:

#include<bits/stdc++.h>
#define N 3000005
#define mod 1000000007
#define int long long
using namespace std;
int n,T,cnt=1,last=1,t[N][11],pre[N],sz[N],len[N],rd[N];
int tot,head[N],nxt[N],d[N],d2[N],p[N],g[N];
char s[N];
char s1[1];
long long z[N],ans;
queue<int>q;
void ins(char *s)
{
    n=strlen(s);
    for (int i=0;i<n;i++)
    {
        int c=(int)(s[i]-'0');
        int p,q,np=++cnt;
        len[np]=len[last]+1;
        for (p=last;p&&!t[p][c];p=pre[p])
            t[p][c]=np;
        if (!p)
            pre[np]=1; else
            {
                q=t[p][c];
                if (len[p]+1==len[q])
                    pre[np]=q; else
                    {

                        cnt++;
                        len[cnt]=len[p]+1;
                        for (int j=0;j<11;j++)
                            t[cnt][j]=t[q][j];
                        pre[cnt]=pre[q];
                        for (;p&&t[p][c]==q;p=pre[p])
                            t[p][c]=cnt;
                        pre[q]=pre[np]=cnt;
                    }
            }
        last=np;
    }
}
void add(int x,int y,int w)
{
    tot++;
    d[tot]=y;
    d2[tot]=w;
    nxt[tot]=head[x];
    head[x]=tot;
    rd[y]++;
}
main() 
{
    scanf("%lld",&T);
    z[1]=0;
    s1[0]=':';
    for (int i=1;i<=T;i++)
    {
        scanf("%s",s);
        ins(s);
        if (i^T)
            ins(s1);
    }
    for (int i=1;i<=cnt;i++)
        head[i]=0,rd[i]=0;
    for (int i=1;i<=cnt;i++)
        for (int j=0;j<10;j++)
            if (t[i][j])
                add(i,t[i][j],j);
    sz[1]=1;
    for (int i=1;i<=cnt;i++)
        if (!rd[i])
            q.push(i);
    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        for (int i=head[u];i;i=nxt[i])
        {
            int v=d[i];
            long long cost=d2[i];
            rd[v]--;
            z[v]+=z[u]*10+cost*sz[u],z[v]%=mod,sz[v]+=sz[u];
            if (!rd[v])
            {
                ans+=z[v];
                ans%=mod;
                q.push(v);
            }
        }
    }
    cout << ans << endl;
    return 0;
}