codeforces-scrape

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

2144C.md (1551B)


      1 Source: https://codeforces.com/problemset/problem/2144/C
      2 
      3 C. Non-Descending Arrays
      4 
      5 time limit per test
      6 
      7 2 seconds
      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 You are given two integer arrays $a$ and $b$ both of length $n$.
     22 
     23 You can choose any subset of indices and swap the elements at those positions (i. e. make a swap($a_i$, $b_i$) for each $i$ in the subset). A subset of indices is considered good if, after the swapping, both arrays are sorted in non-descending order.
     24 
     25 Your task is to calculate the number of good subsets. Since the answer can be large, print it modulo $998244353$.
     26 
     27 Input
     28 
     29 The first line contains a single integer $t$ ($1 \le t \le 500$) — the number of test cases.
     30 
     31 The first line of each test case contains a single integer $n$ ($1 \le n \le 100$).
     32 
     33 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 1000$).
     34 
     35 The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 1000$).
     36 
     37 Additional constraint on the input: there is at least one good subset.
     38 
     39 Output
     40 
     41 For each test case, print a single integer — the number of good subsets, taken modulo $998244353$.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 3
     49 
     50 3
     51 
     52 2 1 4
     53 
     54 1 3 2
     55 
     56 1
     57 
     58 4
     59 
     60 4
     61 
     62 5
     63 
     64 2 3 3 4 4
     65 
     66 1 1 3 5 6
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 2
     73 
     74 2
     75 
     76 8
     77 ```
     78 
     79 Note
     80 
     81 In the first example, there are $2$ good subsets: {1, 3} and {2}.
     82 
     83 In the second example, there are $2$ good subsets: {1} and {}.
     84 
     85 In the third example, there are $8$ good subsets: {1, 2, 3, 4, 5}, {1, 2, 3}, {1, 2, 4, 5}, {1, 2}, {3, 4, 5}, {3}, {4, 5} and {}.