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 {}.