生成函數(shù)

回顧了以前的一些沒有完成的題目，發(fā)現(xiàn)自己的知識漏洞還挺多的，比如這個生成函數(shù)【以前用多重背包一直WA】

生成函數(shù)干嘛的？

比較功利的來說，就是用來求解各種排列組合的問題。如果是求組合問題，那就是構(gòu)造普通型生成函數(shù)，如果是求排列的問題，那就是構(gòu)造指數(shù)型生成函數(shù)。

最關(guān)鍵的是，這個不像DP，這個是有固定的模板的~那就很簡單了。以下是我找的一些生成函數(shù)的題目，基本都是一個思想，主要就是通過例子來熟練使用生成函數(shù)

普通型生成函數(shù)

假設(shè)你手里有1張1塊，1張2塊，1張5塊的紙幣，能夠組成多少種數(shù)量的錢，每種數(shù)量的錢有幾種組成方案

1塊 -> 金額1
2塊 -> 金額2
5塊 -> 金額5
1塊 + 2塊 -> 金額3
1塊 + 5塊 -> 金額6
2塊 + 5塊 -> 金額7
1塊 + 2塊 + 5塊 -> 金額8
（省略了一張都不用，金額0的情況）

設(shè)有函數(shù)：G(x) = a_0x^0 + a_1x^1 + a_2x^2 + …… + a_nx^n

其中，x2表示金額2的情況，x5表示金額5的情況，而前面的系數(shù)a2表示金額2的組成方案數(shù)量，a5表示金額5的組成方案數(shù)量

所以剛才舉例中可得到的函數(shù)是：
G(x) = x^0 + x^1 + x^2 + x^3 + x^5 + x^6 + x^7 + x^8

把這個函數(shù)分解開可以得到

  • 只有一張1塊的生成函數(shù) G(x) = x0 + x1 【可以有0塊和1塊這兩種金額】
  • 只有一張2塊的生成函數(shù) G(x) = x0 + x2

把這兩個式子相乘可以得到1塊和2塊的生成函數(shù)：
(x^0 + x^1)×(x^0 + x^2) = x^0 + x^1 + x^2 + x^3

  • 1塊和2塊的生成函數(shù) G(x) = x0 + x1 + x2 + x3
  • 只有一張5塊的生成函數(shù) G(x) = x0 + x5

把這兩個式子相乘可以得到1塊、2塊和5塊的生成函數(shù)：
(x^0 + x^1 + x^2 + x^3) × (x^0 + x^5) = x^0 + x^1 + x^2 + x^3 + x^5 + x^6 + x^7 + x^8

組合問題其實就是與非運(yùn)算的加法問題。比如上述方案中，就是1、2、5都要；1、2要，5不要；1、5要，2不要；……構(gòu)成的方案，而這種運(yùn)算方式恰好可以與冪級數(shù)的乘積對應(yīng)起來

HDU2082

26個字母價值各不相同，且每個字母的數(shù)量不一，最后問能組成多少種總價值為50的單詞的方案

在上面的例子中，只用到了一張1塊，1張2塊和1張5塊。假設(shè)有2張2塊，那么就應(yīng)該能組成0、2、4三種金額；假如有3張2塊，那么就能組成0，2，4，6四種金額。也就是說，3張2塊的生成函數(shù)為：
x^0 + x^2 + x^4 + x^6

如果數(shù)量不限，那么無數(shù)張2塊的生成函數(shù)為：
x^0 + x^2 + x^4 + …… + x^{2n}

在這個基礎(chǔ)之上，這類題目其實就變成了多項式的乘積問題。在實際編碼時，多項式用數(shù)組表示，數(shù)組的下標(biāo)就是對應(yīng)的多項式的次數(shù)。

首先初始化三個數(shù)組，a數(shù)組記為目前計算完成的生成函數(shù)，b數(shù)組是當(dāng)前正在計算的生成函數(shù)，將a數(shù)組和b數(shù)組進(jìn)行多項式的乘積操作，將計算的答案存儲到c數(shù)組中，最后將c數(shù)組拷貝到a數(shù)組中，更新生成函數(shù)，具體的編碼過程如下：

