← 返回题目列表

AtCoder · abc352_g

G. 袜子 3

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

分数: 600 点

问题陈述

高桥的抽屉柜里有各种颜色的袜子。 袜子的颜色由整数表示 1 to N,并且有 A_i\ (\geq 2) 彩色袜子 i.

他将通过执行以下操作来选择今天穿哪只袜子:

  • 继续以相同的概率一次从箱子中随机抽取一只袜子,直到他可以用已经抽取的袜子制作出一双相同颜色的袜子。 袜子一旦被抽出,就不会再放回箱子里。

求期望值,模 998244353,他必须从胸部抽出袜子的次数。

求期望值模是什么意思 998244353? 可以证明,所求的期望值总是有理数。 此外,该问题的约束保证如果期望值表示为不可约分数 \frac{y}{x},那么 x 不能被整除 998244353。 这里,存在一个唯一的整数 z 之间 0 和 998244352,包含在内,这样 xz \equiv y \pmod{998244353}。找到这个 z.

约束

  • 1\leq N \leq 3\times 10^5
  • 2\leq A_i \leq 3000
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \dots A_N

输出

打印答案。


示例输入 1

2
2 2

示例输出 1

665496238

例如,可以执行如下操作:

  1. 画一只彩色袜子 1 从胸部。只剩下一只颜色的袜子 1 和两只彩色袜子 2 在胸部。
  2. 画一只彩色袜子 2 从胸部。每种颜色还剩下一只袜子 1 和 2 在胸部。
  3. 画一只彩色袜子 1 从胸部。目前绘制的袜子有两种颜色 1 和其中一种颜色 2,允许一对颜色 1 袜子即将制作,从而结束操作。

在此示例中,高桥从胸部抽出袜子 3 次。

高桥从胸部抽出袜子的预期次数是 3 有概率 \frac{2}{3} 和 2 有概率 \frac{1}{3},所以期望值为 3\times \frac{2}{3} + 2\times \frac{1}{3} = \frac{8}{3} \equiv 665496238 \pmod {998244353}.


示例输入 2

1
352

示例输出 2

2

示例输入 3

6
1796 905 2768 253 2713 1448

示例输出 3

887165507