102435: [AtCoder]ABC243 F - Lottery
Description
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
Input
题意翻译
一个游戏的抽卡池里有 $n$ 种角色,每种角色的数量无限多,第 $i$ 个角色被抽出的概率是 $\frac{W_i}{\sum_{j=1}^{n}W_j}$,你的钱包只够你氪金抽 $k$ 次,问你最后恰好抽到 $m$ 种不同的角色的概率是多少,答案对 $998244353$ 取模。Output
问题描述
高桥正在参加一个抽奖活动。
每次抽奖,他都会得到$N$种奖品中的一种。奖品$i$的获奖概率为$\frac{W_i}{\sum_{j=1}^{N}W_j}$。抽奖的结果是相互独立的。
从$K$次抽奖中,他恰好得到$M$种不同的奖品的概率是多少?答案对$998244353$取模。
注意
要打印一个有理数,首先要将其表示为分数$\frac{y}{x}$。 这里,$x$和$y$应该是整数,且$x$不能被$998244353$整除(在这个问题的约束下,总是可以做到这一点)。 然后,打印介于$0$和$998244352$(含)之间的唯一整数$z$,满足$xz\equiv y \pmod{998244353}$。
约束条件
- $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}$。
他在两次抽奖中都获得奖品$1$的概率为$\frac{4}{9}$,在两次抽奖中都获得奖品$2$的概率为$\frac{1}{9}$,所以所求概率为$\frac{5}{9}$。
根据注释,这个值对$998244353$取模的表示为$221832079$。
样例输入2
3 3 2 1 1 1
样例输出2
0
从两次抽奖中获得三种不同的奖品是不可能的,所以所求概率为$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