Today I have been wondering about a problem. Calculate the range xor of all the numbers between l and r which doesnt contain the letter 5.
Now the sum or count of all 5 letter less elements can be fairly easily solved using digit dp in their decimal form. Range xor on the other hand would require us to represent the number in binary form and essentially breaks down the information of whether the number had a letter 5 or not. Not only can I not keep track of a decimal letter in a binary number, the sub states in this dp are not independent from the original state either. By that i mean, say I place a 1 in some index, and count all the positioning of the remaining digits such that the remaining digits dont make up a 5. But obviously this state is dependent on the overall number we build and whether that has a 5 in it or not. Using digit dp for this problem thus becomes difficult.
How exactly can I solve this problem? This problem was inspired from some variations of 2036F.
I may be wrong, but regardless this should provide some insights and ideas.
The following is a $$$O(2^{log_{10}{r}})$$$ solution:
We can work out range xor $$$[l,r]$$$ in O(1) using mod 4 pattern. xor $$$[l, r]$$$ = xor $$$[1, r]$$$ ^ xor $$$[1, l-1]$$$.
Then, we just need to xor all the numbers that contain the digit 5 to get the answer.
For this, we can use a bitmask to bruteforce all the possible positions of 5 that can appear in a number equal or less than r, then use some simple combinatorics and function xor $$$[l, r]$$$ to find the xor of all these numbers efficiently.
No you are correct but I should have been more specific in my post. I am only looking for solutions involving dynamic programming for educational purposes. This problem was inspired from my quest of efficiently solving a variation of 2036F where the mod is any number instead of only a power of 2, in logarithmic time as solving it in linear time to x is simple. As you can see solving the problem in the blog using number theory doesnt serve the purpose of enhancing digit dp for solving a wider variety of problems.
Ah I see. One clarification: you said you are solving a variation of 2036F where the mod is any number. I thought you were calculating the range xor of all the numbers between l and r which doesnt contain the letter 5. Aren't those two different things?
I can't think of feasible DP states and transitions. I'd be quite surprised if it is possible at all. I think a digit DP approach can only be used in 2036F because you can keep track of modulus easily as it is a power of 2.
Yes those are different problems entirely. And yes you are right that 2036F using ddp is simple due to the power of 2 mod. I am only exploring different ways to solve problems using ddp. That's why I said it was inspired. Kind of a stepping stone towards a greater goal.