PROBLEM LINK:Author: Lewin Gan DIFFICULTY:MediumHard PREREQUISITES:Bitmask DP, Digit DP PROBLEM:Find the number of increasing sequences that are also increasing when XORed by another sequence. QUICK EXPLANATION:First, it's helpful to be familiar with digit dp. The state we need to keep is whether or not b_i is strictly less than b_{i+1} and a_i XOR b_i is strictly less than a_{i+1} XOR b_{i+1}. This is a total of 2^(2(N1)) states per digit. EXPLANATION:Using the logic above, we can solve $f(bit, mask1, mask2)$ denoting number of ways given we can fill in the bits 0 to bit. The ith bit in mask1 (resp mask2) is 1 if and only if b_i (resp a_i XOR b_i) is strictly less than b_{i+1} (resp a_{i+1} XOR b_{i+1}). Using this logic, we can brute force over all 2^n ways to fill in the current bit for b, make sure they satisfy the constraints in mask, and recurse to smaller cases. To see more details, see the setter's solution. AUTHOR'S AND TESTER'S SOLUTIONS:
Setter
This question is marked "community wiki".
asked 19 Mar, 22:03

The problem setters code is in Java. Can u add the testers or the editorialists code if it is in c++. answered 20 Mar, 00:24
