MegaCoolNumbers
SRM 431 · 2008-12-23 · by Gluk
SRM 431 · 2008-12-23 · by Gluk · Dynamic Programming
Problem Statement
Problem Statement
A positive integer is called a cool number of power A if it can be separated into exactly A groups of consecutive digits, where the digits in each group form an arithmetic progression. An arithmetic progression is a sequence of numbers in which the difference between any two consecutive numbers is the same. A positive integer is called a mega cool number of power A if it is a cool number of power A, not a cool number of power A-1, and all its digits are in non-decreasing order.
Determine the number of mega cool numbers of power A that contain exactly N digits (with no leading zeroes). Return this number modulo 1,000,000,007.
Determine the number of mega cool numbers of power A that contain exactly N digits (with no leading zeroes). Return this number modulo 1,000,000,007.
Constraints
- A and N will be between 1 and 1,000, inclusive.
Examples
0)
3 1 Returns: 25
1)
3 5 Returns: 0
2)
10 6 Returns: 0
3)
10 2 Returns: 643
4)
6 10 Returns: 0
100)
1 1 Returns: 9
There 9 such numbers: 1, 2, 3, 4, 5, 6, 7, 8, 9.
101)
2 1 Returns: 45
Any two-digit number with non-decreasing digits will be a mega cool number of power 1.
102)
2 2 Returns: 0
There are no such numbers.
Submissions are judged against all 108 archived test cases, of which 8 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class MegaCoolNumbers with a public method int count(int N, int A) · 108 test cases · 2 s / 256 MB per case