随机保险箱劫案AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)Kowasugi Bank has $N$ safes. Safe $i$ contains $A_i$ yen.
One day, a robber entered the bank. The robber repeats the following operation until the total amount stolen reaches at least $X$ yen:
- Choose one safe uniformly at random from the safes not yet opened, open it, and steal all the money inside.
Find the expected value, modulo $998244353$, of the total amount stolen by the robber.
Definition of expected value modulo $998244353$ It can be proved that the expected value sought is always a rational number. Moreover, under the constraints of this problem, it can also be proved that when this value is expressed as an irreducible fraction $\frac{P}{Q}$, it satisfies $Q {{}\not\equiv{}} 0 \pmod{998244353}$. Therefore, there exists a unique integer $R$ satisfying $R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353$. Find this $R$.
Kowasugi 银行有 $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$。AI (CI翻译)
Constraints
约束条件
AI (CI翻译)$1 \le N \le 40$$1 \le A_i \le 10^{16}$$1 \le X \le \sum_{i=1}^{N} A_i$- All input values are integers.
$1 \leq N \leq 40$$1 \leq A_i \leq 10^{16}$$1 \leq X \leq \sum_{i=1}^{N} A_i$- 所有输入值均为整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入从标准输入中以以下格式给出：AI (CI翻译)
N X
A_1 A_2 \ldots A_NN X
A_1 A_2 \ldots A_NOutput
输出格式
AI (CI翻译)Output the answer.
输出答案。AI (CI翻译)
样例
2 5
3 10
499122188
3 2
1 1 1
2
11 60
2 3 5 7 11 13 17 19 23 29 31
525950964
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。