1357. How Many Have That Digit Sum
Count the integers from 1 to n whose digits add up to exactly s.
n reaches 10^18, so nothing can be enumerated. The numbers have to be counted
by their digits rather than visited.
Build them left to right. At each position you choose a digit, and what matters about everything chosen so far is only:
how many digits are still to come
how much of the target sum is left
whether the prefix so far equals n's prefix (the TIGHT flag)
whether any non-zero digit has appeared yet (so 0 is not counted)
That is a small state, and different prefixes reaching the same state have the
same number of completions, so the counts are memoised and the whole thing runs
in about 19 * 163 * 2 * 2 states.
The tight flag is the part that has to be right. While the prefix matches n
exactly, the next digit cannot exceed n's digit at that position. Once a
smaller digit is chosen the prefix is already below n and every later digit is
free, so the flag turns off and never returns.
This shape is called digit dynamic programming, and it answers a whole family of
questions: how many values below n avoid a digit, are divisible by k, or have
no two equal adjacent digits. Recognising it is worth more than this one answer.
Constraints - `1 ≤ n ≤ 1000000000000000000` - `1 ≤ s ≤ 200`
Input
One line containing two integers n and s.
Output
Print how many integers from 1 to n have digits summing to exactly s.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.