/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 525 点
問題文
高橋君のタンスの中には N 色の靴下があり、色 i の靴下は A_i 枚あります。
高橋君ははじめこれらの靴下とは別に色 C の靴下を 1 枚タンスの外に持っており、操作を終える条件を満たすまで以下の操作を繰り返します。
- タンスから靴下を 1 枚一様ランダムに選んで取り出す。その後、タンスの外に持っている 2 枚の靴下が同じ色ならば操作を終える。そうでないならば、片方の靴下を選んでタンスに戻す。ただし、高橋君は常に今後の靴下を取り出す回数の期待値が最小となるようにタンスに戻す靴下を選ぶ。
操作を終えるまでに靴下を取り出す回数の期待値を \bmod\ 998244353 で求めてください。
期待値を \bmod\ 998244353 で求めるとは
この問題の制約のもとで、期待値は存在し、有理数になることが証明できます。 また、その値を既約分数 \frac{P}{Q} (Q > 0) で表したとき、Q \not\equiv 0 \pmod{998244353} となることも証明できます。 よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 を満たす整数 R が一意に定まります。 期待値を \bmod\ 998244353 で求めるとは、この R の値を求めることを指します。
制約
- 1 \leq N \leq 3 \times 10^5
- 1 \leq C \leq N
- 1 \leq A_i \leq 3000
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N C A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
3 2 3 1 2
出力例 1
249561092
靴下を取り出す回数の期待値は \frac{15}{4} となります。
入力例 2
8 4 4 1 6 2 5 1 7 3
出力例 2
393623786
Score : 525 points
Problem Statement
In Takahashi's chest of drawers, there are socks of N colors, with A_i socks of color i.
Initially, Takahashi has one sock of color C outside the chest of drawers, separate from these socks, and repeats the following operation until the termination condition is met:
- Uniformly randomly choose and draw 1 sock from the chest of drawers. Then, if the two socks he has outside the chest of drawers are the same color, terminate the operation. Otherwise, choose one of the socks and put it back in the chest of drawers. He always chooses the sock to put back so as to minimize the expected number of future sock draws.
Find the expected number, modulo 998244353, of sock draws until the operation terminates.
Finding the expected value modulo 998244353
Under the constraints of this problem, it can be proved that the expected value exists and is a rational number. It can also be proved that when this value is expressed as an irreducible fraction \frac{P}{Q} (Q > 0), we have Q \not\equiv 0 \pmod{998244353}. Therefore, there uniquely exists an integer R satisfying R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353. Finding the expected value modulo 998244353 means finding this value of R.
Constraints
- 1 \leq N \leq 3 \times 10^5
- 1 \leq C \leq N
- 1 \leq A_i \leq 3000
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N C A_1 A_2 \ldots A_N
Output
Output the answer.
Sample Input 1
3 2 3 1 2
Sample Output 1
249561092
The expected number of sock draws is \frac{15}{4}.
Sample Input 2
8 4 4 1 6 2 5 1 7 3
Sample Output 2
393623786