后缀自动机四·重复旋律7
时间限制:15000ms
单点时限:3000ms
内存限制:512MB
描述
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一段音乐旋律可以被表示为一段数构成的数列。
神奇的是小Hi发现了一部名字叫《十进制进行曲大全》的作品集，顾名思义，这部作品集里有许多作品，但是所有的作品有一个共同特征：只用了十个音符，所有的音符都表示成0-9的数字。
现在小Hi想知道这部作品中所有不同的旋律的“和”（也就是把串看成数字，在十进制下的求和，允许有前导0）。答案有可能很大，我们需要对（10^9 + 7)取摸。
输入
第一行，一个整数N，表示有N部作品。
接下来N行，每行包含一个由数字0-9构成的字符串S。
所有字符串长度和不超过 1000000。
输出
共一行，一个整数，表示答案 mod （10^9 + 7)。
- 样例输入
-
2
101
09 - 样例输出
-
131
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <time.h>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int N=2e6+;
const int M=1e6+;
const long long MOD = 1000000007LL;
int tot,slink[*N],trans[*N][],minlen[*N],maxlen[*N],edpts[*N];
string str;
int n;
int containPrefix[N],ind[N],ans[*N+],cnt[N*];
ll sum[N*],sz_valid[N*];
int newstate(int _maxlen,int _minlen,int* _trans,int _slink) {
maxlen[++tot]=_maxlen;
minlen[tot]=_minlen;
slink[tot]=_slink;
if(_trans)
for(int i=; i<; i++)
trans[tot][i]=_trans[i];
return tot;
}
int add_char(char ch,int u) {
int c=ch-'',v=u;
int z=newstate(maxlen[u]+,-,NULL,);
containPrefix[z]=;
while(v&&!trans[v][c]) {
trans[v][c]=z;
v=slink[v];
}
if(!v) {
minlen[z]=;
slink[z]=;
ind[]++;
return z;
}
int x=trans[v][c];
if(maxlen[v]+==maxlen[x]) {
slink[z]=x;
minlen[z]=maxlen[x]+;
ind[x]++;
return z;
}
int y=newstate(maxlen[v]+,-,trans[x],slink[x]);
slink[z]=slink[x]=y;
ind[y]+=;
minlen[x]=minlen[z]=maxlen[y]+;
while(v&&trans[v][c]==x) {
trans[v][c]=y;
v=slink[v];
}
minlen[y]=maxlen[slink[y]]+;
return z;
}
void init_dag() {
for ( int i = ; i <=tot; i++ ) {
for ( int j = ; j < ; j++ ) {
if ( trans[i][j] > ) {
cnt[trans[i][j]] ++;
}
}
}
} void topsort(){
queue<int>q;
for ( int i = ; i <=tot; i++ ) {
if ( cnt[i] == ) {
q.push(i);
sz_valid[i] = ;
sum[i] = ;
}
}
while(!q.empty()){
int i=q.front();
q.pop();
for ( int k = ; k < ; k++ ) {
if ( trans[i][k] > ) {
int j = trans[i][k];
if(k < ) {
sz_valid[j] += sz_valid[i];
sz_valid[j] %= MOD;
sum[j] += sum[i] * + k * sz_valid[i];
sum[j] %= MOD;
}
cnt[j] --;
if(cnt[j] == ) q.push(j);
}
}
}
}
int main() {
cin>>n;
cin>>str;
for(int i=;i<n;i++){
string ss;
cin>>ss;
str=str+":"+ss;
}
int pre=newstate(,,NULL,-);;
tot=;
int len=str.length();
for(int i=; i<len; i++) {
pre=add_char(str[i],pre);
}
init_dag();
topsort();
ll ans=;
for ( int i = ; i <=tot; i++ ) {
ans += sum[i];
ans %= MOD;
}
cout << ans << endl;
return ;
}