AT_abc243_f [ABC243F] Lottery

题目描述

高桥君打算抽奖。

每抽一次奖，就会获得 $N$ 种奖品中的某一种。获得第 $i$ 种奖品的概率为 $\frac{W_i}{\sum_{j=1}^{N}W_j}$，且每次抽奖的结果相互独立。

当抽奖 $K$ 次时，恰好获得 $M$ 种不同奖品的概率是多少？请将答案对 $998244353$ 取模后输出。

输入格式

输入从标准输入中按以下格式给出。

$N$ $M$ $K$
$W_1$
$W_2$
$\vdots$
$W_N$

输出格式

请输出答案。

样例 1

输入

2 1 2
2
1

输出

221832079

样例 2

输入

3 3 2
1
1
1

输出

0

样例 3

输入

3 3 10
499122176
499122175
1

输出

335346748

样例 4

输入

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

输出

755239064

说明/提示

注记

输出有理数时，首先将其表示为分数 $\frac{y}{x}$，其中 $x, y$ 均为整数，且 $x$ 不能被 $998244353$ 整除（在本题的约束下，总能做到）。然后，输出唯一满足 $0 \leq z \leq 998244352$ 且 $xz \equiv y \pmod{998244353}$ 的整数 $z$。

约束条件

• $1 \leq K \leq 50$
• $1 \leq M \leq N \leq 50$
• $0 < W_i$
• $0 < W_1 + \ldots + W_N < 998244353$
• 所有输入均为整数

样例解释 1

每次抽奖获得奖品 $1$ 的概率为 $\frac{2}{3}$，获得奖品 $2$ 的概率为 $\frac{1}{3}$。两次抽奖都获得奖品 $1$ 的概率为 $\frac{4}{9}$，都获得奖品 $2$ 的概率为 $\frac{1}{9}$，因此答案为 $\frac{5}{9}$。按照注记的要求对 $998244353$ 取模后输出 $221832079$。

样例解释 2

抽奖 $2$ 次无法获得 $3$ 种不同的奖品，因此概率为 $0$。

由 ChatGPT 4.1 翻译