HDU_1457_尾碼自動機四·重覆旋律7

来源:http://www.cnblogs.com/edward108/archive/2017/10/10/7643894.html
-Advertisement-
Play Games

#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 }

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 預設情況下,每一個MVC請求的HTTP Header中都會包含著當前伺服器的一些信息,出於安全還是性能還是處女座的強迫症等等,都想把這些信息移除掉,增加一些應用程式的神秘感,如下,預設情況下Chrome中截獲的HTTP Header信息: Cache-Control:private, s-maxag... ...
  • AI聖經 深度學習領域奠基性的經典暢銷書!長期位居美國亞馬遜AI和機器學習類圖書榜首!所有數據科學家和機器學習從業者的必讀圖書!特斯拉CEO埃隆·馬斯克等國內外眾多專家推薦! 深度學習是機器學習的一個分支,它能夠使電腦通過層次概念來學習經驗和理解世界。因為電腦能夠從經驗中獲取知識,所以不需要人類 ...
  • 作業1: 需求:輸出一個由 * 符號所組成的矩形,要求每行有50個 * ,一共需要有60行。使用雙重for迴圈完成。 作業2: 需求:輸出一個由 * 符號所組成的三角形,要求第一行一個 * ,第二行 兩個 * 第三行 三個 * 依次類推,最後一行10個 *。使用雙重for迴圈完成。 作業3: 需求: ...
  • A Magic Lamp Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 4694 Accepted Submission(s): 1947 Pr ...
  • cookie與session都是保存會話數據的技術 cookie存放在用戶端的磁碟中,瀏覽器一般只允許存放300個cookie,且每一個站點最多存放20個cookie,每個cookie的大小限製為4kb;當用戶需要記住自己的用戶名與密碼的時候,事件發生在用戶本地瀏覽器,所以使用cookie技術。co ...
  • Check Corners Time Limit: 2000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3247 Accepted Submission(s): 1173 ...
  • # -*- coding: -*- import io LIMIT = 150000 file_count = 0 url_list = [] with io.open('D:\DB_NEW_bak\DB_NEW_20171009_bak.sql','r',encoding='utf-16') as... ...
  • 【轉】JVM介紹 1. 什麼是JVM? JVM是Java Virtual Machine(Java虛擬機)的縮寫,JVM是一種用於計算設備的規範,它是一個虛構出來的電腦,是通過在實際的電腦上模擬模擬各種電腦功能來實現的。Java虛擬機包括一套位元組碼指令集、一組寄存器、一個棧、一個垃圾回收堆和一 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...