翻译并整理latex渲染： First, let's see how many zebra-Like numbers less than or equal to 1018 exist. It turns out there are only 30 of them, and based on some zebra-like number zi , the next one can be calculated using the formula zi+1=4⋅zi+1 . Then, we have to be able to quickly calculate the zebra value for an arbitrary number x . Since each subsequent zebra-like number is approximately 4 times larger than the previous one, intuitively, it seems like a greedy algorithm should be optimal: for any number x , we can determine its zebra value by subtracting the largest zebra-like number that does not exceed x , until x becomes 0 . Let's prove the correctness of the greedy algorithm: Assume that y is the smallest number for which the greedy algorithm does not work, meaning that in the optimal decomposition of y into zebra-like numbers, the largest zebra-like number zi that does not exceed y does not appear at all. If the greedy algorithm works for all numbers less than y , then in the decomposition of the number y , there must be at least one number zi−1 . And since y−zi−1 can be decomposed greedily and will contain at least 3 numbers zi−1 , we will end up with at least 4 numbers zi−1 in the decomposition. Moreover, there will be at least 5 numbers in the decomposition because 4⋅zi−1<zi , which means it is also less than y . Therefore, if the fifth number is 1 , we simply combine 4⋅zi−1 with 1 to obtain zi ; otherwise, we decompose the fifth number into 4 smaller numbers plus 1 , and we also combine this 1 with 4⋅zi−1 to get zi . Thus, the new decomposition of the number y into zebra-like numbers will have no more numbers than the old one, but it will include the number zi — the maximum zebra-like number that does not exceed y . This means that y can be decomposed greedily. We have reached a contradiction; therefore, the greedy algorithm works for any positive number. Now, let's express the greedy decomposition of the number x in a more convenient form. We will represent the decomposition as a string s of length 30 consisting of digits, where the i -th character will denote how many zebra numbers zi are present in this decomposition. Let's take a closer look at what such a string might look like: si∈{0,1,2,3,4} ; if si=4 , then for any j<i , the character sj=0 (this follows from the proof of the greedy algorithm). Moreover, any number generates a unique string of this form. This is very similar to representing a number in a new numeric system, which we will call zebroid. In summary, the problem has been reduced to counting the number of numbers in the interval [l,r] such that the sum of the digits in the zebroid numeral system equals x . This is a standard problem that can be solved using dynamic programming on digits. Instead of counting the suitable numbers in the interval [l,r] , we will count the suitable numbers in the intervals [1,l] and [1,r] and subtract the first from the second to get the answer. Let dp[ind][sum][num_less_m][was_4] be the number of numbers in the interval [1,m] such that: they have ind+1 digits; the sum of the digits equals sum ; num_less_m=0 if the prefix of ind+1 digits of the number m is lexicographically greater than these numbers, otherwise num_less_m=1 ; was_4=0 if there has not been a 4 in the ind+1 digits of these numbers yet, otherwise was_4=1 . Transitions in this dynamic programming are not very difficult — they are basically appending a new digit at the end. The complexity of the solution is O(log2A) , if we estimate the number of zebra-like numbers up to A=1018 as logA .