Lottery

题目描述

Takahashi 正在参加一个抽奖。 每次抽奖，他会得到 $N$ 个奖品中的一个。奖品 $i$ 被授予的概率为 $\frac{W_i}{\sum_{j=1}^{N}W_j}$。各次抽奖的结果彼此独立。 问在 $K$ 次抽奖中他恰好得到 $M$ 个不同奖品的概率是多少？结果要求对 $998244353$ 取模。

输入格式

输入按下列格式从标准输入给出： $N$ $M$ $K$ $W_1$ $\vdots$ $W_N$

输出格式

输出答案。

2 1 2
2
1

221832079

3 3 2
1
1
1

0

3 3 10
499122176
499122175
1

335346748

10 8 15
1
1
1
1
1
1
1
1
1
1

755239064

提示

$1 \leq K \leq 50$ $1 \leq M \leq N \leq 50$ 0 < W_i 0 < W_1 + \ldots + W_N < 998244353 输入中的所有数值均为整数。要输出一个有理数，首先将其表示为分数 $\frac{y}{x}$。 这里，$x$ 和 $y$ 应该是整数，且 $x$ 不应被 $998244353$ 整除（在本题的约束下，此类表示总是可能的）。 然后，输出唯一的整数 $z$，满足 $0 \le z \le 998244352$ 并且 $xz\equiv y \pmod{998244353}$。每次抽奖中奖品 $1$ 的概率为 $\frac{2}{3}$，奖品 $2$ 的概率为 $\frac{1}{3}$。 两次抽奖中两次都得到奖品 $1$ 的概率为 $\frac{4}{9}$，两次都得到奖品 $2$ 的概率为 $\frac{1}{9}$，因此所求的概率是 $\frac{5}{9}$。 根据说明，该值对 $998244353$ 的表示是 $221832079$。
从两次抽奖中不可能得到三个不同的奖品，因此所求概率为 $0$.

标签: AtCoder|abc243F

来源

AtCoder|abc243F