AT_k2pc001_h5.暗号化(Encipherment)

kagamiz 正在学习哈希。
kagamiz 在《算法竞赛进阶指南》中学习了滚动哈希，并了解到哈希是一种在字符串查找中非常有效的方法。

于是，kagamiz 思考是否可以对任意多重集合进行哈希，并设计了如下的哈希函数。

「
设 $P$ 为素数。要进行哈希的序列为 $ {x_1,x_2,x_3,...,x_n} $，对于每个 $x_i$，令 $C_i$ 表示满足 $j \leq i$ 且 $x_j = x_i$ 的 $j$ 的个数，
则（哈希值）$ = \sum x_i^{C_i} \bmod P $
」

虽然这个哈希函数很容易产生冲突，但无论如何，kagamiz 还是让你用这个函数来解决下面的问题。

问题：给定一个长度为 $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 \leq N \leq 10^5$ 数列长度
• $1 \leq Q \leq 10^5$ 子区间个数
• $1 \leq P \leq 10^9$ 哈希函数使用的素数
• $1 \leq a_i \leq 10^6$ 数列中的每个元素
• $1 \leq s_i \leq t_i \leq N$ 每个子区间的端点

对于 $20\%$ 的数据，保证 $i \neq j$ 时 $a_i \neq 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$、$Q$、$P$，分别表示数列长度、子区间个数和哈希函数使用的素数。
第二行包含 $N$ 个整数 $a_1,a_2,...,a_N$，表示数列。
接下来 $Q$ 行，每行包含两个整数 $s_i$、$t_i$，表示一个子区间的起止位置。

对于每个子区间，输出一行哈希值。

无。

由 ChatGPT 4.1 翻译