CF1418E Expected Damage

你正在玩一款电脑游戏。在这款游戏中，你需要与 $n$ 个怪物战斗。 为了防御怪物，你需要一面盾牌。每面盾牌有两个参数：当前耐久度 $a$ 和防御力 $b$。每个怪物只有一个参数：它的力量 $d$。 当你用当前耐久度为 $a$、防御力为 $b$ 的盾牌与力量为 $d$ 的怪物战斗时，有三种可能的结果： - 如果 $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 \times 10^5$）——怪物的数量和盾牌的数量。 第二行包含 $n$ 个整数 $d_1, d_2, \ldots, d_n$（$1 \le d_i \le 10^9$），其中 $d_i$ 表示第 $i$ 个怪物的力量。 接下来 $m$ 行，每行包含两个整数 $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$ 关于 $998244353$ 的逆元（即 $y \cdot y^{-1} \bmod 998244353 = 1$）。

由 ChatGPT 4.1 翻译