FFT 模板二代，簡單易用、精度高 驗證模板正確性 Uva12298 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 10... Read more 27 Jul 2017 - 11 minute read
FFT + 卷積 在這裡做個筆記，假設有兩個數字 123, 567 要相乘，其實就是 下面的向量向右捲動、卷積。 題目傳送門 ZeroJudge a577 程式碼 FFT 還是套 ZOJ 那題來的模板~ 只有修改一小部分 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78... Read more 27 Jul 2017 - 5 minute read
2D Rolling Hash 這題也可以用 Rolling Hash 做，但是要注意碰撞（WA 了無數次）， X, Y 各用兩組 base ，共用一組 Mod 就可以避免碰撞。 2D Rolling Hash 可以戳這裡了解 題目傳送門 Timus 1486 程式碼 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 7... Read more 25 Jul 2017 - 8 minute read
2D Rolling Hash 題目傳送門 POJ 3690 解法 私認為沒什麼參考價值，因為這個算法複雜度太高。 改用其他字串演算法應該會快很多。 因為只有 ‘*’, ‘0’ 兩種字元，就乾脆不 mod 了， 可以搶一點速度。 總之，算法就是先把要搜尋的 NxM 矩陣 Rolling Hash 起來， 然後對每個輸入的 pattern 做 hash ，把它塞進一個 map ， map 的 Key 存 pattern 的 hash 值， value 用來數次數。 輸入完後，利用 NxM 的矩陣得到的 hash 值，判斷在 map 內的 pattern 是否有出現 ，如果有，累計次數、該 pattern 從 map 移除。 最後輸出累計結果。 程式碼 1 2 ... Read more 25 Jul 2017 - 3 minute read
2D Rolling Hash 模板 實作方式 前置動作 要準備兩個 hash 時要使用的 base (質數) ，一個給 X 方向用、一個給 Y 方向用， 還有一個 hash 時要用的 Mod 數 (質數) 。 在產生 hash 時，X 和 Y 方向的 Mod 數必須一致，才可以得到正確結果。 產生 2D 的方法與 “子矩陣求和” 用的方法類似， 以子矩陣求和為出發點 假設我們有一個矩陣 A ，要在 內回答矩陣 A 內的某個子矩陣總和， 例如： 。我們可以先求出各種 的總和， 為了方便起見，我們將上面的 總和定義為 代表從 A 最左上角 累計到 的矩陣內數字總和， 然後 就可以看成， 從 往下找 的子矩陣（包含），就會是 S 就是 A ... Read more 25 Jul 2017 - 7 minute read