【分析】
广义SAM，每个点记录一个ans，表示它代表的串的值的和。如果有前缀0，记得不能加进去，每个点标记一下它表示的串又做少个是有前缀0的，记为zr，用父亲的ans和zr更新儿子。
if(now==1&&k==0) t[np].zr=1;
else t[np].zr+=t[now].zr;
t[np].ans=(t[np].ans+t[now].ans*10+(t[now].step-t[t[now].pre].step-t[now].zr)*k);
SAM上有一步是新加一个点，继承某一个点的信息，记得这里要搞一下，把旧点信息减新点信息。
建完机就可以直接统计答案了哈哈哈！！！
具体看代码：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
#include<set>
using namespace std;
#define Mod 2012
#define Maxn 1000010 int n;
struct node
{
int pre,step,son[];
int ans,zr;
}t[*Maxn];int tot;
int last; char s[Maxn]; void upd(int x)
{
memset(t[x].son,,sizeof(t[x].son));
t[x].pre=;
t[x].ans=;t[x].zr=;
} void add(int now,int k,int np)
{
// if(now==1&&k==0) return;
if(now==&&k==) t[np].zr=;
else /*if(k==0)*/ t[np].zr+=t[now].zr;
t[now].son[k]=np;
t[np].ans=(t[np].ans+t[now].ans*+(t[now].step-t[t[now].pre].step-t[now].zr)*k)%Mod;
} void extend(int k)
{
int np=++tot;upd(tot);
t[np].step=t[last].step+;
int now=last;
while(now&&!t[now].son[k])
{
add(now,k,np);// t[now].son[k]=np;
now=t[now].pre;
}
if(!now) t[np].pre=;
else
{
int p=now,q=t[now].son[k];
if(t[p].step+==t[q].step) t[np].pre=q;
else
{
int nq=++tot;upd(tot);
memcpy(t[nq].son,t[q].son,sizeof(t[nq].son));
t[nq].pre=t[q].pre;
t[q].pre=t[np].pre=nq;
t[nq].step=t[p].step+;
while(now&&t[now].son[k]==q)
{
// t[now].son[k]=nq;
add(now,k,nq);
now=t[now].pre;
}
t[q].ans=(t[q].ans+Mod-t[nq].ans)%Mod;
t[q].zr-=t[nq].zr;
}
}
last=np;
} int main()
{
while(scanf("%d",&n)!=EOF)
{
tot=;
t[++tot].step=;upd(tot);
for(int i=;i<=n;i++)
{
scanf("%s",s+);
int l=strlen(s+);
last=;
for(int j=;j<=l;j++)
{
int k=s[j]-'';
extend(k);
}
}
int ans=;
for(int i=;i<=tot;i++) ans=(ans+t[i].ans)%Mod;
printf("%d\n",ans);
}
return ;
}
[HDU 4436]
2016-09-21 20:51:06