hihocoder 1457
题目概要
给定 (n) 个由数字组成的字符串，求所有不重复子串的权值（当成10进制数）和。
思路：
首先考虑单个字符串的情况，我们知道(SAM)的所有状态(substrings)的并集，刚好是所有不重复的子串。
记 (dp[st]) 为状态 (st) 所有子串的权值和，那么 (ans=sum dp[x])。
现在来考虑转移：
由转移函数的定义，我们不难想到(dp[v]=sum { dp[u]*10+c*|substrings[u]|，trans[u][c]=v })
由于 (SAM) 的所有状态和转移构成了一个 (DAG)，我们可以求出拓扑序，依次求出 (dp[i])。
对于多串的情况，我们可以借用类似 (SA) 的做法。用 (:) 把所有的串链接起来，最后对每一个状态，我们求出所有路径上不经过 (:) 的转移。这一点我们依然可以在拓扑排序的过程中实现。
代码：
//#pragma GCC optimize(2)
//#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int N=2e6+5;
const ll mod=1e9+7;
const double eps=1e-5;
//const double pi=acos(-1);
#define ls p<<1
#define rs p<<1|1
int maxlen[N<<1],trans[N<<1][26],link[N<<1],tot=1,last=1;
inline void extend(int id)
{
int cur=++tot,p;
maxlen[cur]=maxlen[last]+1;
for(p=last;p&&!trans[p][id];p=link[p]) trans[p][id]=cur;
if(!p) link[cur]=1;
else
{
int x=trans[p][id];
if(maxlen[x]==maxlen[p]+1) link[cur]=x;
else
{
int y=++tot;
maxlen[y]=maxlen[p]+1;
for(int i=0;i<26;i++) trans[y][i]=trans[x][i];
link[y]=link[x];
for(;p&&trans[p][id]==x;p=link[p]) trans[p][id]=y;
link[cur]=link[x]=y;
}
}
last=cur;
}
int vis[N<<1],deg[N<<1];
ll siz[N<<1],dp[N<<1];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin>>n;
while(n--)
{
string s;
cin>>s;
for(auto v:s) extend(v-'0');
extend(10);
}
queue<int>q;
q.push(1);vis[1]=1;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=0;i<10;i++)
{
int v=trans[u][i];
if(!v) continue;
deg[v]++;
if(!vis[v]) q.push(v),vis[v]=1;
}
}
q.push(1);siz[1]=1;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=0;i<10;i++)
{
int v=trans[u][i];
if(!v) continue;
siz[v]=(siz[v]+siz[u])%mod;
dp[v]=(dp[v]+dp[u]*10+siz[u]*i)%mod;
if(--deg[v]==0) q.push(v);
}
}
ll ans=0;
for(int i=1;i<=tot;i++) ans=(ans+dp[i])%mod;
cout<<ans<<endl;
return 0;
}