Public Judge

pjudge

Time Limit: 5 s Memory Limit: 512 MB Total points: 100

#21627. 【PR #3】抽卡

Statistics

你在玩一个抽卡游戏。

这个游戏有 $n+1$ 种级别的抽卡方式,编号为 $0,1,\cdots,n$ 。抽出来的每张卡的等级是 $[0,m]$ 中的一个整数。

一次 0 级抽卡就是只抽一次卡,而一次 $i$ 级抽卡 $(1\le i\le n)$ 会包含 $b_i$ 次 $i-1$ 级抽卡,并且这次 $i$ 级抽卡合法当且仅当它包含的所有 $i-1$ 级抽卡合法,且抽出来的卡中至少有一张的等级大于等于 $i$ 。

对于每次 0 级抽卡,抽出一张等级为 $j$ 的卡的概率是 $\dfrac{a_j}{\sum_{k=0}^m a_k}$ 。

设 $p_j$ 表示在一次合法的 $n$ 级抽卡中抽出等级为 $j$ 的卡的期望次数,$q$ 表示一次 $n$ 级抽卡合法的概率。你需要对于 $0\le j\le m$ 求出 $(p_j\cdot q)\bmod {998244353}$ 。

输入格式

第一行,两个正整数 $m,n$ 。

第二行, $m+1$ 个正整数 $a_0,a_1,\cdots,a_m$ 。

第三行, $n$ 个正整数 $b_1,b_2,\cdots,b_n$ 。

输出格式

输出 $m+1$ 行,第 $j$ 行一个整数 $(p_{j-1}\cdot q)\bmod {998244353}$ 。

样例一

input

2 1
1 1 1
3

output

554580197
1
1

explanation

共有 $27$ 种 $n$ 级抽卡,每种的可能性相等,且其中 $26$ 种是合法的。

$\frac 8 9 = 554580197 \pmod{998244353}$

样例二

input

3 2
1 1 2 1
2 3

output

58137752
260406016
517809313
758026833

样例三

input

7 5
1 2 3 4 5 6 7 8
2 3 4 5 6

output

853156597
693809475
552532484
320522442
504282215
597794834
31931071
464311661

数据范围与提示

本题共 $20$ 组测试点,各 $5$ 分。

对于所有数据,$1\le n\le m\le 4000,1\le a_i\le 4000,2\le b_i\le 4000$ 。保证 $a_i,b_i$ 在范围内均匀随机。

测试点编号 $m\le $ 特殊限制
$1\sim 3$ $3$ $\prod_{i=1}^n b_i\le 12$
$4\sim 6$ $10$ $b_i\le 3$
$7\sim 10$ $50$ $a_i\le 10$
$11\sim 15$ $400$
$16\sim 20$ $ $

时间限制:$\texttt{5s}$

空间限制:$\texttt{512MB}$