memset(a,0,sizeof(a));
memset(c,0,sizeof(c));
a[0] = 1;
for (int k=1; k<=26; k++) {
    memset(b,0,sizeof(b));
    cin>>num;
    if (num==0) continue;
    for (int i=0; i<=num && k*i<=50; i++)
        b[i*k] = 1; //當(dāng)前價值的生成函數(shù)，對應(yīng)倍數(shù)的系數(shù)置1
    for (int i=0; i<=50; i++) 
        for (int j=0; j<=50 && i+j<=50; j++)
            c[i+j] += a[i]*b[j];  //i+j表示冪指數(shù)相加，a[i]*b[j]表示系數(shù)相乘
    for (int i=0; i<=50; i++) {  //拷貝c數(shù)組
        a[i] = c[i];
        c[i] = 0;
    }
}

具體的思路就是不斷累乘多項式，每個多項式就是每個價值的生成函數(shù)，最后得到的就是所有價值的生成函數(shù)，也就是所有組成的方案數(shù)量，上面題目中，x50的系數(shù)就是對應(yīng)的方案數(shù)，也就是a[50]的值

簡化累乘過程

上述代碼中用到了三個數(shù)組，其實可以只用兩個數(shù)組，因為每一個新的生成函數(shù)，系數(shù)都是1，比如 4個價值為2 的字母的生成函數(shù)：
G(x) = x^0 + x^2 + x^4 + x^6 + x^8
而相乘的過程就是x0乘以數(shù)組a中的每一項，x2乘以數(shù)組a中的每一項……所以可以得到如下的簡化代碼

for (int i=0; i<=num && k*i<=50; i++)
    //當(dāng)前指數(shù)是i*k，系數(shù)是1
    for (int j=0; j<=50 && i*k+j<=50; j++)
        c[i*k+j] += a[j];

其中i*k就是當(dāng)前價值的生成函數(shù)的指數(shù)，當(dāng)字母價值為2時，k=2，i從0到4，也就對應(yīng)了當(dāng)前每一項的指數(shù)，對于每一項指數(shù)都需要乘以已經(jīng)計算好的a數(shù)組中的每一項，而a數(shù)組中的每一項的系數(shù)就是a[j]，指數(shù)是j，所以i*k+j就是新的指數(shù)，而相應(yīng)的系數(shù)，因為當(dāng)前系數(shù)是1，所以相當(dāng)于加上a[j]

最后需要求的是小于等于價值為50的單詞的方案總數(shù)，那就是a[1]累加到a[50]即可，也就是系數(shù)和相加

HDU2110

這里的總數(shù)不再是50這個固定的值了，而是所有給出的量的總和除以3，也就是1/3的總資產(chǎn)。

核心代碼還是一樣，只是替換了部分變量而已。下滿的p[i]存儲的是每個資產(chǎn)的價值，m[i]存儲的每個資產(chǎn)的數(shù)量，因為上題中資產(chǎn)的價值是固定的，所以這題需要增加數(shù)組存儲每個資產(chǎn)的價值和數(shù)量

for (int k=1; k<=n; k++) {
    for (int i=0; i<=m[k] && p[k]*i<=total; i++) {
        for (int j=0; j<=total && i*p[k]+j<=total; j++) {
            b[i*p[k]+j] += a[j];
            b[i*p[k]+j] %= 10000;
        }
     }
     for (int i=0; i<=total; i++) {
         a[i] = b[i];
         b[i] = 0;
     }
}
HDU1028

這題和上面兩題不同的是，在這題中，每一個價值的數(shù)量是無限的，有無限個1、無限個2……而循環(huán)的終點(diǎn)就是目標(biāo)價值量N

核心代碼與上面兩題基本相同

for (int k=1; k<=N; k++) {
    for (int i=0; k*i<=N; i++)
        for (int j=0; j<=N && i*k+j<=N; j++)
            b[i*k+j] += a[j];
    for (int i=0; i<=N; i++) {
        a[i] = b[i];
        b[i] = 0;
    }
}
HDU1171

這題是大一的時候用多重背包做了很久，一直沒做出來，最后就放著的一題?，F(xiàn)在去看看當(dāng)初寫的代碼量，都快到200行了。

