思路

后缀自动机题目，题目本质上是要求求出所有不同的子串的和，SAM每个节点中存放的子串互不相同，所以对于每个节点的sum，可以发现是可以递推的，每个点对子节点贡献是sum[x]*10+c*sz[x]，对于单个串，sz[x]就是maxlen[x]-minlen[x]+1，现在有多个串，可以用其他字符分割，然后建出SAM，注意到新的合法的sz是不能跨越两个不同的串的，SAM上的一条路径就是一个子串，所以求sz等价于统计不经过分隔符的路径条数，拓扑排序即可

代码

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <string>

#include <queue>

#include <iostream>

#define int long long

using namespace std;

const int MAXN = 1000100*2;

const int MOD = 1000000007;

int cnt,trans[MAXN][11],maxlen[MAXN],sz[MAXN],in[MAXN],suflink[MAXN],sum[MAXN],ok[MAXN],n,len=0;

char s[MAXN],t[MAXN];

int new_state(int _maxlen,int *_trans,int _suflink){

    ++cnt;

    maxlen[cnt]=_maxlen;

    if(_trans)

        for(int i=0;i<11;i++)

            trans[cnt][i]=_trans[i];

    suflink[cnt]=_suflink;

    return cnt;

}

int add_len(int u,int c){

    int z=new_state(maxlen[u]+1,NULL,0);

    if(c==10)

        ok[z]=true;

    while(u&&(!trans[u][c])){

        trans[u][c]=z;

        u=suflink[u];

    }

    if(!u){

        suflink[z]=1;

        return z;

    }

    int v=trans[u][c];

    if(maxlen[v]==maxlen[u]+1){

        suflink[z]=v;

        return z;

    }

    int y=new_state(maxlen[u]+1,trans[v],suflink[v]);

    suflink[z]=suflink[v]=y;

    while(u&&trans[u][c]==v){

        trans[u][c]=y;

        u=suflink[u];

    }

    return z;

}

queue<int> q;

signed main(){

    scanf("%lld",&n);

    for(int i=1;i<=n;i++){

        scanf("%s",t+1);

        int midlen=strlen(t+1);

        if(i!=1)

            s[++len]='0'+10;

        for(int j=1;j<=midlen;j++)

            s[len+j]=t[j];

        len+=midlen;

    }

    s[len+1]='\0';

    // printf("%s\n%lld\n",s+1,len);

    int pre=1;

    cnt=1;

    for(int i=1;i<=len;i++)

        pre=add_len(pre,s[i]-'0');

    // printf("cnt=%d\n",cnt);

    for(int i=1;i<=cnt;i++){

        for(int j=0;j<11;j++)

            if(trans[i][j])

                in[trans[i][j]]++;

    }

    for(int i=1;i<=cnt;i++)

        if(!in[i])

            q.push(i);

    sz[1]=1;

    sum[1]=0;

    while(!q.empty()){

        int x=q.front();

        q.pop();

        for(int i=0;i<11;i++){

            if(trans[x][i]){

                if(i<10){

                    sz[trans[x][i]]=(sz[x]+sz[trans[x][i]])%MOD;

                    sum[trans[x][i]]=(sum[trans[x][i]]+sum[x]*10%MOD+i*sz[x]%MOD)%MOD;

                }

                in[trans[x][i]]--;

                if(!in[trans[x][i]])

                    q.push(trans[x][i]);

            }

        }

    }

    int ans=0;

    for(int i=1;i<=cnt;i++)

        if(!ok[i])

            ans=(ans+sum[i])%MOD;

    printf("%lld\n",ans);

    return 0;

}