AT_fps_24_q サイコロ

题目描述

有两个骰子，分别称为骰子 $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$，求 $（两者点数之和）^k$ 的期望并对 $998244353$ 取模。

::::info[什么是“模 $998244353$ 下的期望”？] 可以证明这个期望总是一个有理数。在本题所给限制下，如果该数可以表示为 $\frac{P}{Q}$，其中 $P$ 和 $Q$ 互质，则存在唯一整数 $R$，满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \le R < 998244353$。你需要输出这个 $R$。 ::::

输入格式

输入按照如下格式从标准输入给出：

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

输出格式

输出共 $K$ 行。第 $i$ 行输出 $k = i$ 时的答案。

输入输出样例 #1

输入 #1

3 2 3
1 2 3
4 5

输出 #1

499122183
166374102
499122469

输入输出样例 #2

输入 #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

说明/提示

样例解释 1

例如，如果骰子 $1$ 掷出 $3$，骰子 $2$ 掷出 $5$，那么两者和的三次方为 $(3+5)^3 = 512$。

数据范围

• $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$
• 所有输入均为整数。

由 ChatGPT 5 翻译