#1457 : 尾碼自動機四·重覆旋律7 #1457 : 尾碼自動機四·重覆旋律7 時間限制:15000ms 單點時限:3000ms 記憶體限制:512MB 描述 小Hi平時的一大興趣愛好就是演奏鋼琴。我們知道一段音樂旋律可以被表示為一段數構成的數列。 神奇的是小Hi發現了一部名字叫《十進位進行曲大全 ...
#1457 : 尾碼自動機四·重覆旋律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
- 給出n個數串然後求出所有數串中所有子數串的sum
- 如果一個一個的字串來求就要造n個自動機
- 至於計算過程就是對於每一個節點延伸到下一個節點過程中將當前sum乘10之後加上到下一個節點的單個數乘以當前字串出現次數的乘積即可
- 那麼這樣的計算方式沒有問題但是建立n個SAM耗時太長了
- 那麼我們可不可以減少SAM的建立呢？
- 還是可以的，只要把全部的字串用“:”鏈接，之後再建立SAM即可
- 在這裡我們總的計算方式是不變的
- 但是對於一個出現過“：”的字串是不應該進行計算的，因為如果出現“：”就代表著當前字串包含至少兩個原始串
- 所以我們現在的問題是怎樣辨別當前字串中是否出現過“：”
- 我們可以通過在字串出現次數這裡做文章，對於字串中出現“：”的我們可以通過把字串出現次數標記為0，在進行計算的過程中我們相當於沒有對於當前待操作節點sum進行更新即可。那麼這裡對於cnt的計算可以通過普通的拓撲排序進行，在排序過程中只對於0到9的的路徑進行記錄
- 之後就是從根節點進行一次bfs即可
- 我的代碼里把以上的cnt的計算和計算最終結果的bfs合併在一起了，用一個拓撲解決了
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 #include <climits> 7 #include <cmath> 8 #include <vector> 9 #include <queue> 10 #include <stack> 11 #include <set> 12 #include <map> 13 using namespace std; 14 typedef long long LL ; 15 typedef unsigned long long ULL ; 16 const int maxn = 1e6 + 10 ; 17 const int inf = 0x3f3f3f3f ; 18 const int npos = -1 ; 19 const LL mod = 1e9 + 7 ; 20 const int mxx = 100 + 5 ; 21 const double eps = 1e-6 ; 22 const double PI = acos(-1.0) ; 23 struct topo{ 24 int len, st; 25 topo(int x, int y){ 26 len=x; st=y; 27 } 28 }; 29 bool topocmp(const topo &l, const topo &r){ 30 return l.len<r.len; 31 } 32 struct SAM{ 33 struct node{ 34 int len; 35 int link, go[26]; 36 LL cnt, val; 37 }; 38 node state[maxn<<1]; 39 int n, tot, root, last; 40 void init(char *str){ 41 n=strlen(str); 42 tot=1; 43 root=1; 44 last=1; 45 memset(&state,0,sizeof(state)); 46 state[root].cnt=1LL; 47 } 48 void extend(int w){ 49 tot++; 50 int p=last; 51 int np=tot; 52 state[np].len=state[p].len+1; 53 state[np].cnt=0LL; 54 // state[np].cnt=(w==10?1LL:0LL); 55 state[np].val=0LL; 56 while(p && state[p].go[w]==0){ 57 state[p].go[w]=np; 58 p=state[p].link; 59 } 60 if(p==0){ 61 state[np].link=root; 62 }else{ 63 int q=state[p].go[w]; 64 if(state[p].len+1==state[q].len){ 65 state[np].link=q; 66 }else{ 67 tot++; 68 int nq=tot; 69 state[nq].len=state[p].len+1; 70 state[nq].cnt=state[q].cnt; 71 state[nq].val=0LL; 72 memcpy(state[nq].go,state[q].go,sizeof(state[q].go)); 73 state[nq].link=state[q].link; 74 state[q].link=nq; 75 state[np].link=nq; 76 while(p && state[p].go[w]==q){ 77 state[p].go[w]=nq; 78 p=state[p].link; 79 } 80 } 81 } 82 last=np; 83 } 84 void build(char *str){ 85 init(str); 86 for(int i=0;i<n;i++) 87 extend(str[i]-'0'); 88 } 89 LL calsum(void){ 90 LL ans=0LL; 91 std::vector< topo > v; 92 for(int i=root;i<=tot;i++) 93 v.push_back(topo(state[i].len,i)); 94 sort(v.begin(),v.end(), topocmp); 95 int sz=v.size(), p, q; 96 for(int i=0;i<sz;i++){ 97 p=v[i].st; 98 for(int j=0;j<10;j++) 99 if(state[p].go[j]){ 100 q=state[p].go[j]; 101 state[q].cnt+=state[p].cnt; 102 state[q].val=(state[q].val + ((10LL*state[p].val)%mod + ((LL)j*state[p].cnt)%mod)%mod)%mod; 103 } 104 ans=(ans+state[p].val)%mod; 105 } 106 ans=(ans+mod)%mod; 107 return ans; 108 } 109 }; 110 SAM A; 111 int n, lth; 112 char str[maxn]; 113 int main(){ 114 // freopen("in.txt","r",stdin); 115 // freopen("out.txt","w",stdout); 116 while(~scanf("%d",&n)){ 117 lth=0; 118 for(int i=1;i<=n;i++,lth++){ 119 scanf("%s",str+lth); 120 lth=strlen(str); 121 if(i==n){break;} 122 str[lth]=':'; 123 } 124 A.build(str); 125 printf("%lld\n",A.calsum()); 126 } 127 return 0; 128 }
