1457 . 三色豆
TopCoder
Tags
Description
虹夏在文化祭時收到了 $N$ 串三色豆，三色豆由紅蘿蔔、玉米、青豆組成，大人小孩都愛吃，虹夏也不例外。但由於這是他在整個祭典的最後一餐，他想要把這些三色豆再變得好吃一點。
首先，由於虹夏不喜歡吃青豆（在想什麼），他已經先把所有青豆拔掉了（在想什麼）。
接下來虹夏會開始品嚐，他定義一串的美味程度如下：一開始美味程度是 $0$，接下來虹夏會從左邊開始一顆一顆吃，每吃一顆他就會把美味程度乘上 $2$。因為虹夏很喜歡吃玉米，因此如果遇到的這顆是玉米，他就會再額外把美味程度加上 $1$。而虹夏的總滿足度就是每一串的美味程度加起來。
例如當前這串從左到右分別是玉米、紅蘿蔔、玉米的話，那美味程度的變化會是 $0 \rightarrow 1$ （玉米）$ \rightarrow 2$ （紅蘿蔔） $\rightarrow 5$（玉米）。因此整串的美味程度是 $5$。
虹夏想叫喜多施下變好吃的魔法，因為喜多的代表色是紅色，假設有一串三色豆（現在可能只能叫做兩色豆了）有兩顆紅蘿蔔相鄰，那喜多可以把其中一顆紅蘿蔔拿出來，然後選擇一串在任意位置插入一個紅蘿蔔。但喜多剛剛在蛋包飯上耗費太多魔力了，因此為了節省力氣，假設紅蘿蔔被合併的那串的編號是 $i$，而被插入紅蘿蔔的那串的編號是 $j$，那麼必須滿足 $i < j$。另外，喜多使用的魔法無次數限制。
現在虹夏也很好奇，他給了你 $Q$ 筆詢問，第 $i$ 筆詢問是有兩個數字 $K_i, P_i$，代表如果虹夏打算吃前 $K_i$ 串，那他最多可以獲得多少的總滿足度，由於數字可能很大，請輸出他模 $P_i$ 的餘數。每筆詢問之間彼此是獨立的。
Input Format
輸入第一行是一個正整數 $T$，代表接下來有幾筆子測試資料。
每筆子測試資料的第一行是兩個以空白分隔的整數 $N, Q$。
接下來有 $N$ 行，第 $i$ 行是一個 $01$ 字串 $S_i$，代表編號為 $i$ 的那串從左到右分別是哪些蔬菜，$0$ 代表這顆是胡蘿蔔，$1$ 代表這顆是玉米。
接下來有 $Q$ 行，第 $i$ 行有兩個整數 $K_i, P_i$。
- $1 \leq T \leq 10^ 4$
- $1 \leq N, Q \leq 10^ 5$
- $|S_i| \leq 100$
- $S_i$ 只會有
0、1兩種字元 - $1 \leq K_i \leq N$
- $1 \leq P_i \leq 10^ 9$
- 所有 $N$ 的總和不超過 $10^ 5$
- 所有 $Q$ 的總和不超過 $10^ 5$
Output Format
在每筆子測試資料中，對每筆詢問輸出一個以空白分隔的整數，代表虹夏能獲得的最大總滿足度。
Sample Input 1
2 3 2 10001 0010 101 2 998244353 3 998244353 5 5 1001 0101 0001 101 1 1 5 2 10 3 13 4 7 5 6
Sample Output 1
19 47 4 5 3 2 4
Sample Input 2
2 6 6 1101 01111 0111 0 00001 11110 5 687059566 2 207082441 3 371142957 4 486938771 4 386563287 5 678336887 6 6 101 010 1 0 1 101 1 905065004 4 223743463 2 237870506 5 558732061 5 527465867 2 105508292
Sample Output 2
36 28 35 35 35 36 5 8 7 9 9 7
Hints
在範測一中，第一個子測試資料有三串三色豆：
- 對於第一個詢問我們只考慮前兩串，這時候最佳的方案是完全不要施展魔法，這樣會有 $17 + 2 = 19$ 的總滿足度。
- 對於第二個詢問，最佳的方案是施展魔法把第一串與第二串的所有相鄰紅蘿蔔都插入到第三串上，並都插入到第三串的最後，這樣第一串剩下
101，第二串剩下010，第三串變成101000，總滿足度是 $5 + 2 + 40 = 47$。
在範測二中，每個詢問的結果分別是 $9, 15, 16, 51, 52$，因此模各自的 $P_i$ 後變成 $4, 5, 3, 2, 4$。
這也是你們營隊期間的的最後一題，享受題目！
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資。 | 0 |
| 2 | 0~48 | 無特別限制。 | 100 |