← 返回题目列表

AtCoder · abc243_f

I. 彩票

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

高桥正在参加抽奖。

每次他抽牌,他都会获得以下之一 N 奖品可用。奖品 i 被授予概率 \frac{W_i}{\sum_{j=1}^{N}W_j}。抽签结果是相互独立的。

他得到的概率是多少 M 不同的奖品 K 抽奖?求模 998244353.

注意

要打印有理数,首先将其表示为分数 \frac{y}{x}。 在这里, x 和 y 应该是整数,并且 x 不应被整除 998244353 (在这个问题的约束下,这样的表示总是可能的)。 然后,打印唯一的整数 z 之间 0 和 998244352 (含)使得 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