← 返回题目列表

AtCoder · abc249_h

Ex. 染料颜色

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

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