題目s：

PS:前兩題可以交換作法試試看喔～

• 洛谷 P3370 (hash 模板題)
• ZJ d518 (Trie 模板題)
• TIOJ 1281 (hash 變形題)
• TIOJ 1515 (hash 變形題)

${5695138290}_{(10)}$

$\sum _{i=0}^9{10}^i\times digi{t}_i$
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

$A_1,A_2,...,A_n$

$S_1=A_1$

$S_2=A_1+A_2$

$S_3=A_1+A_2+A_3$

$S_4=A_1+A_2+A_3+A_4$

$S_5=A_1+A_2+A_3+A_4+A_5$

Hash

• 字串編碼！！
• 這裡使用 Rabin-Karp rolling hash
• 字串
  $S$ 長度
  $n$
• 假設質數
  $p=65537$，
  $M={10}^9+7$
• 記得都要取模
  
  $$\sum _{i=0}^{|S|-1}{p}^i\times S[i]$$
  
  $$\sum _{i=0}^{|S|-1}{p}^{|S|-1-i}\times S[i]$$
• 前綴hash值：
  
  $$pre[i]=\sum _{j=0}^i{p}^{i-j}\ast S[j]$$
• 然後，
  
  $$pre[j]=pre[j-1]\ast p+S[j]$$
• 某一段的hash：
  
  $$hash(i,j)=pre[j]-pre[i-1]\ast p^{j-i+1}$$

補：HASH碰撞機率

• 生日問題～
• 推導過程超出高中數學範圍，在此忽略
• 碰撞機率概算公式：（
  $N$為字串數量，
  $M$為可能值得數量 空間 值域大小）
  
  $$1-exp(-N^2/(2\times M))$$
  
  $$1-e^{-N^2/(2\times M)}$$

Trie

• 就是字典樹～
  
• 圖片來源：https://github.com/Vercaca/Trie
• 實做遇到困難可以相互討論一下喔～