【题目链接】
http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=51267
【题意】
给定n个字符串，计算所有忽略前导0的子串形成的不重整数之和。
【思路】
既然是处理子串问题，我们可以合并串之后构造一个SAM。
SAM的性质：结点u代表的字符串集是从根到u路径上的所有结点代表的字符串集之并，结点u所代表的字符串集为最长串的所有子串。
记cnt[u]为状态u代表的字符串个数，sum[u]代表状态u代表的字符串对应的数之和。
拓扑排序后，设p为当前结点，trans(p,j)为np，则有：
cnt[np]+=cnt[p]
sum[np]+=sum[p]*10+cnt[p]*j
不走$边，第一次不走0边。
【代码】
#include<set>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define trav(u,i) for(int i=front[u];i;i=e[i].nxt)
#define FOR(a,b,c) for(int a=(b);a<=(c);a++)
using namespace std; typedef long long ll;
const int N = 2e5+;
const int MOD = ; int n,len;
char s[N];
int sum[N],cnt[N];
int sz,last,fa[N],ch[N][],l[N],c[N],b[N]; void add(int c)
{
int p=last,np=++sz; last=np;
l[np]=l[p]+;
for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
if(!p) fa[np]=;
else {
int q=ch[p][c];
if(l[q]==l[p]+) fa[np]=q;
else {
int nq=++sz; l[nq]=l[p]+;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
fa[nq]=fa[q];
fa[q]=fa[np]=nq;
for(;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
}
}
}
void init()
{
sz=last=;
len=;
memset(sum,,sizeof(sum));
memset(cnt,,sizeof(cnt));
memset(ch,,sizeof(ch));
memset(c,,sizeof(c));
memset(fa,,sizeof(fa));
memset(l,,sizeof(l));
}
int main()
{
while(scanf("%d",&n)==)
{
init();
FOR(i,,n) {
scanf("%s",s);
if(i!=) add(),len++;
for(int j=;s[j];j++)
add(s[j]-''),len++;
}
FOR(i,,sz) c[l[i]]++;
FOR(i,,len) c[i]+=c[i-];
FOR(i,,sz) b[c[l[i]]--]=i; int ans=;
cnt[]=;
FOR(i,,sz) {
int p=b[i];
for(int j=;j<;j++) {
if(i==&&j==) continue;
if(ch[p][j]) {
int np=ch[p][j];
cnt[np]=(cnt[np]+cnt[p])%MOD;
sum[np]=(sum[np]+sum[p]*+cnt[p]*j)%MOD;
}
}
ans=(ans+sum[p])%MOD;
}
printf("%d\n",ans);
}
return ;
}