← 返回题目列表

Codeforces · 1477/F

F. Nezzar 和巧克力棒

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

Nezzar 买了他最喜欢的零食 — $$$n$$$ 巧克力棒,长度为 $$$l_1,l_2,\ldots,l_n$$$。然而,巧克力棒可能太长而无法正确储存!

为了解决这个问题,Nezzar 设计了一个有趣的过程,将它们分成小块。首先,内扎尔将他所有的巧克力棒放入一个黑盒子中。然后,他将重复执行以下操作,直到所有巧克力棒的最大长度不超过$$$k$$$。

- Nezzar 从盒子里取出一块巧克力,概率与其长度 $$$x$$$ 成正比。
- 在步骤 $$$1$$$ 之后,Nezzar 统一选择一个实数 $$$r \in (0,x)$$$ 并将所选巧克力棒分成长度为 $$$r$$$ 和 $$$x-r$$$ 的两块巧克力棒。
- 最后,他把那两块新巧克力放入黑盒子里。

Nezzar 现在想知道,他将执行将巧克力棒分成小块的预期操作次数是多少。

可以证明,答案可以表示为 $$$\frac{P}{Q}$$$,其中 $$$P$$$ 和 $$$Q$$$ 是互质整数,$$$Q \not \equiv 0$$$ ($$$\bmod 998\,244\,353$$$)。打印 $$$P\cdot Q^{-1} \mod 998\,244\,353$$$ 的值。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 50, 1 \le k \le 2000$$$)。

第二行包含 $$$n$$$ 整数 $$$l_1, l_2, \ldots, l_n$$$ ($$$1 \le l_i$$$, $$$\sum_{i=1}^{n} l_i \le 2000$$$)。

输出

打印一个整数 - Nezzar 将其巧克力棒分成小块的预期操作数,以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

1 1
2

输出 #1

4

输入 #2

1 1
1

输出 #2

0

输入 #3

1 5
1234

输出 #3

15630811

输入#4

2 1
2 3

输出#4

476014684

输入 #5

10 33
10 20 30 40 50 60 70 80 90 100

输出 #5

675105648