当前没有测试数据。

染色问题

分数：$600$ 分

题目描述

有 $N$ 个编号为 $1$ 到 $N$ 的小球。最初，小球 $i$ 被染成颜色 $A_i$。

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

考虑重复以下操作，直到所有小球的颜色相同为止。

• 从大小为 $N$ 的小球集合中选择 $2^N$ 个子集（包括空集），均匀随机选择一个子集。选择的小球的索引为 $X_1,X_2,...,X_K$。接下来，从 $(1,2,\dots,N)$ 中均匀随机选择 $K$ 个整数得到一个置换。$P=(P_1,P_2,\dots,P_K)$ 是所选择的置换。对于每个整数 $i$ 满足 $1 \le i \le K$，将小球 $X_i$ 的颜色更改为 $P_i$。

求操作次数的期望值，取模 $998244353$。

这里的由从 $(1,2,\dots,N)$ 中选择 $K$ 个整数得到的置换，是在 $1$ 到 $N$ 之间的整数中选取 $K$ 个不同的整数，包括在内，其元素两两不相同的长度为 $K$ 的序列。

注意事项

我们可以证明所求的期望值始终是一个有理数。此外，在问题的约束条件下，当这个值用两个互质的整数 $P$ 和 $Q$ 表示为 $\frac{P}{Q}$ 时，我们可以证明存在一个唯一的整数 $R$，满足 $R \times Q \equiv P(\bmod\ 998244353)$ 且 $0 \le R < 998244353$。找到这个 $R$。

约束条件

• $2 \le N \le 2000$
• $1 \le A_i \le N$
• 输入中的所有值都是整数。

输入

输入使用以下格式从标准输入给出：

$N$

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

输出

打印答案。

2
1 2

4

重复操作直到选择一个大小为 $1$ 的子集，然后将小球的颜色更改为不在该子集中的小球的颜色。概率为 $\displaystyle \frac{2}{4} \times \frac{1}{2}=\frac{1}{4}$，因此期望值为 $4$。

3
1 1 1

0

由于小球的颜色已经相同，所以不执行操作。

10
3 1 4 1 5 9 2 6 5 3

900221128