AT_abc243_f.[ABC243F] Lottery

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

高桥君打算抽奖。

每抽一次奖，就会获得 $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
```
输出#1
```
221832079
```
输入#2
```
3 3 2
1
1
1
```
输出#2
```
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
```

说明/提示

注记

输出有理数时，首先将其表示为分数 $\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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页