在這題中，目標(biāo)價值不是固定的了。題意是盡可能的將所有資產(chǎn)平分，那也就是說，目標(biāo)價值是盡量接近總價值的一半，且存在可能的方案（系數(shù)不為0）

核心代碼與HDU2110一樣

for (int k=1; k<=N; k++) {
    for (int i=0; i<=m[k] && i*v[k]<=total; i++)
        for (int j=0; j<=total && i*v[k]+j<=total; j++)
            b[i*v[k]+j] += a[j];
    for (int i=0; i<=total; i++) {
        a[i] = b[i];
        b[i] = 0;
    }
}

在計算完成之后，從中點(diǎn)向起點(diǎn)遍歷，找到第一個系數(shù)不為0的指數(shù)即可，因為存在只有一種資產(chǎn)的情況，所以遍歷時不能只遍歷到1，而需要遍歷到0，也就是說一方什么都沒分到，另一方拿走全部

int t = total/2;
for (int i=t; i>=0; i--) {  //注意這里是大于等于0，而不是大于0
    if (a[i]!=0) {
        cout<<total-i<<" "<<i<<endl;
        break;
    }
}
HDU2152

在這題中，加上了每個價值量（水果）最少出現(xiàn)的次數(shù)和最多出現(xiàn)的次數(shù)，且題意中總數(shù)不大于100

因為第二個循環(huán)代表的是當(dāng)前價值量的使用次數(shù)，所以修改第二層循環(huán)即可，另外，由于在題意中，每個水果的價值量單位都是1，所以前面幾題中的p[k]、v[k]都可以省略

for (int k = 1; k<=N; k++) {
    for (int i = mins[k]; i<=maxs[k] && i<=100; i++)
        for (int j = 0; j<=100 && i+j<=100; j++)
            b[i+j] += a[j];
    for (int i=0; i<=100; i++) {
        a[i] = b[i];
        b[i] = 0;
    }
}

以上就是普通型生成函數(shù)的例題，通過這幾題，大概能得到一個通用的組合方案數(shù)計算的模板，理解之后，修改代碼就方便了

指數(shù)型生成函數(shù)

上面已經(jīng)提到，指數(shù)型生成函數(shù)是用來處理排列問題的。排列問題存在重復(fù)的排列項，比如11333，有2個1和3和3，就需要除以重復(fù)項2!3!，所以得到指數(shù)型的生成函數(shù)：

G(x) = a_0 + \frac{a_1}{1!}x + \frac{a_2}{2!}x^2 + \frac{a_3}{3!}x^3 + …… + \frac{a_n}{n!}x^n

假設(shè)有3個紅球，2個黃球，4個綠球。

那么我們規(guī)定3個紅球的生成函數(shù)是：
G(x) = 1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!}

2個黃球的生成函數(shù)是：
G(x) = 1 + \frac{x}{1!} + \frac{x^2}{2!}

3個紅球和2個黃球的生成函數(shù)是：
(1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!})×(1 + \frac{x}{1!} + \frac{x^2}{2!})

4個綠球的生成函數(shù)是：
G(x) = 1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!}

所以：3個紅球、2個黃球、4個綠球的生成函數(shù)為：
(1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!})×(1 + \frac{x}{1!} + \frac{x^2}{2!}) × (1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!}) =

1 + 3\frac{x^1}{1!} + 9\frac{x^2}{2!} + 26\frac{x^3}{3!} + 71\frac{x^4}{4!} + 180\frac{x^5}{5!} + 410\frac{x^6}{6!} + 805\frac{x^7}{7!} + 1260\frac{x^8}{8!} + 1135\frac{x^9}{9!}

也就是說，從這些球中，取2個的排列數(shù)為9，取3個的排列數(shù)為26，去4個的排列數(shù)為71……

非固定數(shù)量的球的生成函數(shù)
  • 無限數(shù)量
    G(x) = 1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + … + \frac{x^n}{n!} = e^x
  • 奇數(shù)個
    G(x) = \frac{x}{1!} + \frac{x^3}{3!} + \frac{x^5}{5!} + … + \frac{x^{2n+1}}{(2n+1)!} = \frac{e^x - e^{-x}}{2}
  • 偶數(shù)個
    G(x) = 1 + \frac{x^2}{2!} + \frac{x^4}{4!} + … + \frac{x^{2n}}{2n!} = \frac{e^x + e^{-x}}{2}

