生成函数理论 5
基本应用
例 1
依照题意可列出 10 个条件的生成函数 $f_i(x)$，将它们相乘再化简即可。
- $f_1(x)=(1+x^6+x^{12}+\cdots)=\frac{1}{1-x^6}$
- $f_2(x)=(1+x+x^2+\cdots+x^9)=\frac{1-x^{10}}{1-x}$
- $f_3(x)=(1+x+x^2+\cdots+x^5)=\frac{1-x^6}{1-x}$
- $f_4(x)=(1+x^4+x^8+\cdots)=\frac{1}{1-x^4}$
- $f_5(x)=(1+x+x^2+\cdots+x^7)=\frac{1-x^8}{1-x}$
- $f_6(x)=(1+x^2+x^4+\cdots)=\frac{1}{1-x^2}$
- $f_7(x)=(1+x)=\frac{1-x^2}{1-x}$
- $f_8(x)=(1+x^8+x^{16}+\cdots)=\frac{1}{1-x^8}$
- $f_9(x)=(1+x^{10}+x^{20}+\cdots)=\frac{1}{1-x^{10}}$
- $f_{10}(x)=(1+x+x^2+x^3)=\frac{1-x^4}{1-x}$
$\displaystyle f(x)=\prod_{i=1}^{10}f_i(x)=\frac{1}{(1-x)^5}=\sum_{n=0}^{\infty}\binom{n+4}{n}x^n$
$\displaystyle ans_n=\binom{n+4}{4}=\frac{(n+4)(n+3)(n+2)(n+1)}{24}$
由于 $10^{100000}\le n<10^{100001}$，需要用高精度，正解是用 NTT，用 Python 会 TLE，但是竟然可以用 Ruby AC。
Ruby 代码：
C++ 代码：
例 2 （Bell 数）
令 $B_n$ 表示 $[n]$ （$n$ 元集合）所有划分的个数，试找到计算 $B_n$ 的公式。
讨论 $[n]$ 的划分中包含元素 $n$ 的那个子集，设其含有 $k$ （$1\le k\le n$）个元素，则剩余的 $k-1$ 个元素是从 $[n-1]$ 中选取的。而剩余的那些子集为 $n-k$ 个元素的一个划分，所以 $$ B_n=\sum_{k=1}^{n}\binom{n-1}{k-1}B_{n-k},~~~~n\ge 1. $$ 初始值为 $B_0=1,B_1=1$。令 $\displaystyle B(x)=\sum_{n\ge 0}\frac{B_n}{n!}x^n$，两边求导数，得到 $$ \begin{align} \frac{dB(x)}{dx}&=\sum_{n=1}^{\infty}\frac{B_n}{(n-1)!}x^{n-1}\\ &=\sum_{n=1}^{\infty}\frac{1}{(n-1)!}\left(\sum_{k=1}^{n}\binom{n-1}{k-1}B_{n-k}\right)x^{n-1}\\ &=\sum_{n=1}^{\infty}\sum_{k=1}^{n}\frac{x^{k-1}}{(k-1)!}\frac{B_{n-k}x^{n-k}}{(n-k)!}\\ &=\sum_{k=1}^{\infty}\frac{x^{k-1}}{(k-1)!}\sum_{n\ge k}\frac{B_{n-k}x^{n-k}}{(n-k)!}\\ &=\sum_{k=1}^{\infty}\frac{x^{k-1}}{(k-1)!}\sum_{i\ge 0}\frac{B_ix^i}{i!}~~(i=n-k)\\ &=e^xB(x). \end{align} $$ 解微分方程 $\displaystyle \frac{dB(x)}{dx}=e^xB(x)$，可得 $$ B(x)=Ce^{e^x}, $$ 其中 $C$ 为待定常数。由初始条件 $B(0)=1$ 得到 $C=e^{-1}$，即 $$ B(x)=e^{e^x-1}, $$ 从而 $$ \begin{align} B(x)&=\frac{1}{e}\sum_{k=0}^{\infty}\frac{(e^x)^k}{k!}=\frac{1}{e}\sum_{k=0}^{\infty}\frac{1}{k!}\sum_{n=0}^{\infty}\frac{k^nx^n}{n!}\\ &=\frac{1}{e}\sum_{n=0}^{\infty}\left(\sum_{k=0}^{\infty}\frac{k^n}{k!}\right)\frac{x^n}{n!}. \end{align} $$ 因此 $$ B_n=\frac{1}{e}\sum_{k=0}^{\infty}\frac{k^n}{k!}. $$ $\Box$
例 3
题意
题解
Fibonacci 数的生成函数是这个（基础知识）： $$ F(x)=\frac{x}{1-x-x^2} $$ 当拆分为恰好 $k$ 个数时，答案的生成函数是 $F(x)^k$，那么答案的生成函数即为 $$ \begin{align} G(x)&=\sum_{i=0}^{\infty}F(x)^i\\ &=\frac{1}{1-F(x)}\\ &=\frac{1-x-x^2}{1-2x-x^2}\\ &=1+\frac{x}{1-2x-x^2}\\ &=1+\frac{\sqrt 2}{4}(\frac{1}{1-(1+\sqrt 2)x}-\frac{1}{1-(1-\sqrt 2)x})\\ &=1+\frac{\sqrt 2}{4}\sum_{n=0}^{\infty}[(1+\sqrt 2)^n-(1-\sqrt 2)^n]x^n \end{align} $$ 所以通项公式为 $$ a_n\equiv \frac{\sqrt 2}{4}[(1+\sqrt 2)^n-(1-\sqrt 2)^n]\pmod{1e9+7} $$ 需要用二次剩余解出 $x^2\equiv 2\pmod{1e9+7}$
评价
对于理解生成函数和公式推导有一定的帮助
代码
拓展
令 $a_n$ 表示在一个 n-集合上完成某个任务的方法数，$a_0=0$。对于 $n\ge 1$，令 $b_n$ 表示将集合 $[n]$ 划分成任意的连续、非空区间段，然后在这些非空区间段上完成前面任务的方法数，$b_0=1$。设 $\{a_n\}_{n=0}^{\infty}$ 和 $\{b_n\}_{n=0}^{\infty}$ 的普通生成函数分别为 $f(x)$ 和 $g(x)$，则对任意固定的正整数 $i$，将 $[n]$ 划分成 $i$ 个非空子区间时，所对应的方法数的普通生成函数为 $f^i(x)$，且有 $$ g(x)=\frac{1}{1-f(x)}. $$
例 4
题意
求出 $n$ 个点的简单（无重边无自环）有标号无向连通图数目。
题解
令 $\{a_n\}_{n=0}^{\infty}$ 为答案，$\{b_n\}_{n=0}^{\infty}$ 为 $n$ 个点的无向图的数目，显然 $b_n=2^{\binom{n}{2}}$，设 $1$ 号点所在连通块大小为 $k$，则有 $$ \begin{align} b_n&=\sum_{k=1}^{n}\binom{n-1}{k-1}a_kb_{n-k}\\ &=\sum_{k=0}^{n-1}\binom{n-1}{k}a_{k+1}b_{n-k-1}\\ b_{n+1}&=\sum_{k=0}^{n}\binom{n}{k}a_{k+1}b_{n-k} \end{align} $$ 令 $c_k=a_{k+1}$，$A(x),B(x),C(x)$ 分别为 $\{a_n\}_{n=0}^{\infty},\{b_n\}_{n=0}^{\infty},\{c_n\}_{n=0}^{\infty}$ 的指数型生成函数，则 $$ b_{n+1}=\sum_{k=0}^n\binom{n}{k}c_kb_{n-k} $$ 从而 $$ B'(x)=C(x)B(x)=A'(x)B(x) $$ 解得 $$ A(x)=\ln B(x) $$ 所以套用多项式求对数的模板即可求解 $a_n$。
代码
拓展
令 $a_n$ 表示在一个 n-集合上完成某个任务的方法数，$a_0=0$。对于 $n\ge 1$，令 $b_n$ 表示将集合 $[n]$ 划分成任意的非空子集，然后在这些非空子集上完成前面任务的方法数，$b_0=1$。设 $\{a_n\}_{n=0}^{\infty}$ 和 $\{b_n\}_{n=0}^{\infty}$ 的指数型生成函数分别为 $f(x)$ 和 $g(x)$，则对任意固定的正整数 $i$，将 $[n]$ 划分成 $i$ 个非空子集时，所对应的方法数的指数型生成函数为 $f^i(x)/i!$，且有 $$ g(x)=e^{f(x)}. $$
例 5
题意
CF438E The Child and Binary Tree
给定一个含有 $n$ 个互异正整数的数列 $c_1,c_2,\cdots,c_n$，如果一棵带点权的有根二叉树满足其所有顶点的权值都在集合 $\{c_1,c_2,\cdots,c_n\}$ 中，则称之为好树，一棵带点权的树的权值是其所有顶点权值的总和。给出一个正整数 $m$，对任意的 $s,1\leq s\leq m$，计算出权值为 $s$ 的好树个数。
题解
设 $f_i$ 表示点权和为 $i$ 的符合条件的二叉树的个数，$g_i$ 表示权值 $i$ 是否在 $c_i$ 中。 $$ f_0=1\\ f_n=\sum_{i=1}^ng_i\sum_{j=1}^{n-i}f_jf_{n-i-j}~~(n>0) $$ 这个式子的意思是枚举根结点的权值 $i$，然后枚举根结点左右子树的权值，容易发现这是三个多项式的卷积。用 $F(x),G(x)$ 分别表示数列 $\{f_n\}_{n=0}^{\infty},\{g_n\}_{n=0}^{\infty}$ 的普通生成函数。则有 $$ F(x)=G(x)F^2(x)+1 $$ 解得 $$ F(x)=\frac{2}{1+\sqrt{1-4G(x)}} $$ 所以套用多项式开根+求逆即可
