程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU-2082（母函數）

HDU-2082（母函數）

編輯：C++入門知識

HDU-2082（母函數）

找單詞

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2739 Accepted Submission(s): 1941

Problem Description 假設有x1個字母A， x2個字母B,..... x26個字母Z，同時假設字母A的價值為1，字母B的價值為2,..... 字母Z的價值為26。那麼，對於給定的字母，可以找到多少價值<=50的單詞呢？單詞的價值就是組成一個單詞的所有字母的價值之和，比如，單詞ACM的價值是1+3+14=18，單詞HDU的價值是8+4+21=33。(組成的單詞與排列順序無關，比如ACM與CMA認為是同一個單詞）。

Input 輸入首先是一個整數N，代表測試實例的個數。然後包括N行數據，每行包括26個<=20的整數x1,x2,.....x26.

Output 對於每個測試實例，請輸出能找到的總價值<=50的單詞數,每個實例的輸出占一行。

Sample Input 2 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 2 6 2 10 2 2 5 6 1 0 2 7 0 2 2 7 5 10 6 10 2 10 6 1 9

Sample Output 7 379297

Source 2006/1/15 ACM程序設計期末考試

Recommend 其他相同類型的鏈接，大牛的博客寫的很好http://www.cnblogs.com/wally/archive/2012/07/13/hdu1028_1085_1171_.html#undefined

生成函數是說，構造這麼一個多項式函數g(x)，使得x的n次方系數為f(n)。

對於母函數，看到最多的是這樣兩句話：

1.“把組合問題的加法法則和冪級數的乘冪對應起來。”

2.“把離散數列和冪級數一一對應起來，把離散數列間的相互結合關系對應成為冪級數間的運算關系，最後由冪級數形式來確定離散數列的構造。 “

例子：

有1克、2克、3克、4克砝碼各一枚，問能稱出哪幾種重量？每種重量各有幾種方案？

下面是用母函數解決這個問題的思路：

首先，我們用X表示砝碼，X的指數表示砝碼的重量。那麼，如果用函數表示每個砝碼可以稱的重量，

1個1克的砝碼可以用函數X^0 + X^1表示，

1個2克的砝碼可以用函數X^0 + X^2表示，

依次類推。

如果我們把上面2個多項式相乘，可以得到X^0 + X^1 + X^2 + X^3。繼續把它與X^0 + X^3相乘，得到X^0 + X^1 + X^2 + 2*X^3 + X^4 + X^5 + X^6。

接著把它與X^0+X^4相乘，最後得到X^0 + X^1 + X^2 + 2*X^3 + 2*X^4 + 2*X^5 + 2*X^6 + 2*X^7 + X^8 + X^9 + X^10。

由於X的指數表示的是重量，所以，在相乘時，根據冪的運算法則（同底冪相乘，指數相加），得到的結果正是所有的方案。而且，每個X前面的系數代表它有幾種方案。

需要注意的是，如果有2個1克的砝碼，應該用X^0 + X^1 + X^2表示，而不是X^0 + 2*X^1。

母函數還可以解決其他問題，比如，整數劃分。

整數劃分是個很經典的問題，劃分規則就不再細述，直接說思路。與上面的問題相比，每種砝碼的個數不再是1個，而是無限個。於是，

1克的砝碼可以用X^0 + X^1 + X^2 + X^3 ……表示，

2克的砝碼可以用X^0 + X^2 + X^4 + X^6……表示，

3克的砝碼可以用X^0 + X^3 + X^6 + X^9……表示，

依次類推。

相乘後求出X^n的系數，就是結果。

總而言之，解決此類問題，只要模擬好2個多項式相乘就好了。

大概思路是開2個數組，c1[ ]保存當前得到的多項式各項系數，c2[ ]保存每次計算時的臨時結果，當每次計算完畢後，把它賦給c1，然後c2清零。

計算的時候，開3層for循環。最外層，記錄它正在與第幾個多項式相乘。第二層，表示c1中的每一項，第三層表示後面被乘多項式中的每一項。

代碼：

#include
#include
#include
#include
#include
#include
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;

typedef long long ll;
typedef unsigned long long llu;

const int maxd=200;
//---------------------
llu c1[maxd],c2[maxd];
int x[30];
int n;

int main()
{
    freopen("1.txt","r",stdin);
    int kase;
    scanf("%d",&kase);
    while(kase--)
    {
        //int cnt=0;
        for(int i=1; i<=26; ++i)
            scanf("%d",&x[i]);
        mem(c1,0),mem(c2,0);
        c1[0]=1;
        for(int i=1; i<=26; ++i)
        {
            for(int j=0; j<=50; ++j)
            {
                for(int k=0; k+j<=50 && k<=x[i]*i; k+=i)
                    c2[k+j]+=c1[j];
            }
            for(int k=0; k<=50; ++k)
                c1[k]=c2[k],c2[k]=0;
        }
        llu sum=0;
        for(int i=1; i<=50; ++i)
            sum+=c1[i];
        printf("%llu\n",sum);
    }
    return 0;
}