問題文
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]。 对于
出力
制約
- 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
(测试仪)fura2
kyuridenamida:“顺便说一句,这个问题根本不涉及加密。”