题目

在\(DAG\)上跑一个\(dp\)就好了

设\(ans_i\)表示到了\(SAM\)的\(i\)位置上所有的子串形成的数的和，之后我们顺便记录一个方案数\(d_i\)

之后我们直接转移就好了

答案是\(\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\n",now);

	return 0;

}