分数: 625 点
问题陈述
有 N 盒子里的卡片。每张卡片上都写有一个整数,介于 1 和 M,包括在内。对于每个 i=1,\ldots,M,有 C_i 卡片编号 上面写着 i 。
从空笔记本开始,重复以下操作:
- 从盒子里随机抽一张牌。将卡上的整数写在笔记本中,然后将卡放回盒子中。
求期望值,模 998244353,执行操作的次数,直到笔记本拥有来自 1 to M 至少写过一次。
如何求期望值模 998244353
可以证明此问题中寻求的期望值始终是有理数。此外,该问题的约束保证当期望值表示为不可约分数时 \frac yx,分母 x 不能被整除 998244353。 那么,还有一个独特的 0\leq z\lt998244353 这样 y\equiv xz\pmod{998244353}。打印此内容 z.约束
- 1 \leq M \leq N \leq 2\times 10^5
- 1 \leq C_i
- \sum_{i=1}^{M}C_i=N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M C_1 \ldots C_M
输出
打印答案。
示例输入 1
2 2 1 1
示例输出 1
3
这一系列操作可以如下进行:
- 你抽一张牌 上面写着 1 。笔记本现在有一个 里面写着 1 。
- 你再次抓一张牌 上面写着 1 。笔记本现在有两个 里面写着 1。
- 你抽一张牌 上面写着 2 。笔记本现在有两个 里面写着 1和一 2 。
寻求的期望值为 2\times\frac{1}{2}+3\times\frac{1}{4}+4\times\frac{1}{8}+\ldots=3.
示例输入 2
5 2 4 1
示例输出 2
748683270
预期值为 \frac{21}{4},其表示模 998244353 is 748683270.
示例输入 3
50 50 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
示例输出 3
244742906
预期值为 \frac{13943237577224054960759}{61980890084919934128}.
示例输入 4
74070 15 1 2 3 11 22 33 111 222 333 1111 2222 3333 11111 22222 33333
示例输出 4
918012973