AT_abc249_h [ABC249Ex] Dye Color

题目描述

有 $N$ 个球，每个球编号为 $1$ 到 $N$。最初，第 $i$ 个球被涂上颜色 $A_i$。

颜色用 $1$ 到 $N$ 之间的整数表示。

你需要重复以下操作，直到所有球的颜色都相同为止：

• $N$ 个球的所有子集（包括空集）共有 $2^N$ 个，从中等概率随机选择一个集合。设选中的集合包含的球的编号按升序为 $X_1, X_2, \dots, X_K$。然后，从 $1,2,\dots,N$ 中选取 $K$ 个不同的数，得到一个排列，等概率随机选择一个排列 $P=(P_1,P_2,\dots,P_K)$。接下来，对于每个 $1\le i\le K$，将球 $X_i$ 的颜色改为 $P_i$。

请计算使所有球颜色相同所需操作次数的期望值，结果对 $998244353$ 取模。

这里，从 $(1,2,\dots,N)$ 中选取 $K$ 个不同的数得到的排列，指的是由 $K$ 个 $1$ 到 $N$ 之间互不相同的整数构成的序列。

输入格式

输入为一行，格式如下：

$N\ A_1\ A_2\ \dots\ A_N$

输出格式

输出答案。

输入输出样例 #1

输入 #1

2
1 2

输出 #1

4

输入输出样例 #2

输入 #2

3
1 1 1

输出 #2

0

输入输出样例 #3

输入 #3

10
3 1 4 1 5 9 2 6 5 3

输出 #3

900221128

说明/提示

注释

可以证明，所求的期望值一定是有理数。在本题的约束下，若用互质的两个整数 $P, Q$ 表示为 $\frac{P}{Q}$，则存在唯一的整数 $R$ 满足 $R\times Q\equiv P\pmod{998244353}$ 且 $0\le R<998244353$。请输出这个 $R$。

数据范围

• $2\le N\le 2000$
• $1\le A_i\le N$
• 输入均为整数。

样例解释 1

每次选择大小为 $1$ 的集合，并且操作会一直持续，直到将未选球的颜色改为与之相同。该概率为 $\frac{2}{4}\times\frac{1}{2}=\frac{1}{4}$，因此期望操作次数为 $4$。

样例解释 2

由于一开始所有球的颜色都相同，因此不需要进行任何操作。

由 ChatGPT 4.1 翻译