← 返回题目列表

AtCoder · abc464_f

F. 随机金库抢劫

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

分数: 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