• <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>
            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 閱讀(109) 評論(0)  編輯 收藏 引用 所屬分類: 動態規劃
            亚洲综合伊人久久综合| 狠狠色丁香婷婷久久综合五月 | 久久综合亚洲色一区二区三区| 久久亚洲欧洲国产综合| 久久男人中文字幕资源站| 99久久精品免费看国产一区二区三区 | 久久99国产乱子伦精品免费| 国产精品久久久久…| 久久免费香蕉视频| AV无码久久久久不卡网站下载| 久久99国产一区二区三区| 色播久久人人爽人人爽人人片AV| 久久人妻少妇嫩草AV无码专区| 亚洲欧美日韩精品久久| 伊人久久大香线焦AV综合影院| 91精品国产91久久久久久青草| 国产精品久久久久a影院| 一级做a爰片久久毛片16| 久久婷婷五月综合色奶水99啪| 99久久国产综合精品成人影院| 亚洲AV无码久久| 综合久久久久久中文字幕亚洲国产国产综合一区首 | 日批日出水久久亚洲精品tv| 精品多毛少妇人妻AV免费久久| 久久国产V一级毛多内射| 久久精品中文无码资源站| 日本五月天婷久久网站| 精品久久久久久无码免费| 国产精品久久久天天影视| 99久久99久久精品国产片果冻| 日本久久中文字幕| 久久综合九色综合欧美就去吻| 色成年激情久久综合| 99久久婷婷国产综合亚洲| 久久精品欧美日韩精品| 久久久久99精品成人片直播| 一本色道久久88精品综合| 久久天天躁夜夜躁狠狠躁2022| 久久久久精品国产亚洲AV无码 | 99久久国产综合精品成人影院| 精品久久久久久亚洲|