← 返回题目列表

Codeforces · 2116/B

B. 水母和满天星

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

Flower 为 Gellyfish 提供了 $$$[0, 1, \ldots, n-1]$$$ 的两种排列$$$^{\text{∗}}$$$:$$$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)$$$

但是由于水母很懒,你必须帮助她弄清楚$$$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 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_0, p_1, \ldots,p_{n-1}$$$ ($$$0 \leq p_i \lt n$$$)。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$q_0, q_1, \ldots,q_{n-1}$$$ ($$$0 \leq q_i \lt n$$$)。

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

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

输出

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

示例

输入
复制

3
3
0 2 1
1 2 0
5
0 1 2 3 4
4 3 2 1 0
10
5 8 9 3 4 0 2 7 1 6
9 5 1 4 0 3 2 8 7 6

输出
复制

3 6 8 
17 18 20 24 32 
544 768 1024 544 528 528 516 640 516 768 

注意

在第一个测试用例中:

  • $$$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$$$