- #include
- #include
- #include
- #include
- using namespace std;
- typedef long long LL;
- int
- n =
- 0, len, st;
- const int
- maxL = 2e6 +
- 100;
- const int
- MOD = 1e9 +
- 7;
- int
- maxlen[
- 2
- *maxL], minlen[
- 2
- *maxL], trans[
- 2
- *maxL][
- 12
- ], slink[
- 2
- *maxL], col[
- 2
- *
- maxL];
- LL in
- [
- 2
- *maxL], dp[
- 2
- *maxL], sz[
- 2
- *
- maxL];
- int
- new_state(
- int
- _maxlen,
- int
- _minlen,
- int
- *_trans,
- int _slink){
- maxlen[n]
- =
- _maxlen;
- minlen[n]
- =
- _minlen;
- for
- (
- int
- i =
- 0
- ; i <
- 11
- ; i++
- ){
- if
- (_trans ==
- NULL)
- trans[n][i]
- = -
- 1;
- else
- trans[n][i]
- =
- _trans[i];
- }
- slink[n]
- =
- _slink;
- return
- n++
- ;
- }
- int
- add_char(
- char
- ch,
- int u){
- int
- c = ch -
- '0';
- int
- z = new_state(maxlen[u]+
- 1
- , -
- 1
- , NULL, -
- 1);
- int
- v =
- u;
- while
- (v != -
- 1
- && trans[v][c] == -
- 1){
- trans[v][c]
- =
- z;
- v
- =
- slink[v];
- }
- if
- (v == -
- 1){
- minlen[z]
- =
- 1;
- slink[z]
- =
- 0;
- return z;
- }
- int
- x =
- trans[v][c];
- if
- (maxlen[v] +
- 1
- ==
- maxlen[x]){
- minlen[z]
- = maxlen[x] +
- 1;
- slink[z]
- =
- x;
- return z;
- }
- int
- y = new_state(maxlen[v] +
- 1
- , -
- 1, trans[x], slink[x]);
- slink[y]
- =
- slink[x];
- minlen[x]
- = maxlen[y] +
- 1;
- slink[x]
- =
- y;
- minlen[z]
- = maxlen[y] +
- 1;
- slink[z]
- =
- y;
- int
- w =
- v;
- while
- (w != -
- 1
- && trans[w][c] ==
- x){
- trans[w][c]
- =
- y;
- w
- =
- slink[w];
- }
- minlen[y]
- = maxlen[slink[y]] +
- 1;
- return z;
- }
- char str[maxL];
- queue
- <
- int
- >
- Q;
- int main()
- {
- freopen("a.txt"
- ,
- "r", stdin);
- int N;
- cin
- >>
- N;
- st
- = new_state(
- 0
- ,
- 0
- , NULL, -
- 1);
- while
- (N--
- ){
- cin
- >>
- str;
- int
- len =
- strlen(str);
- for
- (
- int
- i =
- 0
- ; i < len; i++
- ) {
- st
- =
- add_char(str[i], st);
- }
- st
- = add_char(
- ':', st);
- }
- Q.push(0
- ); col[
- 0
- ] =
- 1;
- while
- (!
- Q.empty()){
- int
- x =
- Q.front(); Q.pop();
- for
- (
- int
- c =
- 0
- ; c <
- 10
- ; c++
- ){
- int
- y =
- trans[x][c];
- if
- (y == -
- 1
- )
- continue;
- if
- (!col[y]) Q.push(y); col[y] =
- 1;
- in
- [y]++
- ;
- }
- }
- Q.push(0
- ); sz[
- 0
- ] =
- 1;
- while
- (!
- Q.empty()){
- int
- x =
- Q.front(); Q.pop();
- for
- (
- int
- c =
- 0
- ; c <
- 10
- ; c++
- ){
- int
- y =
- trans[x][c];
- if
- (y == -
- 1
- )
- continue;
- in
- [y]--
- ;
- if
- (
- in
- [y] ==
- 0) Q.push(y);
- (sz[y]
- += sz[x]) %=
- MOD;
- (dp[y]
- += dp[x]*
- 10
- + c*sz[x]) %=
- MOD;
- }
- }
- LL ans
- =
- 0;
- /*
- for(int i = 0; i < n; i++){
- for(int c = 0; c < 10; c++){
- if(trans[i][c] == -1) continue;
- cout<<i<<" "<<trans[i][c]<<" "<<c<<endl;
- }
- }*/
- //for(int i = 0; i < n; i++) cout<<dp[i]<<" "; cout<<endl;
- for
- (
- int
- i =
- 0
- ; i < n; i++) (ans += dp[i]) %=
- MOD;
- cout
- <
- endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2146826.html