在(DAG)上跑一个(dp)就好了
设(ans_i)表示到了(SAM)的(i)位置上所有的子串形成的数的和，之后我们顺便记录一个方案数(d_i)
之后我们直接转移就好了
[ans_v+=ans_u imes 10+w[u,v] imes d_u
]
[d_v+=d_u
]
答案是(sum_{i=1}^{cnt} ans_i)
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 1000005
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const LL mod=1e9+7;
int n,m,cnt=1,lst=1;
char S[maxn];
int fa[maxn<<1],len[maxn<<1],son[maxn<<1][11];
LL ans[maxn<<1],d[maxn<<1];
int q[maxn<<1],top,r[maxn<<1];
inline void ins(int c)
{
int f=lst,p=++cnt; lst=p;
len[p]=len[f]+1;
while(f&&!son[f][c]) son[f][c]=p,f=fa[f];
if(!f) {fa[p]=1;return;}
int x=son[f][c];
if(len[f]+1==len[x]) {fa[p]=x;return;}
int y=++cnt;
len[y]=len[f]+1,fa[y]=fa[x],fa[x]=fa[p]=y;
for(re int i=0;i<=10;i++) son[y][i]=son[x][i];
while(f&&son[f][c]==x) son[f][c]=y,f=fa[f];
}
int main()
{
scanf("%d",&m);
for(re int i=1;i<=m;i++)
{
scanf("%s",S+1);n=strlen(S+1);
for(re int j=1;j<=n;j++) ins(S[j]-'0');
ins(10);
}
for(re int i=1;i<=cnt;i++)
for(re int j=0;j<=10;j++) r[son[i][j]]++;
q[++top]=1,d[1]=1;
for(re int i=1;i<=top;i++)
{
for(re int j=0;j<10;j++)
{
if(!son[q[i]][j]) continue;
r[son[q[i]][j]]--;
d[son[q[i]][j]]=(d[q[i]]+d[son[q[i]][j]])%mod;
ans[son[q[i]][j]]=(ans[son[q[i]][j]]+d[q[i]]*(LL)j%mod+10ll*ans[q[i]]%mod)%mod;
if(!r[son[q[i]][j]]) q[++top]=son[q[i]][j];
}
if(!son[q[i]][10]) continue;
r[son[q[i]][10]]--;
if(!r[son[q[i]][10]]) q[++top]=son[q[i]][10];
}
LL now=0;
for(re int i=2;i<=cnt;i++) now=(now+ans[i])%mod;
printf("%lld
",now);
return 0;
}