【题目描述】
你在玩「水月与深蓝之树」。
你发现某干员的伤害不够高,而游戏内两类加伤害的收藏品。
第一类收藏品有 $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.in
与 national/national2.ans
。
【样例 3】
见选手目录下的 national/national3.in
与 national/national3.ans
。
【子任务】
对于全部数据,$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$ |