AT_k2pc001_h5 暗号化(Encipherment)

[problemUrl]: https://atcoder.jp/contests/k2pc-hard/tasks/k2pc001_h5 kagamizは, ハッシュについて勉強をしている. kagamizはローリングハッシュについて蟻本で学び, ハッシングが文字列探索に有効な手法だということを知った. そこで, kagamizは, 任意の多重集合についてハッシングすることが出来ないかということを考え, 以下のようなハッシュ関数を考案した. 「 Pを素数とする. ハッシュ化する列を $ {x_1,x_2,x_3,...,x_n} $ とし, 全ての $ x_i $について, $ j≦i $かつ $ x_j=x_i $が成り立つような $ j $の個数を$ C_i $とすると, (ハッシュ値) $ = $ $ Σx_i^{C_i} $ mod $ P $ 」 このハッシュ関数は容易に衝突ケースが作れてしまうが, ともかくこの関数を用いた以下の問題をあなたに解かせることにした. **問題**： 長さ$ N $の数列$ {a_1,a_2,a_3,...,a_N} $ がある. この数列の $ Q $ 個の部分列について, それぞれ前述のハッシュ値を求めなさい. > $ N $ $ Q $ $ P $ $ a_1 $ $ a_2 $ $ ... $ $ a_N $ $ s_1　t_1 $ $ s_2　t_2 $ . . . $ s_Q　t_Q $ 最初に数列の長さ $ N $ , ハッシュ値を求めたい連続した部分列の個数 $ Q $ , 素数 $ P $ が与えられる. 次に, 長さ $ N $ の数列 $ {a_1,a_2,..,a_N} $ が与えられる. 最後に, $ Q $個の部分列の端点\[$ s_i $, $ t_i $\]が与えられる. $ Q $個の部分列に対して, 数列中で $ s≦i≦t $ を満たす項に対して, 問題文のハッシュ関数を用いて得たハッシュ値を改行区切りで出力せよ. - $ 1\ ≦\ N\ ≦\ 10^5 $ 数列の長さ - $ 1\ ≦\ Q\ ≦\ 10^5 $ ハッシュ値を求めたい連続した部分列の個数 - $ 1\ ≦\ P\ ≦\ 10^9 $ ハッシュ関数で用いる素数 - $ 1\ ≦\ a_i\ ≦\ 10^6 $ 数列の各項の値 - $ 1\ ≦\ s_i\ ≦\ t_i\ ≦\ N $ 各部分列の端点 配点の $ 20% $ 分については, $ i≠j $のとき$ a_i≠a_j $ を満たす. ``` 10 10 8999 2 1 1 2 1 2 1 2 1 2 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 ``` ``` 2 3 4 8 9 17 18 34 35 67 ``` ``` 6 6 2 1 2 3 4 5 6 1 2 2 3 3 4 4 4 5 5 6 6 ``` ``` 1 1 1 0 1 0 ```

N/A

N/A