• <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 閱讀(111) 評論(0)  編輯 收藏 引用 所屬分類: 動態規劃
            久久久久久久久久久免费精品| 国产一区二区三区久久| 久久99毛片免费观看不卡| 国产精品久久久久久一区二区三区| 久久精品中文騷妇女内射| 伊人色综合久久| 免费久久人人爽人人爽av| 久久久婷婷五月亚洲97号色| 精品久久久久久久久久久久久久久| 久久亚洲天堂| 国产精品久久波多野结衣| 亚洲国产综合久久天堂| 国内精品久久久久影院优| 色偷偷91久久综合噜噜噜噜| 久久亚洲欧美国产精品| 久久亚洲AV无码西西人体| 精品久久久久久成人AV| 狠狠色丁香久久婷婷综合蜜芽五月| 精品久久久久久综合日本| 久久天天躁狠狠躁夜夜不卡| 国产成人久久精品麻豆一区| 精品久久久无码21p发布 | 99国产精品久久| 亚洲欧美久久久久9999| 国内精品欧美久久精品| 97久久精品午夜一区二区| 亚洲人成伊人成综合网久久久 | 久久精品国产亚洲一区二区三区| 久久久亚洲裙底偷窥综合| 久久久久国产| 久久久久99精品成人片牛牛影视| 美女写真久久影院| 国产午夜久久影院| 久久久久亚洲AV无码网站| 一本一道久久综合狠狠老| 亚洲人成网站999久久久综合| 99久久人人爽亚洲精品美女| 久久综合狠狠综合久久激情 | 韩国免费A级毛片久久| 国产欧美久久久精品| 91亚洲国产成人久久精品网址|