具體計算時，按固定數(shù)量的一樣，相乘即可，非固定數(shù)量可以直接用級數(shù)和來代替

HDU1521

這是固定數(shù)量的球，我們同樣使用數(shù)組來表示多項式，數(shù)組下標(biāo)對應(yīng)的是指數(shù)，數(shù)組中的值對應(yīng)的是系數(shù)

double Factorial(int n) { //計算n!
    double ans = 1;
    for (int i=1; i<=n; i++) ans*=i;
    return ans;
}
int main() {
    double a[11],b[11];
    int n,m,num[11];
    while (cin>>n>>m) {
        for (int i=1; i<=n; i++)
            cin>>num[i];
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        a[0] = 1.0;  //初始化數(shù)組為1*x^0 = 1
        for (int k=1; k<=n; k++) {  //計算第k個數(shù)
            for (int i=0; i<=num[k]; i++)  //當(dāng)前計算的數(shù)的指數(shù)遍歷
                for (int j=0; j<=m; j++) //對于每一個指數(shù)，都分別乘以已經(jīng)計算好的多項式
                    b[j+i] += a[j]/Factorial(i);  //每一個項初始化的都是x^n/n!，計算時，相當(dāng)于指數(shù)相加，系數(shù)除以n!
            for(int j=0;j<=m;j++){
                a[j] = b[j];
                b[j] = 0;
            }
        }
        cout<<fixed<<setprecision(0)<<a[m]*Factorial(m)<<endl; //保證無小數(shù)輸出
    }
    return 0;
}

我們發(fā)現(xiàn)核心代碼還是相同的，由于數(shù)組沒項存儲的還是指數(shù)對應(yīng)的系數(shù)，而指數(shù)是1/n!，所以計算時存在小數(shù)，所以用double類型

核心代碼中的計算b[j+i] += a[j]/Factorial(i); ，由于剛初始化時的每一個數(shù)的生成函數(shù)的每一項的系數(shù)都是1/i! (i表示的是當(dāng)前的指數(shù))，所以多項式相乘就相當(dāng)于指數(shù)相加，系數(shù)等于原系數(shù)除以i！

大致上與普通型生成函數(shù)相比，核心代碼還是一致的，只是計算時多出了計算階乘的步驟

HDU2065

這題的與上題相比不同的是，數(shù)字（字母）有無限個，出現(xiàn)的次數(shù)不限或者限奇數(shù)次、偶數(shù)次

根據(jù)上面的公式，得到無限次的生成函數(shù)和偶數(shù)次的生成函數(shù)分別是：
e^x 和 \frac{e^x + e^{-x}}{2}

而題意中，無限次的有兩個字母，偶數(shù)次的也有兩個字母，所以生成函數(shù)為：
e^x × e^x × \frac{e^x + e^{-x}}{2} × \frac{e^x + e^{-x}}{2} = \frac{e^{4x}+2e^{2x}+1}{4}

現(xiàn)在我們需要求的是排列的個數(shù)是n的時候的方案數(shù)量，也就是\frac{x^n}{n!}的系數(shù)是多少

我們把e4x和e2x在x=0處進(jìn)行泰勒展開，變?yōu)槎囗検健究偹阌玫礁叩葦?shù)學(xué)中的東西了】。展開式就不累贅了，展開后，e4x的\frac{x^n}{n!}的系數(shù)為4n；e2x的\frac{x^n}{n!}的系數(shù)為2n

所以，所求的系數(shù)為\frac{4^n + 2^{n+1}}{4} = 4^{n-1} + 2^{n-1}

所以只要將n帶入這個式子即可，當(dāng)然由于題中的n很大，所以要用到快速冪，快速冪在前面的文章中已經(jīng)有介紹了，矩陣快速冪——入門

所以最后的答案就是(quickPow(4,n-1)+quickPow(2,n-1))%100

POJ3734和上題相同，題意表述不同而已

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容