思路
后缀自动机题目，题目本质上是要求求出所有不同的子串的和，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]=' ';
// printf("%s
%lld
",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
",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
",ans);
return 0;
}