分数: 525 点
问题陈述
在高桥的抽屉柜里,有袜子 N 颜色,带有 A_i 彩色袜子 i.
最初,高桥有一只彩色袜子 C 在抽屉柜外面,与这些袜子分开,并重复以下操作,直到满足终止条件:
- 统一随机抽奖 1 抽屉柜里的袜子。然后,如果他抽屉柜外的两只袜子颜色相同,则终止操作。否则,选择其中一只袜子并将其放回抽屉柜中。他总是选择将袜子放回去,以尽量减少未来袜子抽出的预期次数。
找到期望的数字,模数 998244353,袜子绘制直到操作终止。
求期望值模 998244353
在这个问题的约束下,可以证明期望值存在并且是一个有理数。 还可以证明,当这个值表示为不可约分数时 \frac{P}{Q} (Q > 0),我们有 Q \not\equiv 0 \pmod{998244353}。 因此,唯一存在一个整数 R 满意 R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353。 求期望值模 998244353 意味着找到这个值 R.
约束
- 1 \leq N \leq 3 \times 10^5
- 1 \leq C \leq N
- 1 \leq A_i \leq 3000
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N C A_1 A_2 \ldots A_N
输出
输出答案。
样本输入 1
3 2 3 1 2
示例输出 1
249561092
预计抽签次数为 \frac{15}{4}.
示例输入 2
8 4 4 1 6 2 5 1 7 3
示例输出 2
393623786