CF2116B.Gellyfish and Baby's Breath

Flower 给了 Gellyfish 两个 $[0, 1, \ldots, n-1]$ 的排列 $p_0, p_1, \ldots, p_{n-1}$ 和 $q_0, q_1, \ldots, q_{n-1}$。

现在 Gellyfish 想通过以下方法计算一个数组 $r_0, r_1, \ldots, r_{n-1}$：

• 对于所有 $i$（$0 \leq i \leq n-1$），有 $r_i = \max\limits_{j=0}^{i} \left(2^{p_j} + 2^{q_{i-j}} \right)$。

但由于 Gellyfish 很懒，你需要帮她计算出数组 $r$ 的所有元素。

由于 $r$ 的元素可能非常大，你只需要输出 $r$ 的每个元素对 $998\,244\,353$ 取模后的结果。

$^{\text{∗}}$ 如果数组 $b$ 由数组 $a$ 的元素任意排列组成，则称 $b$ 是 $a$ 的一个排列。例如，$[4,2,3,4]$ 是 $[3,2,4,4]$ 的一个排列，而 $[1,2,2]$ 不是 $[1,2,3]$ 的排列。

每组测试包含多个测试用例。第一行包含测试用例数 $t$（$1 \leq t \leq 10^4$）。每个测试用例的描述如下：

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）。

第二行包含 $n$ 个整数 $p_0, p_1, \ldots, p_{n-1}$（$0 \leq p_i < n$）。

第三行包含 $n$ 个整数 $q_0, q_1, \ldots, q_{n-1}$（$0 \leq q_i < n$）。

保证 $p$ 和 $q$ 都是 $[0, 1, \ldots, n-1]$ 的排列。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出 $n$ 个整数 $r_0, r_1, \ldots, r_{n-1}$，每个数对 $998\,244\,353$ 取模，输出在一行内。

在第一个测试用例中：

• $r_0 = 2^{p_0} + 2^{q_0} = 1+2=3$
• $r_1 = \max(2^{p_0} + 2^{q_1}, 2^{p_1} + 2^{q_0}) = \max(1+4, 4+2) = 6$
• $r_2 = \max(2^{p_0} + 2^{q_2}, 2^{p_1}+2^{q_1}, 2^{p_2}+2^{q_0}) = (1+1, 4+4, 2+2) = 8$

由 ChatGPT 4.1 翻译