Score : $600$ points
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.
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.
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$.
Input is given from Standard Input in the following format:
$N$ $A_1$ $A_2$ $\dots$ $A_N$
Print the answer.
2 1 2
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$.
3 1 1 1
0
The operation is never performed, since the colors of the balls are already the same.
10 3 1 4 1 5 9 2 6 5 3
900221128