Binary Rhodium

At first, let’s simplify the problem a little bit. If we know the answer $A_R$ for $[1, R]$ range and the answer $A_{L-1}$ for $[1, L-1]$ range, we can calculate the answer for $[L,R]$ range by subtracting $A_{L-1}$ from $A_R$.

Now, let’s simulate the process of building the numbers. Let’s say, currently, the number is $yy01xxx$, where $y$ are the digits we have placed already and $x$ are the digits we need to place. Now, if we can compute the count of the numbers we can build by placing the digits in the positions of $x$, we can easily calculate the contribution of $01$ in this position of the numbers having a structure like this.

To calculate this, we can apply digit Dynamic Programming approach. Definition like this $f(isStart, isSmall, pos, prv)$ is enough to define the DP state while building the numbers. Here, $isStart$ is a flag indicating if the current position is the first position of the number; $isSmall$ indicates if the number we are building is smaller than $R$; $pos$ is the current position we are placing digit and $prv$ is the value we have placed in the previous position. To get the count of numbers and the amount of rhodium from a state together, we may need to manage two DP arrays. An array of pairs also suffices.

Setter’s solution: https://ideone.com/Z5KAJ8