0w1

Hash

CFR 639 C. Bear and Polynomials ( Hash )

Problem - C - Codeforces題意: 給你 N 次多項式 F()。 係數的絕對值不能超過 K。 問你修改一個值之後,F( 2 ) = 0 的方案數。 特別的,A[ N ] != 0。制約: 1 ≤ N ≤ 2e5 abs( K ) ≤ 1e9解法: 哈希水掉。 原本不能暴力算的原因只是因為數字會太大,不過哈…

CFR 611 D. New Year and Ancient Prophecy ( DP, Hash, LCP )

Problem - 611D - Codeforces題意: 給你一個大數。要求分割成若干個數字,滿足嚴格遞增,而且沒有領導 0。 問方案數對 1e9 + 7 取模。制約: 1 ≤ N ≤ 5000 保證第一個字符不為 '0'。解法: dp[ i ][ j ]:最後一個數字是 S[ i : j ] 時的方案數。 想知道 dp…

POI 2 Stage 1 Palindromes ( DP, Hash )

http://main.edu.pl/en/archive/oi/2/pal題意: 給一個字串,問最多和最少可以拆分成幾個偶數長度迴文,存在的話輸出方案。資料規模: The standard input contains one word consisting of at least 1 and at most 200 small letters of English alphabet. …

CFR 128 B. String ( Hash, PFS )

Problem - B - Codeforces題意: 給一個字串,你要把所有子字串 ( 只要下標不同即不同 ) 生出來後輸出字典序第 K 個的字串。資料規模: N, K ≤ 1e5 TL: 1000 ms ML: 256 MB解法: 因為 K 很小,所以按字典序小的出隊,接上自己後一個字符再丟回一個優先隊列…

IOICJ 88 Necklace 2 ( Hash )

Problem Description: lo has a string Slo, and li has a string Sli. You want to find the maximum length of common palindrome substring of both strings.Constraints: 1≤T≤30 1≤|Slo|,|Sli|≤100000Sample Input: 2 abaxyza xyzaaba abaxyzwvcddcpirik…

CFR 7 D. Palindrome Degree ( Hash, DP, Palindrome )

Problem - D - Codeforces題意: f( s ) = k, if f( s[ 0, s.len / 2 ) ) = f( s[ ( len + 1 ) / 2, s.len ) ) = k - 1, _______= 0, otherwise 給字串 seq,求 Sigma{ f( s ), for all s is prefix substring of seq }資料規模: 字串長度 ≤ 5e6 TL: 500 ms…

CFR 757 C. Felicity is Coming! ( Hash )

Problem - C - Codeforces題意: 有 N 個道館,裡面都有若干隻怪獸。怪獸用一個整數描述,表示品種。現在要定義一個一對一 ( 雙向 ) 函數,把 { 1, 2, .. M } 映射到任意一個 [ 1, M ] 的排列。求有多少種這樣的一對一函數,滿足分別將每個道館的怪獸經過函…

Yuki 313 π ( Hash )

No.313 π - yukicoder 間違ってる位置を知らなくていいので、愚直に 0 ~ 9 それぞれの登場回数を比較すればいい。 しかし素数を base にして hash すると間違ってる位置がわかる。 kmjp.hatenablog.jp 素数は 10 以上のだけを使うのに注意。 #include <bits/stdc++.h> using</bits/stdc++.h>…

CFR 126 B. Password ( Hash + Binary Search )

Problem - 126B - Codeforces 題意: 給一個字串,求最長子字串,滿足存在一個前綴和它相等,一個後綴和它相等,一個非前綴也非後綴也和它相等。 解法: 先預處理字串的 rolling hash,接著把滿足所有前綴和後綴相等的長度押入一個有序容器。 接著對那個容器…

CFR 633 C. Spy Syndrome 2 ( String hash + DP )

Problem - C - Codeforces Reverse the text, and perform dynamic programming to mark if some index i is possible to be reached from some index j, and the word it should use to reach from j to i. Make use of Rabin-Karp hashing to accelerate w…

Hacking hash algorithms on string with birthday attack

Many people are familiar with hash algorithms on string because they are easy to write. However, not many are really aware of the probability of collision. Like me, I had always thought the probability of collision is ( 1 / MOD ), and I ha…