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

            思路:
            首先,我們可以證明金字塔最頂端的數(shù)和最低端的數(shù)是有關(guān)系的,關(guān)系就是
            C0N-1*a0 + C1N-1*a1 + C2n-1*a2 + ...... Cn-1n-1*an-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 > 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)  編輯 收藏 引用 所屬分類: 動態(tài)規(guī)劃
            色婷婷综合久久久久中文一区二区 | 超级碰碰碰碰97久久久久| 久久综合视频网站| 久久久久久久久66精品片| 一本久久知道综合久久| 久久99精品国产99久久| 狠狠精品干练久久久无码中文字幕| 久久电影网| 久久久久人妻一区精品色| 99久久精品这里只有精品| 久久国产AVJUST麻豆| 国产精品99久久99久久久| 欧美精品丝袜久久久中文字幕 | A狠狠久久蜜臀婷色中文网| 曰曰摸天天摸人人看久久久| 亚洲国产高清精品线久久| 久久99国产精品一区二区| 99久久香蕉国产线看观香| 国产精品99久久99久久久| 久久久久久久久久久久久久| 精品久久久久久无码免费| 精品久久久久久国产潘金莲 | 无码精品久久久天天影视 | 精品无码久久久久久久动漫| 久久久精品人妻一区二区三区蜜桃| 久久久久四虎国产精品| 欧美亚洲国产精品久久| 久久精品国产欧美日韩| 精品久久无码中文字幕| 久久精品aⅴ无码中文字字幕重口 久久精品a亚洲国产v高清不卡 | 亚洲国产精品久久久久| 久久婷婷国产剧情内射白浆| 久久99精品久久久久久水蜜桃| 亚洲AV无码成人网站久久精品大| 久久久久久久国产免费看| 久久精品www人人爽人人| 伊人久久大香线蕉av不卡| 久久国产亚洲精品| 一本色道久久88精品综合 | 影音先锋女人AV鲁色资源网久久| 亚洲精品成人久久久|