每次做母函数的题都会忘记，于是我学习了一下母函数，写了一篇博客，希望自己能记住。本文有代码模版。mark一下。
介绍
在组合数学中，母函数，又叫生成函数，是一种形式幂级数。每一项的系数可以提供关于这个项的信息。使用母函数解决问题的方法就是母函数法。
母函数有很多种，普通母函数、指数母函数、L级数、贝尔级数、狄利克雷级数。根据一个序列不同的性质，或是需要得到的信息，要选择以上不同的母函数进行套用。
母函数方法的思想就是将数列间的相加关系与幂级数间的乘幂运算对应起来。
定义
序列$a_0, a_1, a_2, a_3, …$构造一个函数
$G(x)=a_0+a_1x+a_2x^2+…$
称$G(x)$为$a_0, a_1, a_2, a_3, …$序列的母函数
普通母函数
该类母函数比较常用，可以用于解决整数拆分，组合数量问题。
一次多项式乘法母函数
一次是指每一个多项式的最高次是1
$\quad(1+a_1x)(1+a_2x)…(1+a_nx)$
$=1+(a_1+a_2+…+a_n)x+(a_1a_2+a_1a_3+…+a_{n-1}a_n)x^2+…+a_1a_2…a_nx^n$
$x$的系数是$a_1, a_2, … a_n$的$1$个组合的和
$x^2$的系数是$a_1, a_2, … a_n$的$2$个组合的和
…
$x^n$的系数是$a_1, a_2, … a_n$的$n$个组合的和
杨辉三角母函数
$\quad(1+x)^n$
$=C_n^0x^0+C_n^1x^1+C_n^2x^2+…+C_n^nx^n$
$=1+C_n^1x+C_n^2x^2+…+C_n^nx^n$
高次有限项多项式乘法母函数
高次指每个多项式的最高次大于1，有限项指的是每个多项式的项数是有限的
比如有这样一个问题。有1元2张、5元4张、10元1张、20元3张，问可以组合出多少种面额，每种面额的组合方式数量是多少
问题可以转化为如下的多项式
$\quad(1\times x^{0 \times 1}+1\times x^{1 \times 1}+1\times x^{2 \times 1})(1\times x^{0 \times 5}+1\times x^{1 \times 5}+1\times x^{2 \times 5}+1\times x^{3 \times 5}+1\times x^{4 \times 5})\cdot$
$\quad(1\times x^{0 \times 10}+1\times x^{1 \times 10})(1\times x^{0 \times 20}+1\times x^{1 \times 20}+1\times x^{2 \times 20}+1\times x^{3 \times 20})$
$=(1+x+x^2)(1+x^5+x^{10}+x^{15}+x^{20})(1+x^{10})(1+x^{20}+x^{40}+x^{60})$
一共四个多项式相乘，分别代表1元、5元、10元、20元的选择情况。
用第一个多项式举例。多项式中每一项的指数代表组合情况，即
$x^{0 \times 1}$代表取0个1元，系数1代表组合种数有1种
$x^{1 \times 1}$代表取1个1元，系数1代表组合种数有1种
$x^{2 \times 1}$代表取2个1元，系数1代表组合种数有1种
因为1元有两张，所以到这里就结束了，这个多项式的项是有限项。
将数列间的相加关系与幂级数间的乘幂运算对应起来在这里的体现就是：在计算这个多项式乘积的时候，x的幂相乘运算就是指数相加，而这个指数相加正好对应了数列间的加法运算。而相乘之后得到的多项式的各项系数就是组合方式数。
高次无限项多项式乘法母函数
高次指每个多项式的最高次大于1，无限项指的是每个多项式的项数是无限的
考虑这样一个问题，有1,2,3克砝码无限个。求某一质量的方案数。
类比高次有限项多项式乘法母函数，直接写出多项式乘积：
$(1+x+x^2+x^3+…)(1+x^2+x^4+x^6+…)(1+x^3+x^6+x^9+…)$
计算这个多项式的和，质量为$n$的方案数就是$x^n$的系数
考虑这样一个题，有120个数，每个数的个数不限。求组成某个数的方案数。$4=3+1$与$4=1+3$属于同一种方案
给出模版代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
using namespace std;
int n;
int num1[125];
int num2[125];
int main(){
memset(num1, 0, sizeof num1);
memset(num2, 0, sizeof num2);
for(int i = 0; i < 125; i++){
num1[i] = 1;
}
for(int i = 2; i <= 120; i++){
for(int j = 0; j <= 120; j++){
for (int k = 0; k+j <= 120; k += i){
num2[k+j] += num1[j];
}
}
for(int j = 0; j <= 120; j++){
num1[j] = num2[j];
num2[j] = 0;
}
}
while(~scanf("%d", &n)){
printf("%d\n", num1[n]);
}
}
解释一下代码，这个代码其实就是在模拟多项式乘法的过程。
$(1+x^1+x^2+…+x^{120})(1+x^2+x^4+x^6+…+x^{120})…(1+x^{120})$
一共120个多项式相乘。
num1在每轮循环结束后存储的都是第一个多项式的系数。
num2是一个中转数组，用来暂存过程中的新的多项式的系数。
每次循环结束，num2中的值都要倒换到num1中。
第13-15行就是第一轮，是$(1+x^1+x^2+…+x^{120})$多项式的各项系数。这是初始化num1，num2数组
第16行是对120个多项式进行循环。每轮乘一个多项式进去。第i轮乘的是各项系数是i的倍数的多项式。也就是说第2轮乘的是$(1+x^2+x^4+…)$，第三轮乘的是$(1+x^3+x^6+…)$，第i轮乘的是$(1+x^i+x^{2i}+…)$。第i轮结束后，num1中的系数是前i个多项式的乘积多项式的系数。即$(1+x^1+x^2+…)(1+x^2+x^4+…)…(1+x^i+x^{2i}+…)$的结果的系数
第17行的j是对第i-1轮得到的乘积多项式的各项进行循环。即，$(1+x^1+x^2+…)(1+x^2+x^4+…)…(1+x^{i-1}+x^{2i-2}+…)$的结果中的各项
第18行的k是对第i个多项式，即$(1+x^i+x^{2i}+…)$的各项进行循环。将这个多项式和前i-1个多项式的乘积相乘，得到前i个多项式的乘积。k的增量是i
第19行，num2存的是相乘运算的过程中的中间结果系数，num1存的是前i-1个多项式的乘积的系数。因为第i个多项式中的每项的系数都是1，所以num2[k+j]直接加了num1[j]，其实是1*num1[j]。
第22-24行，就是将num2的结果跟num1的结果倒腾一下。
注意，有的题，可能要求比如，某个值最少用多少，最多用多少这种情况。这个时候，就是k不从0开始了，并且k+=i的次数有限制。需要灵活变通