母函数又名生成函数
是一种重要的数论函数
多用于求解组合数问题、递推问题
母函数包括很多种
例如
普通母函数、指数母函数、L级数、贝尔级数和狄利克雷级数
而普通母函数
的理解则是
把组合问题的加法法则和幂级数的的乘幂的相加对应起来
总之母函数的思想就是
把离散数列和幂级数一一对应起来，把离散数列间的相互结合关系对应成为幂级数间的运算关系
最后由幂级数形式来确定离散数列的构造
从经典的例子开始
题目：有1克、2克、3克、4克的砝码各一 枚，能称出哪几种重量？每种重量各有几种可能方案？
若是使用穷举法
那么原题的复杂度可以达到O(n^4)
当砝码数量达到了m个时
原题的复杂度就成了O(n^m)
若我们使用母函数
复杂度则可以降到O(n^3)
穷举的细节简单模拟一下
1 先假设使用一个1g的砝码，然后再假设在此情况下，使用2g的砝码，在此基础上， 2 再假设使用一个3g的，再假设使用一个4g的，这就是1中情况， 3 显然，这种方案称出的重量为10g，然后改变上面的一个假设条件， 4 比如假设没有使用4g的，只是用了1g、2g、3g，显然这种方案称出的是6g， 5 以此类推，将所有的可能列举出来后即可得到全部的方案，1g的砝码有两种情况， 6 使用还是不使用，其他的砝码也一样，每一种1g砝码的状态都可以有两种砝码状态， 7 以此类推总共就有2*2*2*2=16中方案，当然其中包含一种一个砝码也没有的0g方案。
最后穷尽结果为
1g、2g、8g、9g、10g各有一种方案
3g、4g、5g、6g、7g各有两种
总共十五种
嗯……
我接下来这段也不知道该怎么讲
所以引用一下别人的
（x0+x1）* （x0+x2） * （x0+x3）* （x0+x4）
=x0 + x1 + x2 + 2x3 + 2x4 + 2x5 + 2x6 + 2x7 + x8+ x9 + x10
和我们的结果一样
如果将每砝码数量换成无限的
那么
之前的式子大概可以写成
（x0 +x1 + x2 + x3 + x4 + x5 + …… ）*（x0 + x2 + x4 + x6 + x8+ x10 + ……）
第一个多项式
表示1g砝码每种数目都只有一种方案来组成
同理第二者用来表明
2的倍数的砝码只有一种方案来表示
多项式乘法不多bb，O(n^2)复杂度，再叠加一个循环
达到O(n^3)
足够优化了吧
这种复杂度遇到正常一点的题
直接就当场裂开
所以你还需要学
其他的东西来辅助 谁辅助谁呀
欸比如你需要
FFT来优化多项式乘法
于是复杂度到了O(nm log m)
就这？还是不行
所以必要时需要
另辟蹊径把所有生成函数取ln
然后exp
所以为了这两个辅助品
你还需要学
有关复数的一些性质
单位根的性质
多项式卷积
这还仅是FFT
exp这个就直接裂开
我根本不会，只是在一篇题解上见到过
-end-
原文：https://www.cnblogs.com/-Iris-/p/12944101.html