← 返回题目列表

AtCoder · k2pc001_h5

E. 加密

中文机器翻译题面 查看原题

問題文

kagamiz 正在研究哈希。
Kagamiz 从 Arimoto 那里了解了滚动哈希,并了解到哈希是搜索字符串的有效方法。

因此,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} 模组 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 很满意。


入力例 1

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

出力例 1

2
3
4
8
9
17
18
34
35
67

入力例 2

6 6 2
1 2 3 4 5 6
1 2
2 3
3 4
4 4
5 5
6 6

出力例 2

1
1
1
0
1
0
(故事)kyuridenamida
(问题)kyuridenamida
(测试仪)fura2

kyuridenamida:“顺便说一句,这个问题根本不涉及加密。”