• <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??梢酝瞥鰊最大是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)  編輯 收藏 引用 所屬分類: 動態規劃
            999久久久国产精品| 国产精品成人99久久久久91gav| 国产毛片欧美毛片久久久| 中文字幕久久精品无码| 久久综合香蕉国产蜜臀AV| 亚洲精品蜜桃久久久久久| 久久精品无码专区免费东京热 | 日产精品久久久久久久| 亚洲国产精品无码久久98| 久久精品免费全国观看国产| 99精品久久精品一区二区| 久久久久99精品成人片| 久久av高潮av无码av喷吹| 狠狠色婷婷久久一区二区 | 久久综合给合久久狠狠狠97色69| 国产女人aaa级久久久级| 久久久久久免费视频| 久久亚洲色一区二区三区| 久久国产乱子伦免费精品| 久久国产三级无码一区二区 | 91精品国产综合久久久久久| 欧美久久久久久精选9999| 久久久亚洲欧洲日产国码二区| 香蕉99久久国产综合精品宅男自 | 久久亚洲私人国产精品| 欧美黑人激情性久久| 9191精品国产免费久久| 国内精品人妻无码久久久影院| 99久久免费国产精品热| 久久久久久一区国产精品| 无遮挡粉嫩小泬久久久久久久| 久久99中文字幕久久| 欧美成人免费观看久久| 国产三级观看久久| 亚洲综合婷婷久久| 91秦先生久久久久久久| 久久综合88熟人妻| 久久亚洲AV成人无码| 久久久WWW免费人成精品| 欧美亚洲国产精品久久高清| 精品一区二区久久久久久久网站|