Forget, it is present on registration page on arena.

Problems were good but not many participants even though SRMs at this time slot used to be most popular

a + b = (a|b) + (a&b)

Now that you have pairOr and pairAnd, note that you can check solution for each bit individually as they are independent. Now, do a dp[n][2] for each bit where dp[i][j] is whether there exists a prefix of length i ending at j. Check if dp[n][0] or dp[n][1] is true for each bit.

But why (a&b) + (a|b) = a + b ?

First, one observation is that it is enough to do at most one of the moves {"left", "right"}, and at most one of the moves {"up", "down"}. There is no point to do both of the moves in one of the sets, so any reachable board would be reachable in at most two steps.

Let's say "left" is true if there exists a block that has a free cell on its left and false otherwise. (similarly, define "right', "up", and "down"). Intuitively, these are the moves which we shouldn't use, since we can't use these and get to our final configuration.

Then, we have the following cases:

1) If all of left, right, down, and up are true, then the answer is 1 (i.e. no moves are possible).

2) Let's say that both left/right are true (similarly for up/down). Then, we can't ever do left/right moves, so we can treat each column independently. Since one of up/down must be false (otherwise, we would be in case 1), then, we can just place the blocks anywhere in the column, as long as the number of such blocks matches. The number of ways to do this is just the binomial coefficient (n choose number of blocks in column). We take the product over all columns.

3) Now, without loss of generality, let's say left is false and up is false. Then, that means all blocks are in the upleft corner. For example, it may look like a shape like this:

####.
###..
###..
##...
.....

There are two options: We either can do the moves "left" then "up" to get the blocks in the correct place, or we can do the moves "up" then "left".

For, "left", then "up", we can arrange the rows in an arbitrary order, then arrange the blocks within each row independently. The number of ways to arrange the rows is the multinomial coefficent (n choose a_0, a_1, ..., a_m), where a_i is the number of rows with exactly i blocks. The number of ways to arrange blocks within each row can be computed similarly to case (2).

Similary, we can do the same thing for "up" then "left" (using columns instead of rows).

However, we double counted the boards that can be solved with both types of moves. Luckily, that is just the number of ways to rearrange rows multiplied by the ways to rearrange columns. We can also use multinomial coefficients here in this case.