IncreasingNumber
SRM 452 · 2009-11-05 · by rng_58
SRM 452 · 2009-11-05 · by rng_58 · Dynamic Programming, Math
Problem Statement
Problem Statement
A positive integer is called Increasing Number if its digits are in non-descending order from left to right in decimal notation. For example, 1234, 111, 58 and 8899 are Increasing Numbers, while 314, 7654 and 2009 are not.
You are given along digits and an int divisor. Calculate the number of Increasing Numbers that satisfy both of the following conditions and return this number modulo 1,000,000,007.
You are given a
- The number contains exactly digits digits in the decimal notation with no leading zeroes.
- The number is divisible by divisor.
Constraints
- digits will be between 1 and 1,000,000,000,000,000,000 (10^18), inclusive.
- divisor will be between 1 and 500, inclusive.
Examples
0)
2 12 Returns: 4
12, 24, 36, and 48 satisfy the conditions.
1)
3 111 Returns: 9
All 3-digits numbers divisible by 111 are Increasing Numbers.
2)
452 10 Returns: 0
There is no Increasing Number divisible by 10.
3)
6 58 Returns: 38
4)
26542766498659 25 Returns: 766312864
44)
1000000000000000000 256 Returns: 479459
maximal pre-cycle length
Submissions are judged against all 61 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class IncreasingNumber with a public method int countNumbers(long long digits, int divisor) · 61 test cases · 2 s / 256 MB per case