SuperSum
SRM 467 · 2009-11-12 · by vexorian
SRM 467 · 2009-11-12 · by vexorian · Advanced Math
Problem Statement
Problem Statement
SuperSum is a function defined as:
- SuperSum(0 , n) = n, for all positive n.
- SuperSum(k , n) = SuperSum(k-1 , 1) + SuperSum(k-1 , 2) + ... + SuperSum(k-1 , n), for all positive k, n.
Given k and n, return the value for SuperSum(k , n) modulo 1000000007.
Constraints
- k will be between 1 and 50, inclusive.
- n will be between 1 and 1000000000, inclusive.
Examples
0)
1 3 Returns: 6
When k = 1, SuperSum is equal to the sum of the first n = 3 numbers: 1 + 2 + 3 = 6.
1)
2 3 Returns: 10
SuperSum(2 , 3) = SuperSum(1 , 1) + SuperSum(1 , 2) + SuperSum(1 , 3) = 1 + 3 + 6 = 10.
2)
4 10 Returns: 2002
3)
10 35 Returns: 150595840
4)
50 1000000000 Returns: 0
Submissions are judged against all 78 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SuperSum with a public method int calculate(int k, int n) · 78 test cases · 2 s / 256 MB per case