分数: 600 点
问题陈述
有 N 球编号 1 通过 N。 最初,鲍尔 i 涂有颜色 A_i.
颜色由之间的整数表示 1 和 N,包括在内。
考虑重复以下操作,直到所有球的颜色变得相同。
- 有 2^N 组成的集合的子集(包括空集) N 球;均匀地随机选择子集之一。 让 X_1,X_2,...,X_K 是所选球的索引。 接下来,选择通过选择获得的排列 K 整数中的整数 (1,2,\dots,N) 均匀随机。 让 P=(P_1,P_2,\dots,P_K) 是所选的排列。 对于每个整数 i 这样 1 \le i \le K,改变球的颜色 X_i to P_i.
求运算次数的期望值,取模 998244353.
这里通过选择获得的排列 K 整数中的整数 (1,2,\dots,N) 是一系列 K 之间的整数 1 和 N,包含在内,其元素成对不同。
注释
我们可以证明所求的期望值始终是有理数。 另外,在该问题的约束下,当该值由两个互质整数表示时 P 和 Q as \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
输出
打印答案。
示例输入 1
2 1 2
示例输出 1
4
重复该操作,直到大小的子集 选择 1 并将球的颜色更改为不包含在子集中的球的颜色。 概率是 \displaystyle \frac{2}{4} \times \frac{1}{2}=\frac{1}{4},所以期望值为 4.
示例输入 2
3 1 1 1
示例输出 2
0
永远不会执行该操作,因为球的颜色已经相同。
示例输入 3
10 3 1 4 1 5 9 2 6 5 3
示例输出 3
900221128