← 返回题目列表

Codeforces · 1418/E

E. 预期损坏

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

您正在玩电脑游戏。在这个游戏中,你必须与 $$$n$$$ 怪物战斗。

为了防御怪物,你需要盾牌。每个盾牌都有两个参数:当前的耐久度 $$$a$$$ 和防御等级 $$$b$$$。每个怪物只有一个参数:其强度 $$$d$$$。

当你与力量为 $$$d$$$ 的怪物战斗,同时拥有当前耐久值 $$$a$$$ 和防御力 $$$b$$$ 的护盾时,有三种可能的结果:

- 如果$$$a = 0$$$,那么你会受到$$$d$$$伤害;
- 如果$$$a > 0$$$且$$$d \ge b$$$,你不会受到任何伤害,但护盾当前的耐久度会降低$$$1$$$;
- 如果 $$$a > 0$$$ 且 $$$d < b$$$,则什么也不会发生。

第 $$$i$$$ 个怪物的强度为 $$$d_i$$$,并且你将以某种随机顺序与每个怪物战斗一次(所有 $$$n!$$$ 顺序都是等概率的)。你必须考虑$$$m$$$不同的护盾,第$$$i$$$个护盾具有初始耐久度$$$a_i$$$和防御等级$$$b_i$$$。对于每个盾牌,计算如果您拿起该盾牌并以随机顺序与给定的 $$$n$$$ 怪物战斗,您将受到的预期伤害量。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — 分别是怪物数量和护盾数量。

第二行包含 $$$n$$$ 整数 $$$d_1$$$, $$$d_2$$$, ..., $$$d_n$$$ ($$$1 \le d_i \le 10^9$$$),其中 $$$d_i$$$ 是第 $$$i$$$ 个怪物的强度。

接下来是 $$$m$$$ 行,其中第 $$$i$$$ 包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i \le n$$$; $$$1 \le b_i \le 10^9$$$) — 第 $$$i$$$ 屏蔽的描述。

输出

打印 $$$m$$$ 整数,其中第 $$$i$$$ 个整数表示使用第 $$$i$$$ 个护盾所受到的预期伤害,如下所示:可以证明,对于每个护盾,预期伤害是一个不可约分数 $$$\dfrac{x}{y}$$$,其中 $$$y$$$ 与$$$998244353$$$。您必须打印 $$$x \cdot y^{-1} \bmod 998244353$$$ 的值,其中 $$$y^{-1}$$$ 是 $$$y$$$ 的逆元素 ($$$y \cdot y^{-1} \bmod 998244353 = 1$$$)。

示例

输入 #1

3 2
1 3 1
2 1
1 2

输出 #1

665496237
1

输入 #2

3 3
4 2 6
3 1
1 2
2 3

输出 #2

0
8
665496236