FINDMAX - Finding Maximum
One way of finding the maximum element in an array is to initialize a variable to the first element in the array, iterate through the remaining array, and update the variable whenever a value strictly greater than it is found. Assuming that the array contains N elements each in the range 1..K, how many such arrays exist such that the above algorithm performs exactly P updates? Initialization of the variable is not counted as an update.
For example, the possible arrays for N = 4, K = 3 and P = 2 are:
- {1, 1, 2, 3}
- {1, 2, 1, 3}
- {1, 2, 2, 3}
- {1, 2, 3, 1}
- {1, 2, 3, 2}
- {1, 2, 3, 3}
Input
The first line contains T the number of test cases. There follow T lines, containing 3 space separated integers N, K and P.
Output
Output T lines, one for each test case. On each line, output the answer as asked above. Since the answers can get very big, output the answer modulo 1000000007.
Example
Sample Input: 3 4 3 2 2 3 1 3 4 1 Sample Output: 6 3 30
Constraints
1 <= T <= 100
1 <= n <= 100
1 <= K <= 300
0 <= P < n
hide comments
phantomhive:
2018-08-28 19:02:56
For this problem (p+1) <= k right? Last edit: 2018-08-28 19:03:11 |
|
hello_world123:
2018-06-21 09:50:05
For those scratching their head , just think about finding the number of arrays of length n , and given k and p, assuming you already know the number of arrays of length <= n
|
|
arpit_01:
2018-03-01 15:00:38
how to approach the recurrence relation?
|
|
nitesh kumar:
2014-06-18 12:05:08
optimization tips here:
|
|
:D:
2011-03-28 08:06:37
Not per test case, but per input :) |
|
Pratham Khandelwal:
2011-01-28 12:25:30
Is O(n*K*P) per test case sufficient?
|
Added by: | Varun Jalan |
Date: | 2010-01-24 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: NODEJS OBJC PERL6 SQLITE VB.NET |
Resource: | own problem used for Codechef Snackdown Onsite |