PROBLEM LINK:
Author: Alexey Zayakin
Tester: Pushkar Mishra
Editorialist: Florin Chirica
PROBLEM
Let’s define a matrix with lines from L to R and columns from L to R. An element (i, j) has value equal to i xor j. Let’s define a walk by cells which have consecutive values and share a side. What’s the maximum length of a walk and how many maximum length walks are there?
CREDITS
Thanks to Alexey Zayakin for contributing in problem explanation.
EXPLANATION
Brute force
Since the limits are so big, it’s quite natural to start seeking patterns. For this, let’s write a brute force (solving the first subtask) which will allow us to see patterns. Let ways[i][j] = in how many ways can I reach cell (i, j) and x[i][j] = value from the cell (i, j).
Then, let (i’, j’) a cell which shares a side with (i, j). We get ways[i][j] += ways[i’][j’], if x[i’][j’] + 1 = x[i][j].
Now let’s run the brute force in order to start finding patterns.
Answer is a power of 2 minus 1
The maximal length is always of the form 2^k - 1. Let’s prove it.
If we have a walk of length at least 2^k, then there exist two adjacent cells with numbers 2^k - 1 and 2^k. There are two cases:
Case 1 These cells are (x, y) and (x + 1, y).
x xor y = 2^k - 1
(x + 1) xor y = 2^k
x xor (x + 1) = 2^{k+1} - 1
One can see that x = A * 2^{k+1} + 2^k - 1
and we can conclude that y = A * 2^{k+1}
We get some necessarily conditions by saying that both cells (x, y) and (x + 1, y) must belong to the matrix.
L \le x
x + 1 \le R
L \le y \le R
It’s enough to check that L \le y and x < R.
L \le A * 2^{k+1} \le R - 2^k
L \le R - 2^k - ( (R - 2^k) mod 2^{k+1} )
(I) R - L - 2^k >= (R - 2^k) mod 2^{k+1}
Case 2 These cells are (x, y) and (x - 1, y)
x xor y = 2^k - 1
(x - 1) xor y = 2^k
x xor (x - 1) = 2^{k + 1} - 1
One can see that x = A * 2^{k + 1} + 2^k
y = A * 2^{k+1} + 2^{k+1} - 1
Using the logic from the above we get that
(II) R - L - 2^k \ge (R + 1) mod 2^{k+1}
Let’s find maximum k that respects one of the inequalities. Then, the maximum walk length is equal to 2^{k+1} - 1.
Finding the number of paths of maximum length
Here is the place where we use brute force. Let’s run brute force for some small tests. Let’s mark a cell (i,j) with 1 if it’s reachable (there exists at least one path ending there) and it has maximum value obtained last step and 0 otherwise. We need, for each value of 1, to add ways[i][j] to the solution.
Let’s print all ways[i][j] values. It’s easy to notice all are equal and more - their value is \frac{K + 1}{2}. So, the answer is simply number of ones * \frac{K + 1}{2}. Let’s focus on calculating number of ones from brute force construction.
Those ones are placed on at most two diagonals. Diagonals are perpendicular by main diagonal. More, each diagonal has one element on line 1, respectively column 1, and on line n, respectively column n.