problem.txt (1531B)
1 C. Non-Descending Arrays 2 time limit per test2 seconds 3 memory limit per test256 megabytes 4 You are given two integer arrays a 5 and b 6 both of length n 7 . 8 9 You can choose any subset of indices and swap the elements at those positions (i. e. make a swap(ai 10 , bi 11 ) for each i 12 in the subset). A subset of indices is considered good if, after the swapping, both arrays are sorted in non-descending order. 13 14 Your task is to calculate the number of good subsets. Since the answer can be large, print it modulo 998244353 15 . 16 17 Input 18 The first line contains a single integer t 19 (1≤t≤500 20 ) — the number of test cases. 21 22 The first line of each test case contains a single integer n 23 (1≤n≤100 24 ). 25 26 The second line contains n 27 integers a1,a2,…,an 28 (1≤ai≤1000 29 ). 30 31 The third line contains n 32 integers b1,b2,…,bn 33 (1≤bi≤1000 34 ). 35 36 Additional constraint on the input: there is at least one good subset. 37 38 --- 39 40 - thoughts 41 - a, b both length n 42 - select any subset of indices and swap a_b and b_i 43 - a subset is good if a and b are sorted non-descendingly 44 - return number of good subsets mod 998244353 45 - big nums 46 47 --- 48 49 since big nums, use long, and we know the algo is efficient 50 51 ex1: 52 53 3 54 2 1 4 55 1 3 2 56 57 option1: 58 59 2 3 4 60 61 1 1 2 62 63 option2: 64 65 1 1 2 66 2 3 4 67 68 --- 69 70 1 71 4 72 4 73 74 we can keep same or swap so 2 75 76 --- 77 78 5 79 2 3 3 4 4 80 1 1 3 5 6 81 82 83 84 // idea: 85 // try flipping an element 86 // try not flipping an element 87 // if current is not non-decreasing and flip is also, return 0 88 // propogate this up 89 // return sum