很好的一个题目。对于理解后缀自动机很有用。
题目给你若干数字串，总长度不超过100000，任意一个串的任意一个子串都可以拿出来单独的作为一个数字。同一个数字只算一次。
问所有不同数字的和为多少？
嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯
首先由于字符串的数字很多，我们可以把么多串连接成一个串，每个串用[10]隔开就好了。
然后往后面搜，对于当前状态，保存以这个状态为终点的所有路径的和，每次记录有多少种路径走到当前状态，对于连接x到达的下一个状态就是这样来计算的：f[next[]]+=f[cur]*10+num[]*x；这个式子不难理解。
于是我们把所有的点都拓扑排序一下，然后这样一路计算下去就可以了。（按step值来排序）
有坑提示：注意前导零，注意不能用num是否等于0来判断当前状态能否到达，因为num对2012取模了，所以判断无意义。
召唤代码君：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define maxn 300300
using namespace std;
int next[maxn][11],pre[maxn],step[maxn];
int N,last,n,ans;
int p,q,np,nq;
int f[maxn],cnt[maxn],g[maxn],t[maxn];
char s[maxn];
bool mark[maxn];
int add()
{
N++; mark[N]=false;
t[N]=cnt[N]=g[N]=f[N]=pre[N]=step[N]=0;
for (int i=0; i<11; i++) next[N][i]=0;
return N;
}
void insert(int x)
{
p=last,np=add(),step[np]=step[last]+1,last=np;
while (p!=-1 && next[p][x]==0) next[p][x]=np,p=pre[p];
if (p==-1) return;
q=next[p][x];
if (step[q]==step[p]+1) { pre[np]=q; return; }
nq=add(),step[nq]=step[p]+1,pre[nq]=pre[q];
for (int i=0; i<11; i++) next[nq][i]=next[q][i];
pre[np]=pre[q]=nq;
while (p!=-1 && next[p][x]==q) next[p][x]=nq,p=pre[p];
}
int main()
{
while (scanf("%d",&n)!=EOF)
{
N=-1;N=add();pre[0]=-1;last=ans=0;
while (n--)
{
scanf("%s",s);
for (int i=0; s[i]; i++) insert(s[i]-'0');
insert(10);
}
for (int i=0; i<=N; i++) cnt[step[i]]++;
for (int i=1; i<=N; i++) cnt[i]+=cnt[i-1];
for (int i=0; i<=N; i++) g[--cnt[step[i]]]=i;
t[0]=1; mark[0]=true;
for (int p=0; p<=N; p++)
{
int cur=g[p];
if (next[0][0]==cur && next[0][0]!=0) continue;
if (!mark[cur]) continue;
ans=(ans+f[cur])%2012;
for (int i=0; i<=9; i++)
{
if (next[cur][i]==0) continue;
f[next[cur][i]]=(f[next[cur][i]]+f[cur]*10+t[cur]*i)%2012;
t[next[cur][i]]=(t[next[cur][i]]+t[cur])%2012;
mark[next[cur][i]]=true;
}
}
printf("%d\n",ans);
}
return 0;
}