题意：
给出若干个串，求所有子串的和，子串和的定义为十进制数，取模1e9+7.
思路：
对于一个串来说，一个状态p就代表着$right$相同的集合，假设我们已经知道了状态p的$sum$，以及状态p的$size$，假设p的下一位有一个c，p+c的状态为q，那么$sum[q]+=sum[p]*10+c*size[p]$,并且要更新$size[q]$，注意这里是“+=”,因为q也有可能通过其他方式得到。
而这道题的终点就是如何转移，显然是用拓扑，但困扰了我好久的就是如何处理一开始每个点的入度。
这是我一开始的代码。
for(int i=1;i<=tot;i++){ for(int j=0;j<10;j++){ in[ch[i][j]]++; } }
这个代码的意思就是我把每个点和后面能抵达的点全部建边了，但这样答案会少，原因是有些点的入度永远不会0，所以少计算了，这个入度处理方式是错误的。
为什么呢？因为我们在处理多个串的时候，需要用一个':'符号来连接两个字符串，而这个符号刚好比‘9’大1，而我们下面用拓扑进行dp的时候，由于我们根本不会在队列里放入":"这个字符，所以形如$:5$这样的入度永远不会被减去，就无法入队。
所以我们处理入度的方式还是要用拓扑。
#include<bits/stdc++.h> #define clr(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const ll mod=1e9+7; const int maxn=1000100; char s[maxn]; int len[maxn<<1],ch[maxn<<1][11],fa[maxn<<1],tot=1,root=1,last=1,siz,r[maxn<<1]; int a[maxn<<1],c[maxn<<1],ans[maxn<<1]; ll dp[maxn<<1]; void extend(int x){ int now=++tot,pre=last; last=now,len[now]=len[pre]+1; while( pre && !ch[pre][x]){ ch[pre][x]=now; pre=fa[pre]; } if(!pre)fa[now]=root; else{ int q = ch[pre][x]; if(len[q]==len[pre]+1)fa[now]=q; else { int nows=++tot; memcpy(ch[nows],ch[q],sizeof(ch[q])); len[nows]=len[pre]+1; fa[nows]=fa[q]; fa[q]=fa[now]=nows; while(pre&&ch[pre][x]==q){ ch[pre][x]=nows; pre=fa[pre]; } } } } bool vis[maxn<<1]; int in[maxn<<1]; int main(){ int n; cin>>n; while(n--){ scanf("%s",s); siz=strlen(s); for(int i=0;i<siz;i++) { int p=s[i]-'0'; extend(p); } extend(10); } queue<int >q; q.push(1); vis[1] = 1; while(!q.empty()){ int x = q.front(); q.pop(); for(int c = 0; c < 10; c++){ int y = ch[x][c]; if(y == 0) continue; if(!vis[y]) q.push(y); vis[y] = 1; in[y]++; } } q.push(1); r[1]=1; while(!q.empty()){ int i=q.front(); q.pop(); for(int j=0;j<10;j++){ int p=ch[i][j]; if(p){ r[p]=(r[p]+r[i])%mod; dp[p]=(dp[p]+dp[i]*10%mod+j*r[i]%mod)%mod; if(--in[p]==0){ q.push(p); } } } } ll res=0; for(int i=1;i<=tot;i++){ res=(res+dp[i])%mod; } cout<<res<<endl; }