**格式**： - 标题按一级、二级依次排列，有些地方如例题中的''指数型生成函数''写成标题，便于检索 - 公式两边接汉字请空格 - $\%x^{n}\to\bmod x^{n}$ **内容**： - 题目讲得太难了吧，从基础开始循序渐进，在定义和难题之间应该有一些基本应用及简单题 - 出现了一些 typo，如 ''HUD 排列组合'' ====== 生成函数 ====== 这几周比较忙，还有很多写得不详细的地方。\\ 本文的知识点和例题可能比较片面。\\ 参考了很多其他人写的，还没来得及写参考文献。 === 形式幂级数 === $$ A(x)=\sum_{i \ge 0}a_ix^i $$ 用$[x^n]A(x)$表示$A(x)$的$n$次项系数$a_n$。 实际运算时，通常只需要保留次数不超过$n-1$的项进行计算$(\%x^n)$ === 有标号和无标号 === 3个点的无标号简单无向图有4种 3个点的有标号简单无向图有8种 === 普通生成函数(OGF) === 数列$A_0,A_1,\dots$的普通生成函数定义为形式幂级数 $$ A(x)=\sum_{i \ge 0}A_i x^i $$ 一个例子： ​ 考虑 $A_i、B_i$为两个背包，如何合并这两个背包。 $$ C_k=\sum_{i+j=k}A_iB_j $$ ​ 对应于生成函数，则有 $$ C(x)=A(x)B(x) $$ ​ 一个容量为$a$的物品的完全背包 $$ \sum_{i \ge 0}x^{ai} $$ ​ 写成封闭形式 $$ \frac{1}{1-x^a} $$ === 指数生成函数(EGF) === 数列$A_0,A_1,\dots$的指数生成函数定义为形式幂级数 $$ A(x)=\sum_{i \ge 0}A_i \frac{x^i}{i!} $$ EGF常用来解决带标号问题。 从$k$个标号里选出$i$个标号给$A_i$中的$i$个元素，$k-i$个标号给$B_j$中的$j$个元素。这样相当于对$C_k$中的元素编号。则$C_k$中带标号方案数 $$ C_k=\sum_{i+j=k}\frac{k!}{i!(k-i)!}A_iB_j $$ $$ \frac{C_k}{k!}=\sum_{i+j=k}\frac{A_i}{i!}\frac{B_j}{j!} $$ 对应于生成函数，则有 $$ C(x)=A(x)B(x) $$ === 指数与对数函数 === $$ ln(1-A(x))=-\sum_{i \ge 1}\frac{A(x)^i}{i} \\ exp(A(x))=\sum_{i \ge 0}\frac{A(x)^i}{i!} $$ === 例题 === 鏼论文中的一道例题：完全背包计数 若干种不同的物品，体积为$i$的物品有$a_i$种，每种物品有无限个。求装满体积为$n$的背包的方案数。$(a_i,n \le10^5)$ 体积为$i$的物品的生成函数 $$ \frac{1}{1-x^i} $$ 将所有物品的生成函数相乘 $$ F(x)=\prod_{i=1}^{n}\left(\frac{1}{1-x^i}\right)^{a_i} $$ $$ lnF(x)=\sum_{i=1}^{n}-a_i ln(1-x^i) $$ 对于右边来说，将 $x^i$代入$ln(1-x)$的展开式得 $$ lnF(x)=\sum_{i=1}^{n}a_i\sum_{j\ge1}\frac{x^{ij}}{j} \\ =\sum_{T \ge 0} \sum_{i|T} \frac{a_i}{T}ix^T $$ 因为$T$最多到$n$，根据调和级数，我们可以在 $O(nlogn)$内求出$lnF(x)$，然后再多项式$exp$一下，可以得到$F(x)$。 [[https://www.luogu.com.cn/problem/P3784|SDOI2017遗忘的集合]] 给定一个集合的完全背包$f(1)\sim f(n)$，求这个集合。集合中元素最大为$n$。 用$a_i$表示$i$这个元素是否为集合中的元素。 则整个集合中元素的生成函数 $$ F(x)=\prod_{i=1}^{n}\left(\frac{1}{1-x^i}\right)^{a_i} $$ 与上一题同样可得 $$ lnF(x)=\sum_{i=1}^{n}a_i\sum_{j\ge1}\frac{x^{ij}}{j} \\ =\sum_{T \ge 0} \sum_{i|T} \frac{a_i}{T}ix^T $$ $$ n[x^n]lnF(x)=\sum_{i|n}ia_i $$ 莫比乌斯反演一下就可以得到 $a_i$ [[https://www.luogu.com.cn/problem/P4389|付公主的背包]] 和完全背包计数很像 [[https://www.luogu.com.cn/problem/P5408|第一类斯特林数·行]] $S_n^m$表示把n个不同的元素构成m个圆排列的方案数（不能有空的环） $S_n(x)$表示第n行斯特林数的生成函数 $$ S_n(x)=\sum_{i=0}^{\infty}S_n^i x^i $$ $$ S_n^i=S_{n-1}^{i-1}+(n-1)S_{n-1}^{i} $$ $$ S_n(x)=xS_{n-1}(x)+(n-1)S_{n-1}(x) \\ =(x+n-1)S_{n-1}(x) \\ =\prod_{i=0}^{n-1}(x+i) $$ 可以分治FFT，在$O(nlog^2n)$的复杂度内求出，也有$O(nlogn)$的求法。 [[https://www.luogu.com.cn/problem/P5409|第一类斯特林数·列]] 大概是采用了**Zory**的做法 考虑n个有标号元素组成的环的方案数$(n-1)!$ 考虑取一个带标号环，可以表示为EGF $$ \sum_{i \ge 1}(i-1)!\frac{x^i}{i!} $$ 依次取m个环，方案数$/m!$ $$ F(x)=\frac{1}{m!}\left(\sum_{i \ge 1}(i-1)!\frac{x^i}{i!}\right)^m $$ [[https://www.luogu.com.cn/problem/P5395|第二类斯特林数·行]] $S_n^m$表示把n个不同的元素分到m个相同的集合中（不能有空集）的方案数 把m个集合看成不同的，枚举几个集合没放，得到容斥的式子后$/m!$ $$ S_n^m=\frac{1}{m!}\sum_{i=0}^{m}C_{m}^{i}(-1)^i(m-i)^n \\ =\sum_{i=0}^{m}\frac{(-1)^i(m-i)^n}{i!(m-i)!} =\sum_{i=0}^{m} \frac{(-1)^i}{i!} \frac{(m-i)^n}{(m-i)!} $$ 可以让$\sum_{i=0}^{m} \frac{(-1)^i}{i!}$和$\sum_{i=0}^{m}\frac{i^n}{i!}$做卷积 [[https://www.luogu.com.cn/problem/P5396|第二类斯特林数·列]] 大概是采用了**Great_Influence**的做法 $S_m(x)$表示第m列斯特林数的生成函数 $$ S_m(x)=\sum_{i=0}^{\infty}S_i^m x^i $$ $$ S_i^m=S_{i-1}^{m-1}+mS_{i-1}^{m} $$ 可以得到 $$ S_m(x)=xS_{m-1}(x)+xmS_{m}(x) $$ $$ S_m(x)=\frac{x}{1-mx}S_{m-1}(x) \\ =\frac{x^m}{\prod_{i=1}^{m}(1-ix)} $$ $\prod_{i=1}^{m}(1-ix)$可以分治FFT，在$O(nlog^2n)$的复杂度内求出，也有$O(nlogn)$的求法。 2020牛客寒假算法基础集训营4 [[https://ac.nowcoder.com/acm/contest/3005/J|二维跑步]] 向左有2种跑法，向右有3种跑法，也可以原地不动。 如果用$F[i][j]$表示跑了i步，当前在位置j的方案数 $$ F[i][j]=3F[i-1][j-1]+F[i-1][j]+2F[i-1][j+1] $$ 令生成函数 $$ F_i(x)=\sum F[i][j]x^j $$ 那么有 $$ F_n(x)=3xF_{n-1}(x)+F_{n-1}(x)+\frac{2}{x}F_{n-1}(x) \\ =(3x+1+\frac{2}{x})^n $$ 为了更方便计算 $$ x^nF_n(x)=(3x^2+x+2)^n $$ 对于右边，可以先求所有单位根$w$的$(3w^2+w+2)^n$然后插值得到$$x^nF_n(x)$$ 复杂度$O(nlogn)$，标算用了更快的做法。 指数生成函数 [[http://poj.org/problem?id=3734|POJ Blocks]] 用RBGY四种颜色涂满长度为n的序列，RG这两种颜色需要出现偶数次。 这是一个带标号组合问题，标号可以理解为颜色的位置。 考虑R，涂满长度为 0~n的序列的方案数为 1，0，1，0，1，0，1，0，1… 那么R的指数生成函数 $$ \sum_{i \ge 0} \frac{x^{2i}}{2i!}=\frac{e^x+e^{-x}}{2} $$ 考虑B，涂满长度为 0~n的序列的方案数为 1，1，1，1，1… 那么R的指数生成函数 $$ \sum_{i \ge 0} \frac{x^{i}}{i!}=e^x $$ 将四种颜色的生成函数乘起来 $$ F(x)=\left(\frac{e^x+e^{-x}}{2}\right)^2e^{2x}=\frac{1}{4}(e^{2x}+1)^2 \\ =\frac{1}{4}(e^{4x}+2e^{2x}+1) \\ =\frac{1}{4}+\frac{1}{4}\sum_{i \ge 0}\frac{4^i+2^{i+1}}{i!}x^i $$ $n \ge 1$时， $n![x^n]F(x)=4^{n-1}+2^{n-1}$可以用快速幂求出。 或者 $f[i][j](0 \le j \le 3)$表示dp到第i个位置，RG分别放了奇数次/偶数次的方案数，可以矩阵快速幂优化。 [[http://acm.hdu.edu.cn/showproblem.php?pid=1521|HUD 排列组合]] 有n种物品，并且知道每种物品的数量 $a_i$ 。要求从中选出m件物品的排列数。例如有两种物品A,B，并且数量都是1，从中选2件物品，则排列有“AB”,“BA”两种。$(1 \le m,n \le10)$ 这是一个带标号组合问题，标号可以理解为某个物品的位置。 第i个物品的EGF $$ \sum_{i=0}^{a_i}\frac{x^i}{i!} $$ 将n个物品的EGF乘起来得$F(x)$ ，则答案为 $$ m! [x^m]F(x) $$ ==== luoguP4841 [集训队作业2013]城市规划 ==== === 题意 === 求n个点的简单有标号无向连通图数目模$1004535809$。 === 题解 === 设$f(n)$为点数为$n$的**无向连通图**的数量，$g(n)$为点数为$n$的**无向图**的数量。\\ 那么有 $$g(n)=\sum_{i=1}^n(_{i-1}^{n-1})f(i)g(n-i)$$ ，可以看成枚举一号节点所在连通块大小。\\ 代入$g(n)=2^{(_2^n)}$， $$2^{(_2^n)}=\sum_{i=1}^n(_{i-1}^{n-1})f(i)2^{(_{2}^{n-i})}$$ $$\frac{2^{(_2^n)}}{(n-1)!}=\sum_{i=1}^n\frac{f(i)}{(i-1)!}\frac{2^{(_{2}^{n-i})}}{(n-i)!}$$ 这是一个卷积，于是定义 $$F(x)=\sum_{n=1}^{+\infty}\frac{f(n)}{(n-1)!}x^n$$ $$G(x)=\sum_{n=0}^{+\infty}\frac{2^{(_2^n)}}{n!}x^n$$ $$H(x)=\sum_{n=1}^{+\infty}\frac{2^{(_2^n)}}{(n-1)!}x^n$$ 则 $$F=H*G^{-1}\quad(mod\;x^{n+1})$$ ==== CF438E The Child and Binary Tree ==== === 题意 === 一棵树的权值为其点权和。点权在正整数集合$\{c_1,...,c_n\}$中，求不同的有根二叉树的权值和模$998244353$。 === 题解 === 设$f_i$表示点权和为$i$的二叉树个数，$g_i$表示权值$i$是否包含在$\{c_1,...,c_n\}$中。\\ $f_i$可由枚举根的点权和左右子树得到 $$f_0=1$$ $$f_n=\sum_{i=1}^ng_i\sum_{j=1}^{n-i}f_jf_{n-i-j}\quad (n>0)$$ 令$F$表示$f$的生成函数，$G$表示$g$的生成函数，那么 $$F=G*F^2+1$$ 解得 $$F=\frac{1\pm\sqrt{1-4G}}{2G}$$ 讨论 $$取正号 \quad \lim_{x \to 0}F(x)=\infty \quad (舍去)$$ $$取负号 \quad \lim_{x \to 0}F(x)=1 \quad (满足)$$ 于是得 $$F=\frac{1-\sqrt{1-4G}}{2G}$$ $$F=\frac{2}{1+\sqrt{1-4G}}$$ ==== luoguP4451 [国家集训队]整数的lqp拆分 ==== === 题意 === $F_n$表示斐波那契数列第$n$项。对给定$n$，拆分指$m>0,a_1,a_2,...,a_m>0,且a_1+a_2+...+a_m=n$的有序集合，拆分的权值为$F_{a_1}F_{a_2} ... F_{a_m}$。求所有拆分权值之和模$1000000007$。 === 题解 === 斐波那契数列的生成函数为 $$F(x)=\frac{x}{1-x-x^2}$$ 拆分为$k$个数，生成函数为$F(x)^k$。于是答案的生成函数为 $$G(x)=\sum_{i=0}^\infty F(x)^i$$ $$=\frac{1}{1-F(x)}=\frac{1-x-x^2}{1-2x-x^2}$$ 分母$\frac{1}{1-2x-x^2}$写成递推式 $$a_n=2a_{n-1}+a_{n-2}$$ 乘上分子 $$ans=a_n-a_{n-1}-a_{n-2}=a_{n-1}$$ 解递推特征方程，得 $$x_1=-\sqrt{2}+1,\;x_2=\sqrt{2}+1$$ 设通项公式为 $$a_n=c_1(-\sqrt{2}+1)^n+c_2(\sqrt{2}+1)^n$$ 代入$n=0,n=1$，解得 $$c_1=\frac{\sqrt{2}-1}{2\sqrt{2}},\;c_2=\frac{\sqrt{2}+1}{2\sqrt{2}}$$ $\sqrt{2}$在模$10^9+7$下有二次剩余$(59713600)$，所以最终答案 $$a_n\equiv485071604×940286408^n+514928404×59713601^n\;(mod10^9+7)$$