Given a huge integer N, you can use the dynamic programming algorithm to count up the number of things that satisfy the condition from non-negative integers less than or equal to N.
Example of my implementation
-
DP S An integer between 1 and K, where the sum of each digit in decimal notation is a multiple of D.
-
ABC154E An integer greater than or equal to 1 and less than or equal to N and exactly K non-zero numbers when expressed in decimal notation.
-
Use the information about the upper i digits to find the information for i+1 digits
- ABC154E: Let x be the number of cases where k non-zero numbers are used in the upper i digits.
- If the next digit is 0, it remains k, x ways; if 1 to 9, it becomes k+1, 9x ways. python
- ABC154E: Let x be the number of cases where k non-zero numbers are used in the upper i digits.
for k in range(K + 1):
new_less[k] += less[k] # for 0
new_less[k + 1] += 9 * less[k] # for 1..9
-
The only exception is when the upper i digits match N
- 1-9 could exceed N
- The i+1st digit of N needs to be taken care of.
- The number of upper i digits matching N is always one way, so we have it by value, not by array.
- Some of the explanations in the world make this an array too, but so far I haven’t encountered a problem that requires it.
-
If the last case matching N satisfies the condition, answer +1.
-
If implemented naturally, the value is for “integers greater than or equal to 0”, so depending on the problem conditions, the case of 0 is subtracted.
https://maspypy.com/atcoder-参加感想-2019-02-16abc-155
This page is auto-translated from /nishio/桁DP using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.