DivFreed2
SRM 684 · 2016-03-02 · by subscriber
SRM 684 · 2016-03-02 · by subscriber · Brute Force, 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 10, inclusive.
- k will be between 1 and 100,000, inclusive.
Examples
0)
2 2 Returns: 3
The three arrays Hero likes are {1,1}, {1,2}, and {2,2}.
1)
9 1 Returns: 1
The only array Hero likes is {1,1,1,1,1,1,1,1,1}.
2)
3 3 Returns: 15
3)
1 107 Returns: 107
4)
2 10 Returns: 83
Submissions are judged against all 133 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class DivFreed2 with a public method int count(int n, int k) · 133 test cases · 2 s / 256 MB per case