154. DAY 4 PH. 字串雜湊

0 Judge

Code: 0


字串雜湊

題目敘述

如果我們給每個字元 $c$ 一個整數 $v_c$,那麼我們就可以遞迴地定義一個字串雜湊函數 $f$:

  1. $f(c) = v_c \pmod{71234}$ ,如果 $c$ 是一個字元
  2. $f(sc) = f(s)\times len(s) + f(c) \pmod{71234}$ ,如果 $s$ 是一個非空字串且 $c$ 是一個字元

對於一個長度為 $L$ 的字串,我們把長度整除 $L$ 的前綴按照長度從小到大編號 $p_1, p_2, ..., p_k$ ,其中 $k$ 是這種前綴的個數,並把這種前綴稱為拆分前綴,因此 $p_1=s_1$ 、 $p_k=s_1 s_2 ... s_L$。

給你 $n$ 個字串,請從每個字串裡選各選出一個拆分前綴出來,使得選出來的拆分前綴的雜湊值總和最小,並且選出來的拆分前綴的編號必須滿足一些條件。

輸入說明

第一行包含兩個正整數 $n,\,m\,(n\le 100, m\le200)$

接下來有一行,包含 $26$ 個整數,對應到 $v_a, v_b, ..., v_z$ 的值。 $(0\le v_a,...,v_z \le 71233)$

接下來有 $n$ 行,每行包含一個字串 $s_i\,(1≤|s_i|≤1000)$,$s_i$ 由小寫英文字母組成 $\sum_1^n |s_i| \le 100,000$

接下來有 $m$ 行,每行包含兩個數字 $x, y (1\le x,y\le n)$ ,代表第 $x$ 個字串所選的拆分前綴編號不能超過第 $y$ 個字串所選的拆分前綴編號

輸出說明

輸出一個整數,代表所選出來的拆分前綴們雜湊值的總和最小是多少

範例輸入 1

2 0
71233 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
ab
bc

範例輸出 1

3

範例輸入 2

2 1
71233 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
ab
bc
1 2

範例輸出 2

6

範例輸入 3

2 0
71233 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a
bc

範例輸出 3

71235

提示

對於一個字串,它從第一個字元開始的子字串稱為它的前綴。


Judge Setting

run-time limit: 1000 ms
memory limit: 64000000 byte
測資數量: 0