/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
高橋君はくじを引こうとしています。
くじを 1 回引くごとに、N 種類の賞品のいずれかが手に入ります。賞品 i が手に入る確率は \frac{W_i}{\sum_{j=1}^{N}W_j} であり、各くじの結果は独立です。
くじを K 回引いたとき、ちょうど M 種類の賞品が手に入る確率はいくらでしょうか？ \bmod 998244353 で求めてください。
注記
有理数を出力する際は、まずその有理数を分数 \frac{y}{x} として表してください。 ここで、x,y は整数であり、x は 998244353 で割り切れてはなりません（この問題の制約下で、そのような表現は必ず可能です）。 そして、xz\equiv y \pmod{998244353} を満たすような 0 以上 998244352 以下の唯一の整数 z を出力してください。
制約
- 1 \leq K \leq 50
- 1 \leq M \leq N \leq 50
- 0 < W_i
- 0 < W_1 + \ldots + W_N < 998244353
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N M K W_1 \vdots W_N
出力
答えを出力せよ。
入力例 1
2 1 2 2 1
出力例 1
221832079
各くじの結果として、賞品 1 が手に入る確率が \frac{2}{3}、賞品 2 が手に入る確率が \frac{1}{3} です。
2 回のくじの結果として、ともに賞品 1 を手に入れる確率が \frac{4}{9}、ともに賞品 2 を手に入れる確率が \frac{1}{9} であるため、求める答えは \frac{5}{9} です。
これを注記にしたがって \bmod 998244353 で出力すると 221832079 になります。
入力例 2
3 3 2 1 1 1
出力例 2
0
くじを 2 回引いて 3 種類の賞品を手に入れることはできません。したがって求める確率は 0 です。
入力例 3
3 3 10 499122176 499122175 1
出力例 3
335346748
入力例 4
10 8 15 1 1 1 1 1 1 1 1 1 1
出力例 4
755239064
Score : 500 points
Problem Statement
Takahashi is participating in a lottery.
Each time he takes a draw, he gets one of the N prizes available. Prize i is awarded with probability \frac{W_i}{\sum_{j=1}^{N}W_j}. The results of the draws are independent of each other.
What is the probability that he gets exactly M different prizes from K draws? Find it modulo 998244353.
Note
To print a rational number, start by representing it as a fraction \frac{y}{x}. Here, x and y should be integers, and x should not be divisible by 998244353 (under the Constraints of this problem, such a representation is always possible). Then, print the only integer z between 0 and 998244352 (inclusive) such that xz\equiv y \pmod{998244353}.
Constraints
- 1 \leq K \leq 50
- 1 \leq M \leq N \leq 50
- 0 < W_i
- 0 < W_1 + \ldots + W_N < 998244353
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M K W_1 \vdots W_N
Output
Print the answer.
Sample Input 1
2 1 2 2 1
Sample Output 1
221832079
Each draw awards Prize 1 with probability \frac{2}{3} and Prize 2 with probability \frac{1}{3}.
He gets Prize 1 at both of the two draws with probability \frac{4}{9}, and Prize 2 at both draws with probability \frac{1}{9}, so the sought probability is \frac{5}{9}.
The modulo 998244353 representation of this value, according to Note, is 221832079.
Sample Input 2
3 3 2 1 1 1
Sample Output 2
0
It is impossible to get three different prizes from two draws, so the sought probability is 0.
Sample Input 3
3 3 10 499122176 499122175 1
Sample Output 3
335346748
Sample Input 4
10 8 15 1 1 1 1 1 1 1 1 1 1
Sample Output 4
755239064