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 翻译