(問題 8) 文字変更 PHP編（paizaランク A 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
(一文字変更においてハッシュ値への影響について)
ここでは、S の文字を変更することを考えます。
S の i 文字目を変更することを考えます。変更後の文字列を V と置きます。
このとき、ハッシュ値計算において、S と V で変わるところは、T_i の値が変更になり、その項の値が変わるのみです。
今回、T_i は T'_i に変わったとします。このとき V のハッシュ値は以下のようになります。
H(V) = T_1 × X ^ {N - 1} + T_2 × X ^ {N - 2} + ... + T'_i × X ^ {N - i} + ... + T_N = T_1 × X ^ {N - 1} + T_2 × X ^ {N - 2} + ... + T_i × X ^ {N - i} + ... + T_N + (T'_i - T_i) × X ^ {N - i} = H(S) + (T'_i - T_i) × X ^ {N - i} (mod P)
このように、H(S) の値に対して差分である (T'_i - T_i) × X ^ {N - i} を足し合わせることで H(V) を計算することが出来ます。
実際に計算してみましょう。
(問題)
素数 P と 2 以上 P - 1 以下の整数 X と長さ N の英大文字列 S が与えられます。Q 個のクエリに対して前から順番に処理してください。i (1 ≦ i ≦ Q) 番目のクエリは以下の通りです。
- 入力される値
-
入力は以下のフォーマットで与えられます。
P X N Q
S
I_1 C_1
I_2 C_2
...
I_Q C_Q- 1 行目には 4 つの整数 P,X,N,Q が与えられます。
- 2 行目には 1 つの文字列 S が与えられます。
- 2 + i (1 ≦ i ≦ Q) 行目には 1 つの整数 I_i と 1 つの英大文字 C_i が与えられます
- 入力は合計で 2 + Q 行からなり、入力値最終行の末尾に改行が 1 つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
答えを Q 行で出力してください。
i (1 ≦ i ≦ Q) 行目には前から i 番目のクエリの答えを出力してください。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
- 10 ^ 8 ≦ P ≦ 2 × 10 ^ 9
- 2 ≦ X ≦ P - 1
- 1 ≦ N ≦ 200000
- 1 ≦ Q ≦ 200000
- S は長さ N の英大文字列
- 1 ≦ I_i ≦ N (1 ≦ i ≦ Q)
- C_i は英大文字 (1 ≦ i ≦ Q)
- P は素数
- 入力例1
-
1000000007 77777 14 7
HELLOWORLDNANA
1 G
4 O
7 O
2 D
14 B
13 Y
7 E
- 出力例1
-
792612268
411858279
411858279
311466064
311466065
312321612
686941116
