← 返回题目列表

Codeforces · 1017/H

H. 电影

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

在《高堡奇人》的世界里,有$$$m$$$不同的电影结局。

Abendsen 拥有一个仓库和一个架子。起初,他在架子上订购了 $$$n$$$ 的电影。在第 $$$i$$$ 个月中,他将执行以下操作:

1. 清空存储器。
2. 将 $$$k_i \cdot m$$$ 影片放入存储器,每个结局为 $$$k_i$$$ 影片。
3. 他会思考一个问题:如果他将架子上的所有影片放入仓库,然后(从仓库中的所有影片中)随机挑选 $$$n$$$ 部影片并重新排列在架子上,则架子上 $$$[l_i, r_i]$$$ 的结局顺序不会改变的概率是多少?注意,他只是想了这个问题,所以架子实际上不会改变。

回答 Abendsen 的所有问题。

令概率为分数 $$$P_i$$$。假设第 $$$i$$$ 个月从存储中取出 $$$n$$$ 影片的方式总数为 $$$A_i$$$,因此 $$$P_i \cdot A_i$$$ 始终是整数。打印每个月 $$$P_i \cdot A_i \pmod {998244353}$$$。

$$$998244353$$$ 是素数,它等于 $$$119 \cdot 2^{23} + 1$$$。

保证不会有超过 $$$100$$$ 不同的 $$$k$$$ 值。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$1 \le n, m, q \le 10^5$$$, $$$n+q\leq 10^5$$$) — 最初上架的电影数量、结局数量和月数。

第二行包含 $$$n$$$ 整数 $$$e_1, e_2, \ldots, e_n$$$ ($$$1\leq e_i\leq m$$$) — 架子上第 $$$i$$$ 部电影的结局。

接下来的 $$$q$$$ 行包含三个整数 $$$l_i$$$、$$$r_i$$$ 和 $$$k_i$$$ ($$$1 \le l_i \le r_i \le n, 0 \le k_i \le 10^5$$$) — 第 $$$i$$$ 查询。

保证不会有超过 $$$100$$$ 不同的 $$$k$$$ 值。

输出

在单独的行中打印每个问题的答案。

示例

输入 #1

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

输出 #1

6
26730
12150
4860

输入 #2

5 5 3
1 2 3 4 5
1 2 100000
1 4 4
3 5 5

输出 #2

494942218
13125
151632

注意

在第二个查询的第一个样本中,将 $$$2 \cdot m$$$ 电影添加到存储中后,存储将如下所示:$$$\{1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4\}$$$。

共有$$$26730$$$种选择影片的方式,使得$$$e_l, e_{l+1}, \ldots, e_r$$$不会被改变,例如$$$[1, 2, 3, 2, 2]$$$和$$$[1, 2, 3, 4, 3]$$$就是这样的方式。

总共有 $$$2162160$$$ 种选择胶片的方法,因此要求您打印 $$$(\frac{26730}{2162160} \cdot 2162160) \mod 998244353 = 26730$$$。