main.cpp (2111B)
1 #include <vector> 2 #include <iostream> 3 #include <unordered_map> 4 5 // idea: 6 // try flipping an element 7 // try not flipping an element 8 // if current is not non-decreasing and flip is also, return 0 9 // propogate this up 10 // return sum 11 12 long long subsets(std::vector<int>& a, std::vector<int>& b, int idx, std::unordered_map<int,long long>& memo) { 13 14 if(memo.contains(idx)) { 15 return memo[idx]; 16 } 17 18 if(idx >= b.size()) { 19 // for(int i = 0; i < a.size(); ++i) { 20 // std::cout << a[i] << " "; 21 // } 22 // std::cout << std::endl; 23 // for(int i = 0; i < a.size(); ++i) { 24 // std::cout << b[i] << " "; 25 // } 26 // std::cout << std::endl; 27 28 29 memo[idx] = 1; 30 return 1; // this means we safely went to the end and know of an ordering 31 } 32 33 bool isFineNoSwap = true; 34 if(idx != 0) { 35 isFineNoSwap = a[idx] >= a[idx-1] && b[idx] >= b[idx-1]; 36 } 37 38 bool isFineSwap = true; 39 if(idx != 0) { 40 isFineSwap = a[idx] >= b[idx-1] && b[idx] >= a[idx-1]; 41 } 42 43 if(!isFineNoSwap && !isFineSwap) { 44 memo[idx] = 0; 45 return 0; 46 } 47 48 long long sm = 0; 49 50 // since this is symmetric, we notice there's either one correct option or both are correct, regardless of if we swapped at the prior step 51 52 if(isFineNoSwap) { 53 sm += subsets(a,b,idx+1, memo); 54 } 55 if(isFineSwap) { 56 sm += subsets(a,b,idx+1, memo); 57 } 58 59 60 memo[idx] = sm % 998244353; 61 return sm % 998244353; 62 } 63 64 int main() { 65 int current, lsSize, testCaseCount; 66 std::cin >> testCaseCount; 67 for(int z = 0; z < testCaseCount; ++z) { 68 std::cin >> lsSize; 69 std::vector<int> a {}; 70 std::vector<int> b {}; 71 for(int x = 0; x < lsSize; ++x) { 72 std::cin >> current; 73 a.push_back(current); 74 } 75 for(int x = 0; x < lsSize; ++x) { 76 std::cin >> current; 77 b.push_back(current); 78 } 79 std::unordered_map<int, long long> mp {}; 80 std::cout << subsets(a,b,0,mp) << std::endl; 81 } 82 }