codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$