NumberPyramids
Time Limit: 20 Sec Memory Limit: 128 MB
Submissions: 103 Solved: 41
Description
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:
15
6 9
3 3 6
2 1 2 4
We 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 ints 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.
Input
Two numbers -- baseLength and top.
baseLengthwill be between 2 and 1,000,000, inclusive.
topwill be between 1 and 1,000,000, inclusive.
Output
The total number of different number pyramids Constraints
Sample Input
3 5
5 16
4 15
15 31556
150 500
Sample Output
2
1
24
74280915
0
HINT
1) The following are two possible pyramids with 3 numbers in the base and the number 5 at the top:
2) The only number pyramid with base of size 5 and 16 at the top looks like this:
Source
Topcoder SRM
非常V5的一道題，一開是以為但是DP，1,000,000的數(shù)據(jù)范圍真的有點不能接受......
看了一個大牛的題解，用數(shù)論證明了這個題可以轉(zhuǎn)化成多重背包.....
思路：
首先，我們可以證明金字塔最頂端的數(shù)和最低端的數(shù)是有關(guān)系的，關(guān)系就是
C0N-1*a0 + C
1N-1*a
1 + C2n-1*a
2 + ...... C
n-1n-1*a
n-1 = T
（1）而且因為T <= 1,000,000。可以推出n最大是20.....
繼續(xù)觀察上述（1），因為必須符合金字塔，所以a序列都至少為1，所以，我們可以發(fā)現(xiàn)，先用T減去每個系數(shù)（因為至少一次），之后用那n-1個數(shù)做多重背包，求T的方案就行了。
復(fù)雜度是(N * 1,000,000)，可以接受。
代碼：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int mod = 1000000009;
int dp[1000100];
int n, top;
int c[21][21];
void init()
{
for (int i = 1; i < 21; ++i)
{
c[i][0] = c[i][i] = 1;
c[i][1] = c[i][i - 1] = i;
for (int j = 2; j < i - 1; ++j)
{
c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
}
}
int work(int n, int top)
{
if (n > 20) return 0;
if (1 << (n - 1) > top) return 0;
top -= 1 << (n - 1);
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for (int i = 0; i <= n - 1; ++i)
{
for (int k = 0; k <= top; ++k)
{
if ((dp[k] && k + c[n - 1][i] <= top) || k == 0)
{
dp[k + c[n - 1][i]] = (dp[k + c[n - 1][i]] + dp[k]) % mod;
}
}
}
return dp[top];
}
int main()
{
memset(c, -1, sizeof(c));
init();
while (scanf("%d%d", &n, &top) != EOF)
{
printf("%d\n", work(n ,top));
}
return 0;
}
posted on 2011-10-15 22:15
LLawliet 閱讀(111)
評論(0) 編輯 收藏 引用 所屬分類:
動態(tài)規(guī)劃