← 返回题目列表

AtCoder · abc412_f

I. 袜子 4

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

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