102497: [AtCoder]ABC249 Ex - Dye Color

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $600$ points

Problem Statement

There are $N$ balls numbered $1$ through $N$. Initially, Ball $i$ is painted in Color $A_i$.

Colors are represented by integers between $1$ and $N$, inclusive.

Consider repeating the following operation until all the colors of the balls become the same.

  • There are $2^N$ subsets (including the empty set) of the set consisting of the $N$ balls; choose one of the subsets uniformly at random. Let $X_1,X_2,...,X_K$ be the indices of the chosen balls. Next, choose a permutation obtained by choosing $K$ integers out of integers $(1,2,\dots,N)$ uniformly at random. Let $P=(P_1,P_2,\dots,P_K)$ be the chosen permutation. For each integer $i$ such that $1 \le i \le K$, change the color of Ball $X_i$ to $P_i$.

Find the expected value of number of operations, modulo $998244353$.

Here a permutation obtained by choosing $K$ integers out of integers $(1,2,\dots,N)$ is a sequence of $K$ integers between $1$ and $N$, inclusive, whose elements are pairwise distinct.

Notes

We can prove that the sought expected value is always a rational number. Also, under the Constraints of this problem, when the value is represented by two coprime integers $P$ and $Q$ as $\frac{P}{Q}$, we can prove that there exists a unique integer $R$ such that $R \times Q \equiv P(\bmod\ 998244353)$ and $0 \le R < 998244353$. Find this $R$.

Constraints

  • $2 \le N \le 2000$
  • $1 \le A_i \le N$
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.


Sample Input 1

2
1 2

Sample Output 1

4

The operation is repeated until a subset of size $1$ is chosen and the color of the ball is changed to the color of the ball not contained in the subset. The probability is $\displaystyle \frac{2}{4} \times \frac{1}{2}=\frac{1}{4}$, so the expected value is $4$.


Sample Input 2

3
1 1 1

Sample Output 2

0

The operation is never performed, since the colors of the balls are already the same.


Sample Input 3

10
3 1 4 1 5 9 2 6 5 3

Sample Output 3

900221128

Input

Output

分数:$600$分

问题描述

有编号为$1$到$N$的$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)$为选择的排列。对于满足$1 \le i \le K$的整数$i$,将第$X_i$个球的颜色更改为$P_i$。

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

通过从$(1,2,\dots,N)$中选择$K$个整数得到的排列是一个包含$1$到$N$之间的整数,且元素两两不同的序列。

注意

我们可以证明所求期望值总是有理数。此外,在本问题的约束下,当该值表示为两个互素的整数$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$

输出

输出答案。


样例输入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

加入题单

上一题 下一题 算法标签: