 # INCXOR - Editorial

Author: Lewin Gan
Testers: Kamil Dębowski
Editorialist: Lewin Gan

Medium-Hard

### 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.

2 Likes

Hi, Could someone please explain this line

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

in a little more detail.

Thanks a lot for the editorial! The problem setters code is in Java. Can u add the testers or the editorialists code if it is in c++.

2 Likes

I am getting the following error. When i am trying to view setter solution.
This XML file does not appear to have any style information associated with it. The document tree is shown below.

`AccessDenied`