简介
感觉是一个很有未来的东西
普通生成函数
定义
序列 $a_1,a_2,\cdots a_n$ 的普通生成函数，又称 $OGF$，定义为形式幂级数 $F(x)=\sum_{i=0}^{\infty} a_ix^i$
通过将 $a_{n+1}\cdots$ 等设置为 $0$，将其变成一个有限数列
注意到我们一直将生成函数称为形式幂级数，即我们只考虑它的形式
封闭形式与展开形式
对于生成函数 $F(x)=1+x+x^2+\cdots$，容易得到 $xF(x)+1=F(x)$，所以 $F(x)=\frac{1}{1-x}$
而 $F(x)=\frac{1}{1-x}$ 就是 $F(x)=1+x+x^2+\cdots$ 的封闭形式，反过来 $F(x)=1+x+x^2+\cdots$ 是展开形式
几个重要的封闭形式与展开形式
$1+x+x^2+\cdots=\frac{1}{1-x}$
$1+x^k+x^{2k},\cdots=\frac{1}{1-x^k}$
$1+ax+a^2x^2+\cdots=\frac{1}{1-ax}$
$x^k+x^{k+1}+\cdots =\frac{x^k}{1-x}$
$\sum_{n=0}^{\infty} \binom{n+k-1}{k-1}x^n=\frac{1}{(1-x)^k}$
$\sum_{i=0}^{\infty}\binom{n}{i}=(1+x)^n$
组合意义
普通生成函数解决的是若干种物品的组合问题
微积分
$\frac{\rm d}{\rm dx}(\sum_{n=0}^{\infty}a_nx^n)=\sum_{n=0}^\infty(n+1)a_{n+1}x^n$
$\int(\sum_{n=0}^\infty a_nx^n)=\sum_{n=1}^\infty\frac{f_{n-1}}{n}x^n+C$
指数生成函数
定义
序列 $a_1,a_2,\cdots a_n$ 的指数生成函数，又称 $EGF$，定义为形式幂级数 $F(x)=\sum_{i=0}^{\infty} \frac{a_i}{i!}x^i$
几个重要的封闭形式和展开形式
$1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots=e^x$
$1-x+\frac{x^2}{2!}-\frac{x^3}{3!}+\cdots=e^{-x}$
$1+\frac{x^2}{2!}+\frac{x^4}{4!}+\frac{x^6}{6!}+\cdots=\frac{e^x+e^{-x}}{2}$
$x+\frac{x^3}{3!}+\frac{x^5}{5!}+\frac{x^7}{7!}=\frac{e^x-e^{-x}}{2}$
$\sum_{n=1}^{\infty}\frac{(-1)^{n-1}}{n}x^n=\ln(1+x)$
$\sum_{n=1}^{\infty}\frac{1}{n}x^n=\ln(\frac{1}{1-x})$
$\sum_{n=0}^\infty(-1)^n\frac{x^{2n+1}}{(2n+1)!}=\sin x$
$\sum_{n=0}^\infin \frac{x^{2n}}{(2n)!}=\cos x$
组合意义
指数生成函数解决的是若干种物品的排列问题
微积分
$\frac{\rm d}{\rm dx}(\sum_{n=0}^{\infty}a_n\frac{x^n}{n!})=\sum_{n=0}^\infty a_{n+1}\frac{x^n}{n!}$
$\int(\sum_{n=0}^\infty a_n\frac{x^n}{n!})=\sum_{n=1}^\infty a_{n-1}\frac{x^n}{n!}+C$
注意到指数生成函数的求导和积分相当于是左移和右移，而乘 $x$ 和除 $x$ 则是类似普通生成函数积分和求导一样的东西
概率生成函数
定义
若 $X$ 为某个离散型随机变量，那么 $X$ 的概率生成函数为
特殊取值
- $F(1)=1$
- $E(X)=F’(X)$
- $E^2(X)=F’’(X)+F’(X)$
- $V(X)=F’’(X)+F’(X)-F’(X)^2$
指数公式定理（指数生成函数exp的组合意义）
如果存在两个 $EGF$，$F(x)$ 与 $G(x)$，满足 $e^{F(x)}=G(x)$，$F(x)$ 是 $f$ 的 $EGF$，那么 $G(x)$ 是
的 $EGF$，其中 $\pi$ 是 $[n]$ 的划分
来源：https://www.luogu.com.cn/blog/220037/exp-formula#
上面那个解释不是太好理解，我们思考下面这个解释
把 $n$ 个有标号的球放到任意多个无标号盒子中，并且一个放了 $i$ 个球的盒子有 $a_i$ 种染色方案，那么放 $n$ 个球并染色的方案就是 $[x^n]exp(A(x))$
我们来看一个最经典的式子，贝尔数 $B(x)=exp(e^x-1)$，贝尔数的定义：将 $n$ 个有标号的小球放到任意多个无标号盒子中的方案数，注意到将大于等于 $1$ 个球放到一个盒子中的方案都是 $1$，所以 $A(x)=e^x-1$，那么 $B(x)=exp(A(x))$
令 $F (x)$ 为带标号简单无向连通图的指数生成函数，$G( x)$ 为带标号无向图的指数生成函数
我们有 $e^{F(x)}=G(x)$，$g_n=2^{\binom{n}{2}}$
Euler变换
将 $exp$ 的组合意义中的有标号元素换成无标号元素就得到了 $Euler$ 变换，$euler(F(x))=\prod_{n} \frac{1}{(1-x^n)^{f_n}}$
生成函数对序列高阶差分和高阶前缀和的优化
首先我们考察前缀和，令 $A_0(x)$ 为原序列 $a_i$ 的生成函数，那么一阶前缀和 $A_1(x)=\sum_{n=0}\sum_{i=0}^na_ix^n=\sum_{n=0}x^n\sum_{i=0}^na_ib_{n-i}$，其中 $b_n=1$，能够发现这是一个卷积的形式，那么 $A_1(x)=A_0(x)B(x)$，能够发现 $B(x)$ 就是 $\frac{1}{1-x}$
差分和前缀和类似，能够得到一阶差分就是乘上 $1-x$
综上，$A_k(x)=(1-x)^{-k}A(x)$，$k>0$ 为 $k$ 阶前缀和，$k<0$ 为 $k$ 阶差分
当我们需要求 $k$ 阶前缀和或者 $k$ 阶差分时，直接使用 $(1-x)^{-k}$ 的展开式即可
常见数列的生成函数推导
斐波那契数
众所周知，斐波那契数列的递推是 $f_0=0,f_1=1,f_n=f_{n-1}+f_{n-2}$，那么我们容易得到 $f_n$ 的生成函数 $F(x)$ 的递推式为 $F(x)=x+xF(x)+x^2F(x)$，即 $F(x)=\frac{x}{1-x-x^2}$，通过这个东西可以退出斐波那契数的通项公式为 $f_n=\frac{(\frac{1+\sqrt 5}{2})^n-(\frac{1-\sqrt 5}{2})^n}{\sqrt 5}$
卡特兰数
众所周知，卡特兰数的递推是 $f_0=1,f_n=\sum_{i=0}^{n-1}f_if_{n-1-i}$，那么我们容易得到 $f_n$ 的生成函数 $F(x)$ 的递推式为 $F(x)=1+xF(x)^2$，即 $F(x)=\frac{1-\sqrt {1-4x}}{2x}$
一类通过生成函数求线性递推式的方法
这里我们只考虑求 $F(x)=\sqrt {G(x)}$ 的公式，令 $H(x)=\frac{1}{\sqrt {G(x)}}$
$F’(x)=\frac{G’(x)}{2\sqrt{G(x)}}=\frac{G’(x)}{2}H(x)$
$H’(x)=-\frac{G’(x)}{2G(x)}H(x)$
则有 $G’(x)H(x)=-2H’(x)G(x)$
另外我们有 $2F’(x)=G’(x)H(x)$
例题
简要题意：给定 $n$ 和 $[1,n]$ 中生成每个数的概率 $p_i$，现在开始随机生成 $[1,n]$ 的数，若生成的数不是已经生成的数的最大值，那么停止生成，最终得分是生成的数的个数的平方，求期望得分
$n\le 100$
简要题解：我们考虑概率生成函数 $F(x)=\sum_{i=0}^{\infty}\Pr(X\ge i)x^i$，随机变量 $X$ 表示生成的数的个数
那么我们发现 $F(x)=\prod_{i=1}^n\frac{1}{1-p_ix}$，原因的话，我们考虑枚举所有生成了 $k$ 个数的情况，因为这 $k$ 个数的生成只有一种顺序，所以可以看成集合
考虑将我们要求的东西转换成与 $F(x)$ 有关的式子：
那么答案就是 $2F’(1)+F(1)$，容易得到 $F’(x)=F(x)\sum_{i=1}^n\frac{p_i}{1-p_ix}$，时间复杂度 $O(n)$
简要题意：给定 $n,k,D$，对于一个长度为 $n$ 的序列 $a_i$，我们定义它的价值为 $\frac{D!}{\prod_{i=1}^n(a_i+k)!}$，求对于所有满足 $\sum_{i=1}^n a_i=D,a_i\ge 0$ 的序列 $a_i$ 的价值和
$n,k\le 50,D\le 10^8$
简要题解：我们考虑转换一下原式，得到 $\frac{(D+nk)!}{\prod_{i=1}^n(a_i+k)!}\times \frac{D!}{(D+nk)!}$，其中 $\sum_{i=1}^n a_i=D,0\le a_i\le D$
容易得到这个式子的前半部分等价于 $EGF$，$x^{D+nk}^n$
它的组合意义很明显，有 $n$ 种物品，每种物品有 $D+k$ 个，且至少选 $k$ 个，一共选 $D+nk$ 个物品做排列的方案数
然后对于这个东西，我们直接暴力二项式展开算系数即可，时间复杂度 $O(D+n^2k)$
简要题意：你现在有一个整数 $x$，题目给出它属于 $[0,n]$ 中某个数的概率，现在要进行 $m$ 次随机，每次随机将等概率的将 $x$ 变成 $[0,x]$ 中的任意一个整数，求 $m$ 次操作后，整数 $x=k$，其中 $k\in[0,n]$ 的概率
$n\le 10^5,m\le 10^{18}$
简要题解：我们令 $f_{k,i}$ 表示进行了 $k$ 次随机之后为 $i$ 的概率，容易得到 $f_{k,i}=\sum_{j=i}^n\frac{f_{k-1,j}}{j+1}$，发现这个东西是一个线性变换，尝试用生成函数搞一下，我们将其写成生成函数的形式，得到 $F_{k}(x)=\sum_{i=0}^nf_{k,i}x^i$，然后尝试化简一下
现在似乎有点眉目了，但是这个 $\frac{1}{x-1}$ 和这个从 $1$ 积到 $x$ 的积分不是很好应对，我们令 $G_{k}(x)=F_{k}(x+1)$，然后在带进这个式子里去，$G_{k}(x)=\frac{1}{x}\int_{1}^{x+1}F_{k-1}(t)\rm dt=\frac{1}{x}\int_{0}^xF_{k-1}(t+1)\rm dt$，我们注意到 $G_{k-1}(x)=F_{k-1}(x+1)$，那么我们就能得到 $G_k(x)=\frac{1}{x}\int_{0}^xG_{k-1}(x)\rm dt=\sum_{i=0}^n\frac{1}{i+1}g_{k-1,i}x^i$，也就是说 $g_{k,i}=\frac{1}{(i+1)^k}g_{0,i}$，然后我们只需要求一下 $F_0(x)$ 到 $G_0(x)$ 的转换和 $G_m(x)$ 到 $F_m(x)$ 的转换，推一下能发现都是一个差卷积的形式，时间复杂度 $O(n\log n)$
简要题意：现在有 $n$ 种物品，每种物品都有无限多个，第 $i$ 个物品的体积为 $v_i$，求恰好装满 $k,k\in[1,m]$ 的背包的方案数
$n,m\le 10^5$
简要题解：容易得到生成函数 $F(x)=\prod_{i=1}^n\frac{1}{1-x^{v_i}}$，我们尝试用 $\exp$ 和 $\ln$ 来操作一下，$F(x)=exp(\ln F(x))=exp(\sum_{i=1}^n\ln\frac{1}{1-x^{v_i}})$，我们知道 $\ln(\frac{1}{1-x})=\sum_{i\ge 1}\frac{x^i}{i}$，那么 $\sum_{i=1}^n\ln\frac{1}{1-x^{v_i}}$，我们是可以在 $O(n\log n)$ 的时间内完成预处理的，这样再做一个 $exp$ 就结束了，时间复杂度 $O(n\log n)$
简要题意：令 $f_n$ 为斐波那契数第 $n$ 项，求 $\sum \prod_{i=1}^m f_{a_i}$，$m>0,a_1,a_2,\cdots,a_m>0,\sum_{i=1}^ma_i=n$
$n\le 10^{100000}$
简要题解：令 $F(x)$ 为斐波那契数的生成函数，那么容易得到答案的生成函数就是 $\sum_{i=0}^\infty F(x)^i-[n=0]=\frac{1}{1-F(x)}-[n=0]$
我们考虑 $G(x)=\frac{1}{1-F(x)}$ 这个生成函数，我们知道 $F(x)=\frac{x}{1-x-x^2}$，那么 $G(x)=\frac{1-x-x^2}{1-2x-x^2}$，我们尝试求出它的递推式
我们知道分母的递推式就是 $a_n=2a_{n-1}+a_{n-2}$，我们将这个递推式乘上 $1-x-x^2$，那么变成 $a_n-a_{n-1}-a_{n-2}=a_{n-1}\rightarrow a_n=2a_{n-1}+a_{n-2}$，解特征方程能得到 $x_1=1-\sqrt 2,x_2=1+\sqrt 2$，我们知道 $a_0=0,a_1=1$，能够得到 $a_n=\frac{(1+\sqrt 2)^n-(1-\sqrt 2)^n}{2\sqrt 2}$
我们知道 $2$ 在 $1e9+7$ 下有二次剩余 $59713600$，那么我们直接做快速幂即可，注意指数要对 $\varphi(1e9+7)$ 取模
简要题意：给定一个含有 $n$ 个相异正整数的序列 $c_i$，现在要求用这些数构造一个带点权的有根无标号二叉树（形态不同，二叉树不同），一棵二叉树的权值为所有点的权值的和，现在给定 $m$，求权值为 $m$ 的二叉树的个数
$n,m\le 10^5$
简要题解：我们考虑 $dp$，令 $f_k$ 表示权值为 $k$ 的二叉树的个数，$f_k=\sum_{c\in S}\sum_{i=0}^{k-c}f_{i}f_{k-c-i}$，其中 $f_0=1$，那么容易得到生成函数为 $F(x)=C(x)F(x)^2+1$，解得 $F(x)=\frac{1-\sqrt {1-4C(x)}}{2C(x)}$，我们上下同乘 $1+\sqrt {1-4C(x)}$，得到 $\frac{2}{1+\sqrt {1-4C(x)}}$，那么现在我们只需要多项式开根和多项式求逆即可，时间复杂度 $O(n\log n)$
简要题意：现在有 $n$ 个骨牌，每个骨牌有左右两边，每边只能是黑色和白色且不能交换，现在给定 $n$ 个骨牌，有些骨牌的的某一些边已经固定了颜色，剩下的位置需要你来染色，现在一种合法的染色方案为将 $n$ 个骨牌染好色之后，存在一个圆排列满足，任亮两个相邻骨牌的相邻的两个边的颜色不同，即第 $i$ 个骨牌的右边和第 $i+1$ 个骨牌的左边的颜色不同，求有多少种染色方案
$n\le 10^5$
简要题解：容易得到一个合法方案一定有 $00$ 和 $11$ 的数量相同，但如果 $00$ 和 $11$ 都只出现一次，会有一些不合法方案，这个单独处理即可，所以接下来的讨论我们不考虑这种情况
我们令 $a$ 表示 $00$ 的个数，$b$ 表示 $11$ 的个数，$c$ 表示 $0?$ 加上 $?0$ 个数，$d$ 表示 $1?$ 加上 $?1$ 的个数，$e$ 表示 $??$ 个数
令 $f_{i}$ 表示 $00$ 的个数减掉 $11$ 的个数为 $i$ 的染色方案数
容易得到一个 $c$ 会让 $f’_i= f_i+f_{i-1}$，一个 $d$ 会让 $f’_i=f_i+f_{i+1}$，一个 $e$ 会让 $f’_i=f_{i-1}+2f_i+f_{i+1}$，这个东西是线性变换，我们考虑多项式，第一个相当于乘上 $(1+x)^c$，第二个相当于乘上 $(1+\frac{1}{x})^d$，第三个相当于乘上 $(2+x+\frac{1}{x})$，除了第三个，前面两个的式子我们都可以手推出来，第三个我们只能做多项式快速幂了
时间复杂度为 $O(n\log n)$，但常数巨大
简要题意：求 $n$ 个点的无标号无根树数量，答案对 $998244353$ 取模
$n \le 2\times 10^5$
简要题解：首先我们考虑无标号有根树计数，令 $F(x)$ 为无标号有根树的生成函数
我们枚举根节点，容易得到 $F(x)=x\times Euler(F(x))=x\times exp(\sum_{n=1}\frac{F(x^n)}{n})$
我们考虑求 $F(x)$，容易想到使用牛顿迭代，我们令 $H(F_k(x))=F_k(x)-x\times exp(\sum_{n=1}\frac{F_k(x^n)}{n})\equiv 0(\bmod x^{2^k})$，注意到 $exp$ 里的求和 有一个 $F_k(x^n)$，因为 $F_k(x)$ 的前 $2^{k-1}$ 项一定与 $F_{k-1}(x)$ 相同，所以当 $n\ge 2$ 时，$\frac{F_k(x^n)}{n}$ 只与 $F_{k-1}(x)$ 有关，换句话说这个东西是常数，那么我们现在能够得到 $H(F_k(x))=F_k(x)-x\times exp(\sum_{n=2}\frac{F_k(x^n)}{n})\times exp F_k(x),H’(F_k(x))=1-x\times exp(\sum_{n=2}\frac{F_k(x^n)}{n})\times exp F_k(x)$，根据牛顿迭代的公式，我们能够得到 $F_k(x)=F_{k-1}(x)-\frac{F_k(x)-x\times exp(\sum_{n=2}\frac{F_k(x^n)}{n})\times exp F_k(x)}{1-x\times exp(\sum_{n=2}\frac{F_k(x^n)}{n})\times exp F_k(x)}$
时间复杂度为 $O(n\log n)$，常数较大
然后我们考虑无标号无根树计数，相对于无标号有根树计数，我们只需要在根为重心的时候统计一次即可，如果 $n$ 是奇数，那么树的重心有且仅有一个，我们枚举根的一个大于 $\lceil \frac{n}{2}\rceil$ 的子树的大小即可，不合法的答案为 $\sum_{i=\lceil\frac{n}{2}\rceil}^{n-1}f_{i}f_{n-i}$，如果 $n$ 是偶数，那么有可能存在有两个重心的情况，如果将两个重心中间的边断开，形成两棵树，这两棵树如果完全相同，则这些方案我们只会统计一次，不会算重，否则我们恰好算了两次，那么我们把多算的减掉即可，即减掉 $\binom{f_{\frac{n}{2}}}{2}$ 次
简要题意：假设现在有一个集合 $S$，$S$ 中只含若干个 $[1,n]$ 的正整数，我们令 $f(k)$ 为把 $k$ 表示成 $S$ 中的元素的和的方案数，每个数都能用无限次，每种方案都是无序的，现在给定 $f(1)$ 到 $f(n)$ 这 $n$ 个模 $p$ 的值，求构造一个字典序最小的集合 $S$，保证 $p$ 是素数，但不一定是 $998244353$
$n\le 2^{18}$
简要题解：我们不妨令 $f(x)$ 的生成函数为 $F(x)$，根据一些经典结论容易得到 $F(x)=\prod_{a_i\in S}\frac{1}{1-x^{a_i}}=\exp(\sum_{a_i\in S}\ln\frac{1}{1-x^{a_i}})=\exp(\sum_{a_i\in S}\sum_{n=1}\frac{x^{na_i}}{n})$
两边取一下 $\ln$，能够得到 $\ln F(x)=\sum_{a_i\in S}\sum_{n=1}\frac{x^{na_i}}{n}$，我们令 $G(x)$ 表示 $S$ 的生成函数，含义为如果 $S$ 有 $a_i$ 这个元素，那么 $x^{a_i}$ 的系数为 $1$，否则为 $0$，那么能够得到 $f(k)=\frac{1}{k}\sum_{d|k}\frac{d}{k}g(d)$，容易发现这是一个莫比乌斯反演的形式，那么答案一定是唯一的
唯一的难点在于任意模数多项式求逆，用三模NTT写确实慢，时间复杂度 $O(n\log n)$
简要题意：现在有两个序列 $a$ 和 $b$，长度分别为 $n$ 和 $m$，现在随机从 $a$ 中选一个数 $x$，然后再随机从 $b$ 中选一个数
$y$，求对于 $k\in [1,t]$，$(x+y)^k$ 的期望是多少，答案对 $998244353$ 取模$a,b,t\le 10^5$
简要题解：我们将 $(x+y)^k$ 拆开，然后得到 $ans_k=\sum_{x=1}^n\sum_{y=1}^m\sum_{i=0}^k\binom{k}{i}a_x^ib_y^{k-i}$，稍微交换一下求和顺序，$ans_k=\sum_{i=0}^n\binom{k}{i}(\sum_{i=1}^na_x^i)(\sum_{j=1}^mb_y^{k-i})$，我们令 $A_k$ 表示 $\sum_{i=1}^na_i^k$，如果我们能预处理 $A_0$ 到 $A_1$，那么 $ans$ 我们可以直接卷积
我们现在考虑如何求 $A_k$，我们令 $A_k$ 的生成函数为 $F(x)$，容易得到 $F(x)=\sum_{i=1}^n\frac{1}{1-a_ix}$，发现对于分数的求和并没有什么特别好的做法，一个比较简单的做法是类似于分治+NTT的做法，我们直接维护分子和分母这两个多项式，然后左右两边乘的时候暴力通分即可
我们接下来考虑一个比较神奇的做法，我们考虑将这个 $\sum$ 变成 $\prod$，实现这个的最好做法是 $\ln$，但原始并没有 $\ln$，所以我们造一个 $\ln$，我们知道 $\ln’(1-a_ix)=\frac{-a_i}{1-a_ix}$，我们令 $G(x)=\sum_{i=1}^n\ln’(1-a_ix)$，那么我们有 $F(x)=-xG(x)+n$
而 $G(x)=\sum_{i=1}^n\ln’(1-a_ix)=\ln’(\prod_{i=1}^n1-a_ix)$，这个直接分治+NTT加多项式 $\ln$ 即可
时间复杂度 $O(n\log^2 n)$
简要题意：给定一个长度为 $n$ 的序列 $a_i$，现在需要计算对于所有满足条件的序列 $b_i$ $\prod_{i=1}^n\binom{b_i}{a_i}$ 的累加和，序列 $b_i$ 满足的条件为序列 $b$ 只包含自然数且长度为 $n$，序列 $b_i$ 中所有数的和小于等于 $m$
$n\le 5000,a_i\le 2000,m\le 10^9$
简要题解：考虑生成函数，我们令 $F_k(x)=\sum_{i=0}^\infty\binom{i}{a_k}x^k$，容易得到答案就是 $\sum_{k=0}^m[x^k]\prod_{i=1}^nF_i(x)$，注意到 $F_i(x)$ 的形式还可以继续化简，根据 $\frac{1}{(1-x)^k}=\sum_{i=0}^\infty\binom{i+k-1}{k-1}x^i$，我们可以得到 $F_k(x)=\frac{x^{a_k}}{(1-x)^{a_k+1}}$
那么 $ans=\sum_{k=0}^m[x^k]\frac{x^{\sum_{i=1}^na_i}}{(1-x)^{n+\sum_{i=1}^na_i}}$，我们令 $t=\sum_{i=1}^na_i$，那么 $ans=\binom{m+n}{n+t}$
简要题意：给定 $m$ 个字符串 $S_i$，字符集为 $[1,n]$，现在要求对于每个字符串 $S_i$ 进行如下操作：从空串 $T$ 开始，每次随机生成一个 $[1,n]$ 内的整数，添加到 $T$ 的末尾，直到 $S$ 作为 $T$ 的子串出现过，求 $T$ 的期望长度
$|S_i|,n\le 10^5,m\le 50$
简要题解：我们令 $f_i$ 表示 $T$ 的长度为 $i$ 的概率，$g_i$ 表示 $T$ 的长度大于 $i$ 的概率，分别令 $F(x)$ 和 $G(x)$ 为 $f_i$ 和 $g_i$ 的生成函数
容易得到 $F(x)+G(x)=1+xG(x)$ 这个等式，可以理解其为没有停止时，我们再加入一个字符，有停止和继续两种情况，加一是处理边界情况
同时，我们可以得到另一个等式 $G(x)(\frac{1}{n}x)^m=F(x)\sum_{i=1}^na_i(\frac{1}{n}x)^{m-i}$，这里我们令 $m$ 表示字符串 $S$ 的长度 $a_i$ 表示 $S[1..i]$ 是否为 $S$ 的 $border$，这个等式可能理解起来有一点难度，我们可以理解其为没有停止的串加入 $S$ 之后一定会停止，但注意到可能会在完整添加 $S$ 之前停止，这种情况只有在 $S[1..i]$ 是 $S$ 的 $border$ 的情况下，我们添加了 $S[1..i]$ 就已经停止了
我们考虑利用这两个式子来得到我们所需要的答案，即 $F’(1)$
我们对第一个式子求导并带入 $x=1$，可以得到 $F’(1)=G(1)$，在第二个式子里带入 $x=1$ 并化简可以得到 $G(1)=\sum_{i=1}^m a_in^i$，时间复杂度 $O(n)$
简要题意：给定 $n$，求 $n$ 个点有标号简单无向连通图的数量
$n\le 1.3\times 10^5$
简要题解：我们令 $g_n$ 表示 $n$ 个点的简单无向图的数量，$f_n$ 表示 $n$ 个点简单无向连通图的数量，则 $g_n=2^{\binom{n}{2}}$，我们枚举 $1$ 号点所在的位置，可以得到 $g_n=\sum_{i=1}^n\binom{n-1}{i-1}f_ig_{n-i}$，这个式子把 $f_n$ 提到左边就可以直接分治 $NTT$，时间复杂度 $O(n\log^2 n)$，我们考虑继续化简
我们令 $H(x)=\sum_{i=1}^n\frac{g_i}{(i-1)!},F(x)=\sum_{i=1}^n\frac{f_i}{(i-1)!},G(x)=\sum_{i=0}^n\frac{g_i}{i!}$，那么 $F(x)=H(x)G^{-1}(x)$，我们只需要一个多形式求逆，时间复杂度 $O(n\log n)$
另外我们考虑生成函数，我们令 $F(x)$ 表示简单无向连通图的指数生成函数，$G(x)$ 表示简单无向图的指数生成函数，根据指数公式定理，我们可以得到 $e^{F(x)}=G(x)$，那么 $F(x)=\ln G(x)$
简要题意：现在有一个 $n$ 个点的无向图，每条边存在的概率都为 $p$，求图的连通块的期望个数
$n\le 5\times 10^5$
简要题解：我们令 $f_n$ 表示 $n$ 个点联通的概率，$g_n$ 表示 $n$ 个点不连通的概率，那么我们知道最后的答案就是 $\sum_{i=1}^n\binom{n}{i}f_i(1-p)^{i(n-i)}$，我们首先考虑如何求 $f_n$
对于一个不连通的图，我们枚举 $1$ 号点所在连通块的大小，可以得到 $g_n=\sum_{i=1}^{n-1}\binom{n-1}{i-1}f_i(1-p)^{i(n-i)}$，我们知道 $g_n=1-f_n$，那么这个东西很像是一个分治 $NTT$ 的式子，但 $(1-p)^{i(n-i)}$ 无法拆开，我们考虑其组合意义，容易得到 $i(n-i)=\binom{n}{2}-\binom{i}{2}-\binom{n-i}{2}$，那么就可以拆成 $\frac{(1-p)^{\binom{n}{2}}}{(1-p)^{\binom{i}{2}}(1-p)^{\binom{n-i}{2}}}$，这样我们就可以做分治 $NTT$ 了，时间复杂度 $O(n\log^2 n)$，我们考虑继续化简
我们令 $F(x)=\sum_{i=1}^n\frac{f_i}{(i-1)!(1-p)^{\binom{i}{2}}}x^i,G(x)=\sum_{i=1}^n\frac{1}{(i-1)!(1-p)^{\binom{i}{2}}}x^i,H(x)=\sum_{i=0}^n\frac{1}{i!(1-p)^{\binom{i}{2}}}x^i$，则可以得到 $\frac{G(x)}{H(x)+1}=F(x)$，需要注意 $H(x)=0$，那么这个式子可以用多项式求逆解决，时间复杂度 $O(n\log n)$
我们考虑指数公式定理，令 $g_n$ 表示 $n$ 个点无向图的概率，$f_n$ 表示 $n$ 个点联通的概率，显然有 $g_n=1$，同时我们令 $G(x)$ 和 $F(x)$ 分别为 $g_n$ 和 $f_n$ 的 $EGF$，那么我们应该有 $exp(F(x))=G(x)$，但实际上这并不成立，因为 $f_n$ 和 $f_m$ 合并贡献到 $g_{n+m}$ 时还需要乘上 $(1-p)^{nm}$ 这个系数，所以我们需要把 $\frac{1}{(1-p)^{\binom{n}{2}}}$ 的系数乘到 $f_n$ 和 $g_n$ 上，所以 $G(x)$ 和 $F(x)$ 应该为 $\frac{f_n}{(1-p)^{\binom{n}{2}}}$ 和 $\frac{g_n}{(1-p)^{\binom{n}{2}}}$ 的 $EGF$，那么我们只需要做一个 $\ln$ 即可，时间复杂度 $O(n\log n)$
简要题意：给定 $n,m$，求有多少长度为 $m$ 的序列 $a_i$，满足 $a_i\in[1,n]$，且不存在一个长度为 $n$ 的子区间且这个子区间是一个 $1$ 到 $n$ 的排列
$n,m\le 2\times 10^5$
简要题解：我们考虑计算出现 $[1,n]$ 的排列的方案数，对于每个出现过 $[1,n]$ 的序列 $a_i$，我们在 $[1,n]$ 第一次出现的位置来统计贡献，我们令 $f_k$ 表示区间 $[1,k-1]$ 没有出现 $[1,n]$ 的排列，且 $[k,k+n-1]$ 是一个 $[1,n]$ 的排列的方案数，容易得到 $f_k=n^{k-1}n!-\sum_{i=1}^{i+n-1<k}f_in^{k-i-n}n!-\sum_{i+n-1\ge k}^{k-1}f_i(k-i)!$，容易发现这个东西是符合分治 $NTT$ 的形式的，直接计算即可，时间复杂度 $O(n\log^2 n)$，另外这个式子也可以化简成求逆的式子
简要题意：求 $n$ 个点有标号有向无环图的个数，需要保证该有向图弱连通
$n\le 10^5$
简要题解：我们首先不考虑弱连通，令 $g_n$ 表示 $n$ 个点有标号有向无环图的个数，我们钦定入度为 $0$ 的点的个数为 $i$，那么我们有 $g_n=\sum_{i=1}^n\binom{n}{i}(-1)^{i+1}g_{n-i}2^{i(n-i)}$，其中 $(-1)^{i+1}$ 是容斥系数，因为我们是钦定了 $i$ 个点的入度为 $0$，$g_{n-i}$ 中也有入度为 $0$ 的点，这里显然是一个二项式反演
有了这个式子之后我们可以直接分治 $NTT$，或者再推一下可以得到 $\frac{g_n}{2^{\binom{n}{2}}n!}=\sum_{i=1}^n\frac{(-1)^{i+1}}{2^\binom{i}{2}i!}\frac{g_{n-i}}{2^{\binom{n-i}{2}}(n-i)!}$，这显然是一个求逆的式子，我们令 $G(x)$ 表示不要求弱连通的 $EGF$，$F(x)$ 表示需要弱连通的$EGF$，我们显然有 $e^{F(x)}=G(x)$，那么只需要一个多项式 $ln$，时间复杂度 $O(n\log n)$
简要题意：给定 $n$ 和 $q$，现在有 $q$ 次询问，每次询问给定 $x$ 求 $\sum_{i=1}^n\binom{3i}{x}$
$n\le 10^6,q\le 2\times 10^5,x\le 3n$
简要题解：考虑生成函数知识，我们知道 $\binom{n}{i}=x^i^n$，那么关于 $x$ 的生成函数为 $F(x)=\sum_{i=1}^n(1+x)^{3i}$，简单化简我们可以得到 $\frac{(1+x)^{3n+3}-(1+x)^3}{(1+x)^3-1}$，这个东西上面可以直接用组合数计算，下面这个除法我们暴力做多项式除法即可，时间复杂度 $O(n)$
简要题意：给定一个 $n$ 个点的带权完全无向图，给定 $k$，求所有生成树的权值的 $k$ 次方之和
$n,k\le 30$
简要题解：我们知道 $(\sum_{i=1}^{n-1}w_i)^k=\sum_{i\in[1,n-1],a_i\ge0,\sum_{a_i}=k}\binom{k}{a_1,\cdots,a_k}\prod_{i=1}^{n-1}w_i^{a_i}$，这是一个多项式卷积的形式，我们考虑将其看做生成函数，相当于 $ans=k![x^k]\prod_{i=1}^{n-1}e^{w_ix}$
我们把每条边看做一个 $k$ 次的多项式，然后做矩阵树定理即可，因为 $k$ 很小，所以求逆和乘法直接 $O(k^2)$ 暴力即可
时间复杂度 $O(n^3k^2)$
简要题意：给定 $n$ 和 $k$，定义一个合法序列为 $a_i\in[1,k],i\in[1,n]$，一个序列的值为 $\prod_{i=1}^na_i$，求对于 $m\in[1,n]$，所有长度为 $m$ 的序列的价值和
$n\le 5\times 10^5 $
简要题解：看到价值和计算是先乘后加，容易想到多项式，通过简单思考可以得到生成函数为 $\prod_{i=1}^k(1+ix)$，我们知道 $ln(1+kx)=\sum_{i=1}^{\infty}\frac{(-1)^{i+1}k^i}{i}x^i$，我们那么我们考虑将原式 $\ln$ 起来再做 $\exp$，下面我们化简一下 $\ln$ 之后的式子
注意到复杂度瓶颈在于计算自然数幂和，即对于 $i\in[1,n]$，求 $F_i(k)$
我们知道固定 $k$，对于单个 $i$，$F_i(k)$ 可以用第二类斯特林数或者插值一类的做法来做，对于 $i\in[1,n]$，我们考虑从多项式的角度入手，我们写出这东西的 $EGF$，然后考虑化简
这个东西的分母常数项为 $0$，看起来不能直接求逆，但同时分子的常数项也为 $0$，所以可以同除 $x$ 之后求逆
简要题意：给定一个多重集 $S$，满足 $S$ 中的元素都在 $[0,n]$，且 $|S|=n$，求由 $S$ 组成的长度为 $n$ 的序列的价值和，一个序列的价值定义为它的所有区间的 $mex$ 的和
$n\le 10^5$
简要题解：令 $a_i$ 表示 $S$ 中 $i$ 的出现次数，我们首先考虑枚举区间的组成 $b_i$，满足 $\forall i\in[0,n],0\le b_i\le a_i$，对于 $mex$ 为 $k$ 的答案，我们考虑枚举 $i\in [0,k-1]$，在 $[0,i]$ 都出现至少一次的时候记一次答案，这样正好记 $k$ 次答案，形式化的写，答案即为
考虑枚举 $\sum_{i=0}^nb_i$ 统计答案，考虑生成函数 $f_k(x)=\sum_{i=0}^{a_k}\frac{x^i}{(a_k-i)!i!}$，令 $g_k(x)=f_k(x)-\frac{1}{a_k!}$ 表示至少是 $1$，那么答案为
我们考虑分治计算，维护区间 $f$ 的乘积、区间 $g$ 的乘积以及 $\sum_{i=l}^rg_l\cdots g_if_{i+1}\cdots f_{r}$ 即可，时间复杂度 $O(n\log^2 n)$
简要题意：给定一棵大小为 $n$ 的有根树，求对于所有 $k\in[1,n]$，有多少大小为 $k$ 的集合，满足集合内不存在任意两点使得一个点是另一个点的祖先
$n\le 2\times 10^5$
简要题解：我们令 $f_u(x)$ 表示以 $u$ 为根的子树的生成函数，容易得到 $f_u(x)=1+x+\prod_{v}f_v(x)$，但是我们如果直接这样乘，复杂度显然是 $O(n^2\log n)$，我们参考 $dsu$ 的优化方法，首先将整棵树轻重链剖分
我们令 $g_u(x)$ 表示 $\prod_{v\neq son_u}f_v(x)$，其中 $son_u$ 表示 $u$ 的重儿子，然后对于每条重链我们在链首单独求解，注意多个多项式乘的时候必须分治来乘，这样的时间复杂度为 $O(n\log^3 n)$，但实际运行时可以接收的
对于重链，我们不妨令其长度为 $k$，从链首到链尾的节点构成的序列为 $a_i$，那么我们有 $f_{a_1}(x)=\prod_{i=1}^kg_{a_i}(x)+\sum_{i=1}^kx\prod_{j=1}^{i-1}g_{a_j}(x)$，前面那个 $\prod$ 表示不选重链上的点，后面的 $\sum$ 枚举的选择重链上的哪个点，重链的计算也可以分治来求
简要题意：给定一个 $n$ 个点有点权的无根树，求所有大小为 $m$ 的点集的贡献和，要求点集内不存在任何两点相邻，一个点集的贡献是点集内所有点的点权积
$n\le 8\times 10^4$
简要题解：我们令 $f_u(x)$ 表示选择 $u$ 的生成函数，$g_u(x)$ 表示不选 $u$ 的生成函数，容易得到转移 $f_u(x)=w_ux\prod_{v}g_v(x)$，$g_u(x)=\prod_{v}(f_v(x)+g_v(x))$
我们考虑轻重链剖分，轻儿子暴力合并，重链在链首合并，令 $G_u(x)=\prod_{v\neq son_u}g_v(x),F_u(x)=\prod_{v\neq son_u}(f_v(x)+g_v(x)) $，其中 $son_u$ 表示 $u$ 的重儿子，为了方便表示对于重链，我们不妨令其长度为 $k$，从链首到链尾的节点构成的序列为 $a_i$，那么我们有 $f_{a_i}(x)=w_uxg_{a_{i+1}}(x)G_{a_i}(x),g_{a_i}(x)=F_{a_i}(x)(f_{a_{i+1}}(x)+g_{a_{i+1}}(x))$，我们可以把转移写成矩阵的形式，然后分治计算即可，时间复杂度 $O(n\log^3 n)$
简要题意：给定一棵以 $1$ 为根 $n$ 个点的有根树，现在要为每个点赋一个权值 $p_i$，要求 $p_i$ 为 $[1,n]$ 的排列，且对于 $u$ 为 $v$ 的父亲 $p_u\neq p_v+1$，求方案数
$n\le 2.5\times 10^5$
简要题解：我们考虑组合容斥，令 $f_k=x^k!\prod_{i=1}^n(1+d_ix)$，其中 $d_i$ 表示 $i$ 的儿子的数量，这个式子大概的意思就是选 $k$ 条不合法的边，注意到每个点 $i$ 和其儿子的连边中我们只能选择一条，令 $g_k$ 表示恰好有 $k$ 条不合法边的方案，容易得到 $f_k=\sum_{i=k}^n\binom{i}{k}g_i,g_k=\sum_{i=1}^k(-1)^{i-k}\binom{i}{k}f_i$，所求即为 $g_0$
对于 $f_k$，容易想到 $O(n\log^2 n)$ 的分治 $NTT$ 的做法，但是我们知道 $\sum_{i=1}^nd_i=n-1=O(n)$，我们考虑优化，首先对于相同的 $d_i$，不妨假设有 $k$ 个，我们显然可以做到 $O(k)$，那么我们将 $d_i$ 从大到小排序，对于相同的线性做，不同的暴力乘起来，这样的时间复杂度为 $O(n\log n)$，证明如下，令 $S$ 表示 $d_i$ 的可重集合，容易发现时间复杂度为 $O((\sum_{i\in S}\sum_{j=1}^n[i\ge j])\log n)=O(n\log n)$