GreaterThanAll
Cognizance - Insomnia · 2019-04-11 · by Vasyl[alphacom]
Problem Statement
Given a sequence A = (a1, a2, ..., an) (where a[i] >= 1 are integers), of length n, we define the Peak_Set as
Peak_Set(A) = { a[i] : a[i] > a[j] for all j < i }
For example, for the sequence A = {2, 1, 5, 6, 3, 3, 2, 8, 10, 4}, Peak_Set(A) = {2, 5, 6, 8, 10}.
For a given integers N and K, you need to count the number of Sequences 'X' of length N with Peak_Set(X) = {1, 2, 3,..., K}, modulo (109 + 7).
Constraints
- The number of elements of the sequence, N ranges from 1 to 106, inclusive.
- The value of K is between 1 and N.
3 2 Returns: 3
The only possible sequences are "112", "121" and "122" whose Peak_Set is {1, 2}.
762476 157929 Returns: 441862509
827329 254322 Returns: 801382793
812215 610951 Returns: 375724243
506277 454955 Returns: 317906005
Submissions are judged against all 100 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class GreaterThanAll with a public method int count(int n, int k) · 100 test cases · 2 s / 256 MB per case