/ 
Time Limit: 3.5 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 個のボールがあり、ボールには 1 から N の番号がついています。初め、ボール i は色 A_i で塗られています。
色は 1 以上 N 以下の整数によって表されます。
以下の操作を、全てのボールの色が等しくなるまで繰り返します。
- N 個のボールからなる集合の部分集合(空集合を含む)は 2^N 個あるが、そこから 1 個の集合を一様ランダムに選ぶ。選んだ集合に含まれるボールの index を昇順に X_1,X_2,...,X_K とする。次に、(1,2,\dots,N) から K 個を選んで得られる順列を一様ランダムに 1 個選び P=(P_1,P_2,\dots,P_K) とする。そして、1 \le i \le K を満たす整数 i に対し、ボール X_i の色を P_i に変更する。
操作回数の期待値 \bmod\ 998244353 を求めてください。
ここで、(1,2,\dots,N) から K 個を選んで得られる順列とは、1 以上 N 以下の整数 K 個からなる数列であって、要素が相異なるもののことです。
注記
求める期待値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な 2 つの整数 P,Q を用いて \frac{P}{Q} と表した時、R \times Q \equiv P(\bmod\ 998244353) かつ 0 \le R < 998244353 を満たす整数 R がただ一つ存在することが証明できます。この 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
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