分数: 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