分数: 550 点
问题陈述
小和杉银行有 N 保险箱。安全 i 包含 A_i 日元。
有一天,一名劫匪进入了银行。抢劫者重复以下操作,直到被盗总金额至少达到 X 日元:
- 从尚未打开的保险箱中统一随机选择一个保险箱,打开它,偷走里面的所有钱。
求期望值,模 998244353,占强盗偷走的总金额的比例。
期望值模的定义 998244353
可以证明,所求的期望值始终是有理数。而且,在这个问题的约束下,还可以证明,当这个值表示为不可约分数时 \frac{P}{Q},它满足 Q {{}\not\equiv{}} 0 \pmod{998244353}。因此,存在唯一的整数 R 满意 R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353。找到这个 R.
约束
- 1 \le N \le 40
- 1 \le A_i \le 10^{16}
- 1 \le X \le \sum_{i=1}^{N} A_i
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N X A_1 A_2 \ldots A_N
输出
输出答案。
示例输入 1
2 5 3 10
示例输出 1
499122188
第一个保险箱打开有两种选择。
如果安全的话 1 先被打开,强盗也打开保险箱 2,所以被盗的总金额是 13 日元。
如果安全的话 2 首次打开,总数已达到至少
此时 X 日元,因此被盗总金额为 10 日元。
因此,预期值为 \frac{13 + 10}{2} = \frac{23}{2}.
示例输入 2
3 2 1 1 1
示例输出 2
2
无论打开顺序如何,两个保险箱被打开时被盗的总金额为 2 日元。因此,期望值为 2.
示例输入 3
11 60 2 3 5 7 11 13 17 19 23 29 31
示例输出 3
525950964