?母函數(shù)(生成函數(shù)):? ?

??? 生成函數(shù)有普通型生成函數(shù)和指數(shù)型生成函數(shù)兩種。

??? 形式上，普通型母函數(shù)用于解決多重集的組合問題，

??????????????? 指數(shù)型母函數(shù)用于解決多重集的排列問題。

??? 母函數(shù)還可以解決遞歸數(shù)列的通項(xiàng)問題（例如使用母函數(shù)解決斐波那契數(shù)列，Catalan數(shù)的通項(xiàng)公式）。

普通母函數(shù)：

??? 構(gòu)造母函數(shù)G(x), G(x) = a0 + a1*x + a2*?+ a3*?+....+ an*，? 則稱G(x)是數(shù)列a0,a1…an的母函數(shù)。

??? 通常普通母函數(shù)用來解多重集的組合問題，其思想就是構(gòu)造一個(gè)函數(shù)來解決問題，一般過程如下：

??? 1.建立模型：物品n種,每種數(shù)量分別為k1,k2,..kn個(gè)，每種物品又有一個(gè)屬性值p1,p2,…pn,(如本題的字母價(jià)值)，

????? 求屬性值和為m的物品組合方法數(shù)。（若數(shù)量ki無窮 也成立，即對(duì)應(yīng)下面式子中第ki項(xiàng)的指數(shù)一直到無窮）

??? 2.構(gòu)造母函數(shù)：G(x)=(1++…)(1+++…)…(1+++…)??????? （一）

??????????????????????????????? =a0 + a1*x + a2*?+ a3*?+....+ akk*???? (設(shè)kk=k1·p1+k2·p2+…kn·pn)? （二）

????????????????? G(x)含義： ak 為屬性值和為k的組合方法數(shù)。

母函數(shù)利用的思想：

??? 1.把組合問題的加法法則和冪級(jí)數(shù)的乘冪對(duì)應(yīng)起來。

??? 2.把離散數(shù)列和冪級(jí)數(shù)對(duì)應(yīng)起來，把離散數(shù)列間的相互結(jié)合關(guān)系對(duì)應(yīng)成為冪級(jí)數(shù)間的運(yùn)算關(guān)系，最后由冪級(jí)數(shù)形式來

?????? 確定離散數(shù)列的構(gòu)造。

代碼實(shí)現(xiàn)：

??? 求G(x)時(shí)一項(xiàng)一項(xiàng)累乘。先令G=1=(1+0*x+0*+…0*),再令G=G*(1++…)得到形式(二)的式子…最后令G=G*(1+++…)。

模板：

const int MAX_N = 10000; int a[MAX_N]; // 保存函數(shù)的各項(xiàng)系數(shù) int b[MAX_N]; // 中間量， 保存每一次的情況 int NumMin[MAX_N]; //每種最少數(shù)量 int NumMax[MAX_N]; //每種最多數(shù)量 int Val[MAX_N]; //每種的權(quán)重 int N; // 種數(shù) int P; // 價(jià)值上限（即目標(biāo)）； memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); a[0] = 1; for (int i = 1; i <= N; i++) { // 循環(huán)每種函數(shù)（1 + a1 x ^ p1 + a2 x ^ p2 + ......） // 一般情況下NumMin 都是 0// 如果每種情況都可以取無限個(gè) 就可以刪去 j <= NumMAX[i] for (int j = NumMin[i]; j <= NumMax[i] && j * Val[i] <= P; j++)// 兩個(gè)函數(shù)相乘 k 是被乘函數(shù)各項(xiàng)的指數(shù) for (int k = 0; k + j * Val[i] <= P; k++)// k + j * Val[i] 是結(jié)果函數(shù)的指數(shù) b[k + j * Val[i]] += a[k];for (int j = 0; j <= P; j++) {a[j] = b[j];b[j] = 0; } }

優(yōu)化：?

　　當(dāng)數(shù)據(jù)規(guī)模特別大時(shí)，可以用一個(gè) last 來標(biāo)記目前最大的指數(shù)，這樣只需要在 0 ~ last 上計(jì)算。

a[0] = 1; int last = 0; //因?yàn)橛?last ,所以無需初始化其他位 for (int i = 0; i < N; i++) {int lastnext = min(last + NumMax[i]* Val[i], P); memset(b, 0, sizeof(lastnext + 1));for (int j = NumMin[i]; j <= NumMax[i] && j * Val[i] <= lastnext; j++)for (int k = 0; k + j * Val[i] <= lastnext; k++)b[k + j * Val[i]] += a[k];for (int j = 0; j <= P; j++) {a[j] = b[j];b[j] = 0; }last = lastnext; }

// 這種方式應(yīng)該不適用于無限個(gè)的情況

例題：

?

Problem Description：

假設(shè)有x1個(gè)字母A， x2個(gè)字母B,..... x26個(gè)字母Z，同時(shí)假設(shè)字母A的價(jià)值為1，字母B的價(jià)值為2,..... 字母Z的價(jià)值為26。那么，對(duì)于給定的字母，可以找到多少價(jià)值<=50的單詞呢？單詞的價(jià)值就是組成一個(gè)單詞的所有字母的價(jià)值之和，比如，單詞ACM的價(jià)值是1+3+14=18，單詞HDU的價(jià)值是8+4+21=33。(組成的單詞與排列順序無關(guān)，比如ACM與CMA認(rèn)為是同一個(gè)單詞）。 Input 輸入首先是一個(gè)整數(shù)N，代表測(cè)試實(shí)例的個(gè)數(shù)。
然后包括N行數(shù)據(jù)，每行包括26個(gè)<=20的整數(shù)x1,x2,.....x26. Output 對(duì)于每個(gè)測(cè)試實(shí)例，請(qǐng)輸出能找到的總價(jià)值<=50的單詞數(shù),每個(gè)實(shí)例的輸出占一行。 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

?

題解：

1.建模：物品(字母)26種，每種數(shù)量x1,x2…x26，屬性值為1,2,3..26,求屬性值和<=50的組合方法數(shù)。

2.G(x)=(1++…)(1+++…)…(1++…)

#include<iostream> #include<cstdio> #include<cstring> using namespace std; long long a[60],b[60];int main() {int n;cin>>n;while(n--){memset(a,0,sizeof(a));memset(b,0,sizeof(b));a[0]=1;int x;for(int i=1;i<=26;i++){scanf("%d",&x);for(int j=0;j<=50;j++){for(int k=0;k<=x&&(j+k*i<=50);k++){b[j+k*i]+=a[j];}}for(int j=0;j<=50;j++){a[j]=b[j];b[j]=0;}}long long ans=0;for(int i=1;i<=50;i++)ans+=a[i];cout<<ans<<endl;} } AC Code

?

---

?

轉(zhuǎn)載于:https://www.cnblogs.com/astonc/p/9916159.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的3.1 普通型生成函数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。