### PROBLEM LINK:

**Author:** Lewin Gan

**Testers:** Kamil Dębowski

**Editorialist:** Lewin Gan

### DIFFICULTY:

Medium-Hard

### PREREQUISITES:

Bitmask DP, Digit DP

### PROBLEM:

Find the number of increasing sequences that are also increasing when XOR-ed 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(N-1)) 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 i-th 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

Tester Solution will be added soon.