G - Socks 3 Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 600 点

問題文

高橋君のタンスの中には様々な色の靴下が入っています。 靴下の色は 1 以上 N 以下の整数として表され、色 i の靴下は A_i\ (\geq 2) 枚入っています。

高橋君は、以下の操作を行うことで今日履く靴下を選ぼうとしています。

  • 今までに取り出した靴下の中で同じ色の靴下の 2 枚組が作れるようになるまで、タンスの中からランダムに等確率で 1 枚の靴下を取り出すことを繰り返す。 なお、一度取り出した靴下はタンスの中には戻さない。

高橋君がタンスから靴下を取り出す回数の期待値を \text{mod } 998244353 で求めてください。

期待値を \text{mod } 998244353 で求めるとは 求める期待値は必ず有理数になることが証明できます。 また、この問題の制約下では、期待値を既約分数 \frac{y}{x} で表したときに x が 998244353 で割り切れないことが保証されます。 このとき xz \equiv y \pmod{998244353} を満たすような 0 以上 998244352 以下の整数 z が一意に定まるので、この z を求めてください。

制約

  • 1\leq N \leq 3\times 10^5
  • 2\leq A_i \leq 3000
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

2
2 2

出力例 1

665496238

例えば、以下のように操作を行うことが考えられます。

  1. タンスの中から色 1 の靴下を 1 枚取り出す。タンスの中には色 1 の靴下が 1 枚と色 2 の靴下が 2 枚残っている。
  2. タンスの中から色 2 の靴下を 1 枚取り出す。タンスの中には色 1,2 の靴下が 1 枚ずつ残っている。
  3. タンスの中から色 1 の靴下を 1 枚取り出す。今までに取り出した靴下は色 1 の靴下が 2 枚と色 2 の靴下が 1 枚であり、この中で色 1 の靴下の 2 枚組が作れるので操作を終了する。

この例の場合、高橋君がタンスから靴下を取り出す回数は 3 回です。

高橋君がタンスから靴下を取り出す回数は \frac{2}{3} の確率で 3 回、\frac{1}{3} の確率で 2 回なので、求める期待値は 3\times \frac{2}{3} + 2\times \frac{1}{3} = \frac{8}{3} \equiv 665496238 \pmod {998244353} です。

入力例 2

1
352

出力例 2

2

入力例 3

6
1796 905 2768 253 2713 1448

出力例 3

887165507

Score: 600 points

Problem Statement

Takahashi has various colors of socks in his chest of drawers. The colors of the socks are represented by integers from 1 to N, and there are A_i\ (\geq 2) socks of color i.

He is about to choose which socks to wear today by performing the following operation:

  • Continue to randomly draw one sock at a time from the chest, with equal probability, until he can make a pair of socks of the same color from those he has already drawn. Once a sock is drawn, it will not be returned to the chest.

Find the expected value, modulo 998244353, of the number of times he has to draw a sock from the chest.

What does it mean to find the expected value modulo 998244353? It can be proved that the sought expected value is always rational. Furthermore, the constraints of this problem guarantee that if the expected value is expressed as an irreducible fraction \frac{y}{x}, then x is not divisible by 998244353. Here, there exists a unique integer z between 0 and 998244352, inclusive, such that xz \equiv y \pmod{998244353}. Find this z.

Constraints

  • 1\leq N \leq 3\times 10^5
  • 2\leq A_i \leq 3000
  • All input values are integers.

Input

The 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
2 2

Sample Output 1

665496238

For example, the operation could be performed as follows:

  1. Draw a sock of color 1 from the chest. There remains one sock of color 1 and two socks of color 2 in the chest.
  2. Draw a sock of color 2 from the chest. There remains one sock each of colors 1 and 2 in the chest.
  3. Draw a sock of color 1 from the chest. The socks drawn so far are two of color 1 and one of color 2, allowing a pair of color 1 socks to be made, thus ending the operation.

In this example, Takahashi draws a sock from the chest three times.

The expected number of times Takahashi draws a sock from the chest is 3 with probability \frac{2}{3} and 2 with probability \frac{1}{3}, so the expected value is 3\times \frac{2}{3} + 2\times \frac{1}{3} = \frac{8}{3} \equiv 665496238 \pmod {998244353}.

Sample Input 2

1
352

Sample Output 2

2

Sample Input 3

6
1796 905 2768 253 2713 1448

Sample Output 3

887165507