NumberPyramids
SRM 459 · 2009-11-12 · by gojira_tc
SRM 459 · 2009-11-12 · by gojira_tc · Dynamic Programming, Math
Problem Statement
Problem Statement
Suppose that there are N numbers written in a row. A row above this one consists of N-1 numbers, the i-th of which is the sum of the i-th and (i+1)-th elements of the first row. Every next row contains one number less than the previous one and every element is the sum of the two corresponding elements in the row below. The N-th row contains a single number. For example, if the initial numbers are {2,1,2,4}, the whole structure will look like this:
Givenint s baseLength and top, compute the total number of different number pyramids consisting of positive integers, having baseLength elements in the first row and the value at the top equal to top. Since the number of such pyramids might be enormous, return the result modulo 1,000,000,009.
15 6 9 3 3 6 2 1 2 4We shall refer to such a structure as a number pyramid. Two number pyramids are equal if all the numbers at corresponding positions are equal.
Given
Constraints
- baseLength will be between 2 and 1,000,000, inclusive.
- top will be between 1 and 1,000,000, inclusive.
Examples
0)
3 5 Returns: 2
The following are two possible pyramids with 3 numbers in the base and the number 5 at the top:
1)
5 16 Returns: 1
The only number pyramid with base of size 5 and 16 at the top looks like this:
2)
4 15 Returns: 24
3)
15 31556 Returns: 74280915
4)
150 500 Returns: 0
Submissions are judged against all 148 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class NumberPyramids with a public method int count(int baseLength, int top) · 148 test cases · 2 s / 256 MB per case