Link to the problem : https://atcoder.jp/contests/abc138/tasks/abc138_f
Problem Statement : Given are integers L and R . Find the number, modulo 10^9 + 7 , of pairs of integers ( x , y ) , ( L ≤ x ≤ y ≤ R ) such that the remainder when y is divided by x is equal to y XOR x .
1<=L<=R<=10^18
Basically, the crux of the problem is to find all the pairs (x,y) such that y>=x, MSB of "y" and "x" should be same , and wherever(position) the bits of "x" are set(1), at those positions, bits of "y" must also be set.
In the editorial,they solved this task using dp. (but gave close to no explanation what is done in the dp and its states)
Link(s) : 1)https://img.atcoder.jp/abc138/editorial.pdf
2)https://codeforces.me/blog/entry/69181?#comment-536085
But , nowhere is it mentioned what are the states of the dp ?
(dp[i][j][k][l] is used , but whats the meaning of "i" , "j" , "k" and "l" here ?)
Can somebody make the dp-states and transitions explanation simple and to the point ?
$$${i}$$$ -> denotes the bit you currently are at, $$${j}$$$ -> ensures that x>=l , $$${k}$$$ -> ensures that y <=r , $$${l}$$$ -> ensures that x and y have 1 in their MSB. This is how it works — $$${j,k,l}$$$ are initially 0 which means that starting from bit 59 till i+1 there is no point at which either we have made x>l or y<r or both x and y have been given 1 at any bit belonging to $$${[i+1,59]}$$$. Now we can only have three conditions as stated in the editorial. Let's see how the first transition is happening — For $$${x=0}$$$ and $$${y=0}$$$ we can have $$${x=0}$$$ only if either $$${l}$$$ has $$${0}$$$ at this bit or we already have a bit before for which we have made $$${x>l}$$$ that is we placed a 1 where $$${l}$$$ had 0, which means $$${j}$$$ is 1. For $$${y=0}$$$ we don't need to check any condition on $$${k}$$$ as $$${y=0}$$$ we are ensuring $$${y<=r}$$$. Also we need to update the value of $$${j,k,l}$$$ in every transition.