/ 
実行時間制限: 3 sec / メモリ制限: 1024 MiB
配点 : 550 点
問題文
コワスギ銀行には N 個の金庫があります。金庫 i には A_i 円が入っています。
ある日、強盗がコワスギ銀行に入りました。強盗は盗んだ金額の合計が X 円以上になるまで、以下の操作を繰り返します。
- まだ開けていない金庫の中から一様ランダムに 1 つ選んで開けて、中のお金をすべて盗む。
強盗によって盗まれた金額の合計の期待値を \text{mod }998244353 で求めてください。
期待値 \text{mod }998244353 の定義
求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 \frac{P}{Q} で表した時、Q {{}\not\equiv{}} 0 \pmod{998244353} となることも証明できます。 よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 を満たす整数 R が一意に定まります。 この R を答えてください。
制約
- 1 \le N \le 40
- 1 \le A_i \le 10^{16}
- 1 \le X \le \sum_{i=1}^{N} A_i
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N X A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
2 5 3 10
出力例 1
499122188
はじめに開ける金庫は 2 通りです。
金庫 1 をはじめに開けた場合、続けて金庫 2 も開けるので盗まれた金額の合計は 13 円です。
金庫 2 をはじめに開けた場合、その時点で X 円以上になるので盗まれた金額の合計は 10 円です。
したがって期待値は \frac{13+10}{2}=\frac{23}{2} です。
入力例 2
3 2 1 1 1
出力例 2
2
どの順番で開けても、2 個の金庫を開けた時点で盗まれた金額の合計が 2 円になります。したがって期待値は 2 です。
入力例 3
11 60 2 3 5 7 11 13 17 19 23 29 31
出力例 3
525950964
Score : 550 points
Problem Statement
Kowasugi Bank has N safes. Safe i contains A_i yen.
One day, a robber entered the bank. The robber repeats the following operation until the total amount stolen reaches at least X yen:
- Choose one safe uniformly at random from the safes not yet opened, open it, and steal all the money inside.
Find the expected value, modulo 998244353, of the total amount stolen by the robber.
Definition of expected value modulo 998244353
It can be proved that the expected value sought is always a rational number. Moreover, under the constraints of this problem, it can also be proved that when this value is expressed as an irreducible fraction \frac{P}{Q}, it satisfies Q {{}\not\equiv{}} 0 \pmod{998244353}. Therefore, there exists a unique integer R satisfying R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353. Find this R.
Constraints
- 1 \le N \le 40
- 1 \le A_i \le 10^{16}
- 1 \le X \le \sum_{i=1}^{N} A_i
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N X A_1 A_2 \ldots A_N
Output
Output the answer.
Sample Input 1
2 5 3 10
Sample Output 1
499122188
There are two choices for the first safe to open.
If safe 1 is opened first, the robber also opens safe 2, so the total amount stolen is 13 yen.
If safe 2 is opened first, the total already reaches at least X yen at that point, so the total amount stolen is 10 yen.
Thus, the expected value is \frac{13 + 10}{2} = \frac{23}{2}.
Sample Input 2
3 2 1 1 1
Sample Output 2
2
Regardless of the order in which they are opened, the total amount stolen when two safes have been opened is 2 yen. Thus, the expected value is 2.
Sample Input 3
11 60 2 3 5 7 11 13 17 19 23 29 31
Sample Output 3
525950964