大家好，又见面了，我是全栈君。
在数学中，某个序列的母函数(Generating function，又称生成函数)是一种形式幂级数。其每一项的系数能够提供关于这个序列的信息。使用母函数解决这个问题的方法称为母函数方法。
我们首先来看下这个多项式乘法：
由此能够看出:
1.x的系数是a1,a2,…an 的单个组合的全体。 2. x^2的系数是a1,a2,…a2的两个组合的全体。 ……… n. x^n的系数是a1,a2,….an的n个组合的全体（仅仅有1个）。
令a1,a2…an都等于1,由此可得
这里先给出两句话。不懂的能够等看完这篇文章再回过头来看：
1.“把组合问题的加法法则和幂级数的乘幂相应起来” 2.“母函数的思想非常easy — 就是把离散数列和幂级数一 一相应起来，把离散数列间的相互结合关系相应成为幂级数间的运算关系。最后由幂级数形式来确定离散数列的构造. ”
母函数的定义
对于序列a0。a1，a2，…构造一函数：
第一种：
有1克、2克、3克、4克的砝码各一枚，能称出哪几种重量？每种重量各有几种可能方案？
考虑用母函数来解决问题：
我们如果x表示砝码。x的指数表示砝码的重量。这样：
1个1克的砝码能够用函数1 1*x^1表示， 1个2克的砝码能够用函数1 1*x^2表示。 1个3克的砝码能够用函数1 1*x^3表示， 1个4克的砝码能够用函数1 1*x^4表示。
上面这四个式子懂吗？
我们拿1 x^2来说，前面已经说过，x表示砝码，x的指数表示砝码的重量！初始状态时，这里就是一个质量为2的砝码。
那么前面的1表示什么？依照上面的理解，1事实上应该写为：1*x^0,即1代表重量为2的砝码没有取。
所以这里1 1*x^2 = 1*x^0 1*x^2，即表示2克的砝码有两种状态。不取或取，不取则为1*x^0。取则为1*x^2
接着讨论上面的1 x^2。这里x前面的系数有什么意义？
这里的系数表示状态数(方案数)
1 x^2。也就是1*x^0 1*x^2，也就是上面说的不取2克砝码。此时有1种状态；或者取2克砝码，此时也有1种状态。(分析！)
所以，前面说的那句话的意义大家能够理解了吧？
几种砝码的组合能够称重的情况，能够用以上几个函数的乘积表示：
(1 x)(1 x^2)(1 x^3)(1 x^4)
=(1 x x^2 x^4)(1 x^3 ^4 x^7)
=1 x x^2 2*x^3 2*x^4 2*x^5 2*x^6 2*x^7 x^8 x^9 x^10
从上面的函数知道：可称出从1克到10克，系数便是方案数。（！
。！经典！！。）
比如右端有2^x^5 项，即称出5克的方案有2种：5=3 2=4 1。相同。6=1 2 3=4 2；10=1 2 3 4。
故称出6克的方案数有2种。称出10克的方案数有1种 。
接着上面，接下来是另外一种情况：
另外一种：
求用1分、2分、3分的邮票贴出不同数值的方案数：
大家把这样的情况和第一种比較有何差别？第一种每种是一个，而这里每种是无限的。
以展开后的x^4为例。其系数为4。即4拆分成1、2、3之和的拆分方案数为4；
即 ：4=1 1 1 1=1 1 2=1 3=2 2
这里再引出两个概念”整数拆分“和”拆分数“：
所谓整数拆分即把整数分解成若干整数的和（相当于把n个无差别的球放到n个无标志的盒子。盒子同意空。也同意放多于一个球）。
整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。
代码模板：
代码语言：javascript复制#include <iostream>
using namespace std;
const int _max = 10001;
// c1是保存各项质量砝码能够组合的数目
// c2是中间量。保存没一次的情况
int c1[_max], c2[_max];
int main()
{
int nNum;
int i, j, k;
while(cin >> nNum)
{
for(i=0; i<=nNum; i) // ---- ①
{
c1[i] = 1;
c2[i] = 0;
}
for(i=2; i<=nNum; i) // ----- ②
{
for(j=0; j<=nNum; j) // ----- ③
for(k=0; k j<=nNum; k =i) // ---- ④
{
c2[j k] = c1[j];
}
for(j=0; j<=nNum; j) // ---- ⑤
{
c1[j] = c2[j];
c2[j] = 0;
}
}
cout << c1[nNum] << endl;
}
return 0;
} 我们来解释下上面标志的各个地方：(***********！！
！重点！
！！***********)
① 、首先对c1初始化，由第一个表达式(1 x x^2 ..x^n)初始化，把质量从0到n的全部砝码都初始化为1. ② 、 i从2到n遍历。这里i就是指第i个表达式。上面给出的另外一种母函数关系式里。每个括号括起来的就是一个表达式。 ③、j 从0到n遍历，这里j就是(前面i個表达式累乘的表达式)里第j个变量，(这里感谢一下seagg朋友给我指出的错误。大家能够看下留言处的讨论)。如(1 x)(1 x^2)(1 x^3)，j先指示的是1和x的系数，i=2运行完之后变为 （1 x x^2 x^3）(1 x^3)。这时候j应该指示的是合并后的第一个括号的四个变量的系数。 ④ 、 k表示的是第j个指数，所以k每次增i（由于第i个表达式的增量是i）。 ⑤ 、把c2的值赋给c1,而把c2初始化为0。由于c2每次是从一个表达式中開始的。
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/115889.html原文链接：https://javaforall.cn
