蒟蒻听了yxc老师的 算法基础课 后，写了一个关于数学知识的笔记，以图像形式分享给大家。

update ：

1. 2020年3月15日 22:07:06 —— 增加了母函数（在最下面）

母函数：

对于一个问题，方案数为$P_0,P_1,P_2,\dots,P_n$（该序列记成${P_n}$）
则该数列的生成函数为：$f(x)=P_0x^0+P_1x^1+P_2x^2+\dots+P_nx^n$（把每一项看成系数）
也可化成：$\quad\quad\quad\quad\quad f(x)=(1+x+x^2+x^3+\dots)(1+x^2+x^4+\dots)(1+x^3+x^6+\dots)\dots$
重点：选第二个式子括号里的项表示$P_n$，在第$k$个括号选第$i$个项，表示数字$k$选择$i - 1$个
这样就可以构造出母函数的两种情况了。
把第二个式子化简可得：
$\quad f(x)=(1+x+x^2+x^3+\dots)(1+x^2+x^4+\dots)(1+x^3+x^6+\dots)\dots (0\leq x<1)$
$=\frac{1}{1-x}\frac{1}{1-x^2}\frac{1}{1-x^3}\dots$
$=\frac{1}{(1-x)(1-x^2)\dots}$
$=\frac{1}{1-x-x^2+x^5+x^7-x^{12}\dots}$（指数规律：$\frac{3k^2\pm k}{2}$）
$∴f(x)(1-x-x^2+x^5+x^7-x^{12}\dots)=1$
综上可得：
$(P_0x^0+P_1x^1+P_2x^2+\dots+P_nx^n)(1-x-x^2+x^5+x^7-x^{12}\dots)=1$
$x^n$的系数：
$P_n-P_{n-1}-P_{n-2}+P_{n-5}+P_{n-7}\dots=0$
$∴P_n=P_{n-1}+P_{n-2}-P_{n-5}-P_{n-7}\dots$（减数规律：$\frac{3k^2\pm k}{2}$）（项数：$O(\sqrt {n})$）
算法总时间复杂度：$O(n\sqrt{n})$