Dynamic programming 0/49

Lesson 3 of 3 Advanced

Digit DP: decimal prefixes and bounded counting

Count integers under a large bound by processing decimal digits and retaining the information that controls the remaining choices.

4,568 words · 21 min read

Part 1 of 10 The Digit Sum problem

Digit DP and the Digit Sum problem

Some counting problems ask how many integers up to a bound have a property of their decimal digits: a digit sum divisible by 4, a digit sum between 10 and 20, no two equal digits next to each other. The bound can be far too large to test the integers one by one. Digit DP is dynamic programming that counts them by building the numbers one digit at a time. The first problem is Digit Sum.

Difficulty tier:Easy

You get a positive integer KK and an integer DD. Count the integers from 1 to KK whose digit sum, in base ten, is a multiple of DD. Print the count modulo 109+710^9 + 7.

The input holds KK on the first line and DD on the second.

Constraints

  • 1≤K<10100001 \le K < 10^{10000}
  • 1≤D≤1001 \le D \le 100

Sample 1 · Input

30
4

Output

6

Sample 2 · Input

1000000009
1

Output

2

Sample 3 · Input

98765432109876543210
58

Output

635270834

In the first sample K=30K = 30 and D=4D = 4. Six numbers from 1 to 30 have a digit sum that is a multiple of 4: 4, 8, 13, 17, 22 and 26. In the second sample D=1D = 1, so every number counts and the answer is KK itself, 1,000,000,009. The program prints the remainder of that modulo 109+710^9 + 7, which is 2.

The direct solution is a loop over the numbers from 1 to KK that adds up the digits of each one. It is correct but far too slow. Suppose KK were only 101810^{18}, about the largest bound a 64-bit integer can hold. Even at 10810^8 numbers a second the loop would run for 101010^{10} seconds, which is more than 300 years. In this problem KK can have 10,000 digits.

A bound with 10,000 digits has only 10,000 digit positions, though. So the program we write loops over the digit positions of KK, and at each position it counts whole groups of numbers at once, without listing them.