How to calculate the range xor between l and r without numbers with the digit 5?

Правка en1, от Aspergillus, 2024-11-06 03:01:56

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.

Теги help, dp, range xor

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Aspergillus 2024-11-06 03:01:56 1072 Initial revision (published)