2116B.md (2164B)
1 Source: https://codeforces.com/problemset/problem/2116/B 2 3 B. Gellyfish and Baby's Breath 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Flower gives Gellyfish two permutations$^{\text{∗}}$ of $[0, 1, \ldots, n-1]$: $p_0, p_1, \ldots, p_{n-1}$ and $q_0, q_1, \ldots, q_{n-1}$. 22 23 Now Gellyfish wants to calculate an array $r_0,r_1,\ldots,r_{n-1}$ through the following method: 24 25 * For all $i$ ($0 \leq i \leq n-1$), $r_i = \max\limits_{j=0}^{i} \left(2^{p_j} + 2^{q_{i-j}} \right)$ 26 27 But since Gellyfish is very lazy, you have to help her figure out the elements of $r$. 28 29 Since the elements of $r$ are very large, you are only required to output the elements of $r$ modulo $998\,244\,353$. 30 31 $^{\text{∗}}$An array $b$ is a permutation of an array $a$ if $b$ consists of the elements of $a$ in arbitrary order. For example, $[4,2,3,4]$ is a permutation of $[3,2,4,4]$ while $[1,2,2]$ is not a permutation of $[1,2,3]$. 32 33 Input 34 35 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 36 37 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 10^5$). 38 39 The second line of each test case contains $n$ integers $p_0, p_1, \ldots,p_{n-1}$ ($0 \leq p_i \lt n$). 40 41 The third line of each test case contains $n$ integers $q_0, q_1, \ldots,q_{n-1}$ ($0 \leq q_i \lt n$). 42 43 It is guaranteed that both $p$ and $q$ are permutations of $[0, 1, \ldots, n-1]$. 44 45 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 46 47 Output 48 49 For each test case, output $n$ integers $r_0, r_1, \ldots, r_{n-1}$ in a single line, modulo $998\,244\,353$. 50 51 Example 52 53 Input 54 55 ``` 56 3 57 58 3 59 60 0 2 1 61 62 1 2 0 63 64 5 65 66 0 1 2 3 4 67 68 4 3 2 1 0 69 70 10 71 72 5 8 9 3 4 0 2 7 1 6 73 74 9 5 1 4 0 3 2 8 7 6 75 ``` 76 77 Output 78 79 ``` 80 3 6 8 81 17 18 20 24 32 82 544 768 1024 544 528 528 516 640 516 768 83 ``` 84 85 Note 86 87 In the first test case: 88 89 * $r_0 = 2^{p_0} + 2^{q_0} = 1+2=3$ 90 * $r_1 = \max(2^{p_0} + 2^{q_1}, 2^{p_1} + 2^{q_0}) = \max(1+4, 4+2) = 6$ 91 * $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$