Logo Universal Online Judge

UOJ

时间限制:2 s 空间限制:512 MB
Statistics

【题目描述】

你在玩「水月与深蓝之树」。

你发现某干员的伤害不够高,而游戏内两类加伤害的收藏品。

第一类收藏品有 $n$ 个,拿到第 i 时会将该干员的伤害增加 $a_i$。

第二类收藏品有 $m$ 个,拿到第 i 时会将该干员的伤害乘以 $c_i$。

收藏品会根据拿到的顺序依次生效,你不会拿到重复的收藏品。

例如原本该干员的伤害为 $x$,然后依次拿了 $a_1, c_1, a_2, c_2$ 四个收藏品,那么最后该干员的伤害为 $(((x + a1)c1) + a2)c2$。

你想知道对于每一个 $k = 0, \cdots, n + m$,一共拿了 $k$ 个收藏品的情况下,若一开始该干员的伤害为 $1$,那么游戏结束时该干员的伤害的期望对 $998244353$ 取模的值。

【输入格式】

从标准输入读入数据。

输入数据第一行包含两个整数 $n$,$m$。

第二行包含 $n$ 个整数,表示第 $i$ 个整数表示 $a_i$。

第二行包含 $m$ 个整数,表示第 $i$ 个整数表示 $c_i$。

【输出格式】

输出到标准输出。

输出一行 $n + m + 1$ 个整数,第 $i$ 个整数表示若游戏结束时拿了 $i − 1$ 个收藏品,该 干员的伤害的期望。

【样例 $1$ 输入】

2 1
1 2
3

【样例 $1$ 输出】

1 665496238 332748123 9

【样例 1 解释】

对于 $k = 2$,一共有 $6$ 种情况,每种情况出现概率相同:$1+1+2 = 4$,$(1+1)×3 = 6$,$1 + 2 + 1 = 4$,$(1 + 2) × 3 = 9$,$1 × 3 + 1 = 4$,$1 × 3 + 2 = 5$。故期望值为 $\frac{16}{3}$ 。

【样例 2】

见选手目录下的 national/national2.innational/national2.ans

【样例 3】

见选手目录下的 national/national3.innational/national3.ans

link

【子任务】

对于全部数据,$1 ≤ n, m ≤ 10^5$,$0 ≤ k ≤ n + m$,$0 ≤ ai , ci < 998244353$。

测试点编号 $n$ $m$
$1 \sim 4$ $\leq 2 \times 10^3$ $\leq 2 \times 10^3$
$5,6$ $=0$ $\leq 10^5$
$7,8$ $\leq 10^5$ $=0$
$9 \sim 20$ $\leq 10^5$ $\leq 10^5$