P4705 Playing a Game

Warning: Malicious submissions will result in account bans.

Alice and Bob are playing a game again. In one game, first Alice receives a sequence $a$ of length $n$, and Bob receives a sequence $b$ of length $m$. Then they each randomly pick one number from their own sequence, denoted $a_x, b_y$. The $k$-th value of this game is defined as $(a_x + b_y)^k$. Because they find this game too boring, they ask you to compute, for $i = 1, 2, \cdots, t$, the expected $i$-th value of a game. Since the answer can be large, you only need to output the result modulo $998244353$.

The first line contains two integers $n, m(1 \leq n, m \leq 10^5)$, representing the lengths of Alice’s and Bob’s sequences. The next line contains $n$ numbers, where the $i$-th number is $a_i(0 \leq a_i < 998244353)$, representing Alice’s sequence. The next line contains $m$ numbers, where the $j$-th number is $b_j(0 \leq b_j < 998244353)$, representing Bob’s sequence. The next line contains one integer $t(1 \leq t \leq 10^5)$, as described above.

Output $t$ lines, where the $i$-th line is the expected $i$-th value of a single game.

Translated by ChatGPT 5