青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

posts - 7,comments - 3,trackbacks - 0

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的數據范圍真的有點不能接受......
看了一個大牛的題解,用數論證明了這個題可以轉化成多重背包.....

思路:
首先,我們可以證明金字塔最頂端的數和最低端的數是有關系的,關系就是
C0N-1*a0 + C1N-1*a1 + C2n-1*a2 + ...... Cn-1n-1*an-1 = T      (1)

而且因為T <= 1,000,000。可以推出n最大是20.....
繼續觀察上述(1),因為必須符合金字塔,所以a序列都至少為1,所以,我們可以發現,先用T減去每個系數(因為至少一次),之后用那n-1個數做多重背包,求T的方案就行了。

復雜度是(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 > 20return 0;
    
if (1 << (n - 1> top) return 0;
    top 
-= 1 << (n - 1);
    memset(dp, 
0sizeof(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, 
-1sizeof(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 閱讀(116) 評論(0)  編輯 收藏 引用 所屬分類: 動態規劃
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            欧美四级剧情无删版影片| 国产精品中文字幕在线观看| 亚洲第一精品电影| 欧美承认网站| 欧美日本精品一区二区三区| 正在播放欧美一区| 亚洲男人影院| 在线观看欧美日韩| 亚洲人成7777| 国产精品一区二区三区久久| 久久影视精品| 欧美巨乳在线| 久久久久久9| 欧美精品日日鲁夜夜添| 亚洲欧美日韩精品综合在线观看| 性做久久久久久久久| 亚洲黄色在线视频| 亚洲一区二区三区免费在线观看| 激情欧美一区二区三区| 99精品欧美一区| 海角社区69精品视频| 亚洲国产日本| 国产一区二区三区在线播放免费观看| 美女精品在线观看| 欧美日韩在线免费| 老司机久久99久久精品播放免费 | 久久精品在线| 欧美一级日韩一级| 亚洲精品视频在线看| 亚洲欧美电影在线观看| 亚洲美女少妇无套啪啪呻吟| 午夜视频一区二区| 亚洲一区二区三区欧美| 久久综合久久综合久久综合| 欧美一区二区视频在线观看2020 | 国产精品亚洲综合久久| 免费一级欧美片在线播放| 国产精品福利影院| 亚洲欧洲日本国产| 一区二区在线看| 亚洲欧美日韩成人高清在线一区| 日韩视频在线观看国产| 久久成人精品无人区| 亚洲欧美国产毛片在线| 欧美精品一区二区三区很污很色的| 久久偷窥视频| 国产一区二区三区日韩| 亚洲免费网址| 性欧美videos另类喷潮| 欧美视频国产精品| 日韩视频中午一区| 日韩网站在线| 欧美极品在线观看| 亚洲国产日韩一区| 亚洲欧洲视频| 欧美电影电视剧在线观看| 美女图片一区二区| 亚洲电影免费观看高清| 久久久久久97三级| 男女精品视频| 亚洲精品国产系列| 欧美国产第二页| 亚洲国产精品专区久久| 91久久久久久国产精品| 欧美大片免费久久精品三p| 亚洲第一免费播放区| 亚洲精品久久久蜜桃| 欧美风情在线| aaa亚洲精品一二三区| 亚洲午夜视频| 国产伦精品一区二区三区免费迷 | 欧美一区二区久久久| 久久精品欧洲| 亚洲高清中文字幕| 欧美精品在线极品| 亚洲性av在线| 久久久免费精品| 亚洲国产精品成人一区二区| 欧美激情综合色| 亚洲小视频在线观看| 久久久亚洲高清| 日韩一区二区高清| 欧美色图五月天| 香蕉久久夜色| 欧美国产日本高清在线| 中文精品视频一区二区在线观看| 欧美日韩一区二区视频在线观看 | 欧美性开放视频| 午夜精品三级视频福利| 欧美成年人视频网站| 国产精品99久久不卡二区| 国产日本亚洲高清| 欧美精品 国产精品| 亚洲欧美日韩国产综合在线 | 亚洲国产美女| 亚洲欧美综合精品久久成人| 国产一区欧美日韩| 欧美—级在线免费片| 欧美一区二区三区视频| 亚洲欧洲日本在线| 久久久免费观看视频| 亚洲天堂av高清| 在线观看成人av| 国产精品欧美日韩一区| 男人的天堂成人在线| 亚洲影视在线播放| 亚洲人www| 老司机精品视频网站| 午夜精品一区二区三区在线播放| 亚洲电影在线免费观看| 国产伦精品一区二区三区免费迷 | 亚洲一区二区三区乱码aⅴ| 欧美国内亚洲| 久久久久久网站| 亚洲欧美制服中文字幕| 日韩视频免费在线观看| 一区二区在线观看视频在线观看| 欧美性片在线观看| 欧美精品一区二区三区一线天视频| 香蕉久久夜色精品国产| 一级日韩一区在线观看| 亚洲人成在线免费观看| 欧美激情国产日韩精品一区18| 欧美在线视频一区二区| 亚洲男人第一网站| 一本色道久久综合亚洲精品按摩| 亚洲成色777777在线观看影院| 国产精品亚发布| 国产精品毛片va一区二区三区 | 亚洲区一区二| 亚洲国产精品福利| 在线成人中文字幕| 狠狠色丁香婷婷综合| 国产午夜精品理论片a级大结局 | 国产日韩精品一区二区浪潮av | 久久亚洲精品伦理| 久久九九国产精品怡红院| 欧美一级二区| 欧美在线黄色| 久久久精品国产一区二区三区| 午夜日韩在线观看| 欧美一二三区在线观看| 欧美在线观看视频在线| 欧美在线二区| 老牛嫩草一区二区三区日本| 久久人体大胆视频| 麻豆精品视频在线| 欧美精品色综合| 欧美日韩精品综合| 国产精品久久综合| 国产一区二区三区高清播放| 狠狠色丁香久久婷婷综合丁香| 黑人一区二区三区四区五区| 亚洲国产乱码最新视频| 99国内精品| 欧美亚洲一区二区三区| 久久久久久网| 亚洲精品国产精品乱码不99按摩| 亚洲精品五月天| 亚洲免费婷婷| 美女精品视频一区| 欧美日韩一区二区三区视频| 国产精品免费观看在线| 国产亚洲欧美日韩一区二区| 亚洲国产电影| 亚洲综合色网站| 久久国产加勒比精品无码| 鲁大师成人一区二区三区| 亚洲人成毛片在线播放| 亚洲欧美日韩另类| 老司机午夜精品视频| 国产精品久久久久aaaa| 激情国产一区二区| av成人免费| 久久一二三区| 这里只有精品电影| 久久这里有精品15一区二区三区| 欧美另类久久久品| 精品成人一区二区| 亚洲自拍偷拍麻豆| 免费观看成人鲁鲁鲁鲁鲁视频| 日韩一级免费| 久久在线视频在线| 国产视频在线一区二区| 夜夜嗨av色一区二区不卡| 久久嫩草精品久久久精品一| 亚洲美女在线观看| 老司机精品导航| 国产日韩精品久久| 亚洲影院一区| 亚洲狠狠丁香婷婷综合久久久| 欧美一级精品大片| 国产精品高潮呻吟久久av黑人| 亚洲国产精品一区二区久| 欧美一区二区高清| 一区二区三区日韩欧美精品| 欧美国产日韩一区二区| 一区二区三区自拍| 久久夜色精品国产亚洲aⅴ| 亚洲自拍电影|