← 返回题目列表

AtCoder · fps_24_q

Q. 骰子

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

分数: 5 点

问题陈述

有两个骰子,称为骰子 1 然后死去 2.

  • 模具 1 是一个 N双面骰子,每面显示一个不同的正整数 A_1, A_2, \dots, A_N 具有相同的概率。
  • 模具 2 是一个 M双面骰子,每面显示一个不同的正整数 B_1, B_2, \dots, B_M 具有相同的概率。

还给你一个正整数 K.
对于每个 k = 1, 2, \dots, K,解决以下问题:

  • 滚压模具时 1 然后死去 2 同时,计算期望值 (\text{sum of the outcomes})^k 模数 998244353.
期望值模是什么 998244353 是什么意思? 可以证明期望值始终是有理数。 在该问题的约束下,如果该值可以表示为 \tfrac{P}{Q} 与互质整数 P 和 Q, 那么存在一个唯一的整数 R 这样 R \times Q \equiv P \pmod{998244353} 和 0 \leq R < 998244353。 你被要求计算这个 R.

约束

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq K \leq 10^5
  • 1 \leq A_1 < A_2 < \dots < A_N \leq 10^8
  • 1 \leq B_1 < B_2 < \dots < B_M \leq 10^8
  • 所有输入值均为整数

输入

输入由标准输入给出,格式如下:

N M K
A_1 A_2 \dots A_N
B_1 B_2 \dots B_M

输出

打印 K 行。上 i第行,输出答案 k = i.


示例输入 1

3 2 3
1 2 3
4 5

示例输出 1

499122183
166374102
499122469

例如,如果死了 1 显示 3 然后死去 2 显示 5,则总和的立方为 (3+5)^3 = 512.


示例输入 2

8 9 5
26056440 37770730 49119845 54471601 59187620 86450214 95205990 97771081
12521133 14054302 19786177 21524935 39265456 53591023 65158870 86176948 87221915

示例输出 2

981084750
45312313
562611236
522662310
196292405