TopCoder problem "MegaCoolNumbers" used in SRM 431 (Division I Level Two)



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.
 

Definition

    
Class:MegaCoolNumbers
Method:count
Parameters:int, int
Returns:int
Method signature:int count(int N, int A)
(be sure your method is public)
    
 

Constraints

-A and N will be between 1 and 1,000, inclusive.

 

Examples

0)
    
1
1
Returns: 9
There 9 such numbers: 1, 2, 3, 4, 5, 6, 7, 8, 9.
1)
    
2
1
Returns: 45
Any two-digit number with non-decreasing digits will be a mega cool number of power 1.
2)
    
2
2
Returns: 0
There are no such numbers.
3)
    
10
3
Returns: 7502

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10259

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13522&pm=10259

Writer:

Gluk

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Dynamic Programming