DivFree
SRM 684 · 2016-03-02 · by subscriber
SRM 684 · 2016-03-02 · by subscriber · Dynamic Programming
Problem Statement
Problem Statement
Hero likes some arrays. The arrays he likes are the arrays that have all of the following properties:
int s n and k.
Let X be the number of different arrays Hero likes.
Compute and return the value (X mod 1,000,000,007).
- The length of the array is n.
- Each element is an integer between 1 and k, inclusive.
- Whenever A and B are two consecutive elements of the array (in this order), we have (A <= B) or (A mod B != 0).
For example, suppose n=4 and k=7. Hero will like the array {1,7,7,2} because it has the right length, all elements are in the correct range, 1 <= 7, 7 <= 7, and 7 mod 2 != 0. Hero will not like the array {4,4,4,2}.
You are given theConstraints
- n will be between 1 and 50,000, inclusive.
- k will be between 1 and 50,000, inclusive.
Examples
0)
2 2 Returns: 3
The three arrays Hero likes are {1,1}, {1,2}, and {2,2}.
1)
3 2 Returns: 4
The four arrays Hero likes in this case are {1,1,1}, {1,1,2}, {1,2,2}, and {2,2,2}.
2)
3 3 Returns: 15
3)
1 107 Returns: 107
4)
5 6 Returns: 2292
Submissions are judged against all 128 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class DivFree with a public method int dfcount(int n, int k) · 128 test cases · 2 s / 256 MB per case