分析组合 学习笔记

· · 个人记录

前置知识：基础多项式。

分析组合也称解析组合，同解析几何类似，分析组合试图用代数的视角去把握组合问题的脉络，发掘组合性质。

形式幂级数

我们试图用代数的视角考察一个数列。

形式幂级数的引入

对于一个数列 a_{1\cdots n}，我们定义其生成函数（Generating Function，也称母函数）为：

f(x)=\sum_{i=0}^n a_ix^i

其中第 i 项的系数记为 [x^i]f(x)=a_i。

特别地，当 a 为无穷数列时，其生成函数为一个有无限项的幂级数（Power Series）。

比如，数列 a={1,1,1,\cdots} 的生成函数为 1+x+x^2+x^3+\cdots。

其实这个东西可以被写成封闭形式 \dfrac{1}{1-x}，那么问题来了，代入一个 x=0 两边还是对的，代入一个 x=2 不就寄了吗？

事实上这个幂级数里的 x 是没有实际意义的，它只是为了把这个数列写成函数形式而存在的。

这样的幂级数叫做形式幂级数（Formal Power Series）。

形式幂级数的运算

有了一个函数，我们自然想对它进行操作。

那么问题来了，你这个东西有些时候它都不收敛，你操作个啥？

事实上这东西被我们假定为一定收敛，而且关于这点有严谨（但是复杂）的正确性证明。

这样我们就可以定义两集合幂级数的一些操作：

而且，既然我们不关心它是否收敛，那么它的麦克劳林展开两边就是等号，即：

F(x)=\sum_{i=0}^{\infty}\dfrac{G^{(i)}(0)}{i!}x^i

这样我们刚学的 \ln, \exp 也能应用于形式幂级数上！

生成函数

如果说形式幂级数的 x^i 就像解析几何里的坐标轴，那么生成函数就像解析几何里的曲线方程。

分析组合中最重要的思想和解析几何类似，就是方程思想。所以碰到初等组合做不来，想用生成函数时一定要考虑方程。

注意：列方程时不要忘记考虑常数项！！！

推数列通项

对于一个数列 a，定义其普通生成函数（Ordinary Generating Funtion，OGF）为：

F(x)=\sum_{i=0}^{n}a_ix^i

普通生成函数可以用来推数列通项，下面举几个例子。

设生成函数是 F(x)，那么有 F(x)=xF(x)+x^2F(x)+x，得到 F(x)=\dfrac{x}{1-x-x^2}。

这个东西怎么用呢？注意到：

F(x)=-\dfrac{x}{(\lambda_1-x)(\lambda_2-x)},\lambda_1=\dfrac{1-\sqrt{5}}{2},\lambda_2=\dfrac{1+\sqrt{5}}{2}

考虑设 F(x)=\dfrac{A}{\lambda_1-x}+\dfrac{B}{\lambda_2-x}，得到 A=\dfrac{5-\sqrt{5}}{10},B=\dfrac{5+\sqrt{5}}{10}。

而且 \displaystyle \dfrac{1}{c-x}=\sum_{i=0}^\infty c^ix^i，所以：

\text{Fib}_i=[x^i]F(x)=A\times \lambda_1^i+B\times \lambda_2^i

容易发现这是一个卷积的形式，设生成函数是 F(x)，可以写出：

F(x)=xF^2(x)+1

解得：

F(x)=\dfrac{1\pm \sqrt{1-4x}}{2x}

取哪个根好呢？

既然是生成函数最好把分子有理化，处理得到：

F(x)=\dfrac{2}{1\mp\sqrt{1-4x}}

其实由定义可以得到，形式幂级数还是有一个要求的：x=0 时 F(x)=a_0 必须收敛。

但是如果取符号就寄了，所以：

F(x)=\dfrac{2}{1+\sqrt{1-4x}}

我们把这个分母里的东西挖出来：

F(x)=\dfrac{2}{1+(\sqrt{1-4x})}=2\sum_{i=0}^{\infty}\left(-\sqrt{1-4x}\right)^i

用广义二项式定理展开，有：

F(x)=2\sum_{i=0}^{\infty}(-1)^i\sum_{d\ge 0}\binom{\frac{i}{2}}{d}(-4x)^d

所以：

\begin{aligned} \text{Cat}_d&=[x^d]F(x) \\ &=2\times (-4)^d\sum_{i\ge 2d}\binom{\frac{i}{2}}{d}(-1)^i \\ &=2\times (-2)^d\times \dfrac{1}{d!}\times \sum_{i\ge 2d}(-1)^i \dfrac{i!!}{(i-2d)!!} \end{aligned}

到这里就化不下去了。

试试把根式提到分子上：

F(x)=\dfrac{1-\sqrt{1-4x}}{2x}=\dfrac{1}{2x}\left(1-\sum_{d\ge 0}\binom{\frac{1}{2}}{d}(-4x)^d\right)

（感觉这补很无厘头，一会儿处下去，一会儿乘上来；一会儿收敛，一会儿又不收敛了）

把 d=0 的项特殊处理，刚好和那个 1 约掉，有：

F(x)=\dfrac{1}{2x}\sum_{d\ge 1}2^d\times \dfrac{1\times 1 \times 3\times 5\times \cdots }{d!}\times x^d

其中上面共有 d 项。那么对 d\ge 1：

[x^d]F(x)=2^d\times \dfrac{(2d-1)!!}{(d+1)!}=2^d\times \dfrac{(2d)!}{(d+1)!(2d)!!}=\dfrac{(2d)!}{(d+1)!d!}

这里用了一点双阶乘的处理技巧：偶数每个除 2，奇数化成阶乘除偶数。

所以

[x^d]F(x)=\dfrac{(2d)!}{(d+1)!d!}=\dfrac{1}{d+1}\times \dfrac{(2d)!}{d!\times d!}=\dfrac{1}{d+1}\binom{2d}{d}

结论就出来了。

卷积的组合意义

在组合中，除了 OGF，有时我们需要另一种生成函数，叫做指数生成函数（Exponential Generating Function，EGF）。

其定义式为：

F(x)=\sum_{i=0}^\infty a_i\times \dfrac{x^i}{i!}

EGF 的运算可以只在要用到每项系数时处理 \dfrac{1}{i!} 带来的影响，所以不作展开。

现在我们考虑它们的组合意义是什么。

如果我们将 a_{1\cdots n} 分别看作在集合 S_A 中选 1\cdots n 个数的方案数，生成函数为 A(x)，对 b 同理。

那么对于 OGF：

[x^m](A\times B)=\sum_{i=0}^m a_ib_{m-i}

其意义就是在 S_A,S_B 两集合中无序地取出总共 m 个元素的所有方案数。

那么对于 EGF：

m![x^m](A\times B)=m!\sum_{i=0}^m \dfrac{1}{i!}a_i\times \dfrac{1}{(m-i)!}b_{m-i}=\sum_{i=0}^m\binom{m}{i}a_ib_{m-i}

其意义就是在 S_A,S_B 两集合中有序地取出总共 m 个元素的所有方案数，这也被称为二项卷积。

这对我们的提醒是：无标号组合类应当用 OGF 刻画，有标号组合类应当用 EGF 刻画。

生成函数与组合类

我们推广一下上面的内容，设 a_i,b_i 分别是两个无标号组合类 S_A,S_B 中大小为 i 的对象个数，A(x),B(x) 分别为其 OGF。

注意区分组合类中的对象和元素，一个对象是元素的集合。

那么我们对一个由二者组合得到的组合类 S_C，记其 OGF 为 C，有如下情况：

这个东西是若干等比数列相乘，就是：

C=\prod_{i=0}^\infty\left(\sum_{j=0}^\infty x^{ij}\right)^{a_i}=\prod_{i=0}^\infty(1-x^i)^{-a_i}

这个东西被称为欧拉变换（Euler Transformation），记为 C(x)=\mathcal{E}(A(x))。

C=\prod_{i=0}^\infty(1+x^i)^{a_i}

上面两条公式均要求 a_0=0（否则会得到无穷），因此这里不区分求和下限中的 0 和 1。

其中前三个可以直接算，第六个的多项式复合则过于困难。

第四、五条的乘积可以考虑取对数化乘为加，得到：（第四个）

\ln C=\sum_{i=1}^\infty a_i\sum_{j=1}^\infty \dfrac{1}{j}x^{ij}

不难发现 ij\le n 的不同项只有 \mathcal O(n\log n) 种。这样求出 \ln C 再 \exp 回去即可。

另一种视角是：

C=\exp a_i\sum_{j=1}^\infty\sum_{i=1}^\infty \dfrac{a_ix^{ij}}{j}=\exp \sum_{j=1}^\infty \dfrac{F(x^j)}{j}

这在解含欧拉变换的方程时非常有用。

第五个是：

\ln C = \sum_{i=0}^{\infty}a_i\ln (1+x^i)=\sum_{i=0}^{\infty}a_i\sum_{j=1}^\infty (-1)^{j-1}\dfrac{x^{ij}}{j}

与上面类似。

四、五的实际应用类似于整数拆分，不再展开。

对于带标号的组合类，前三种和第六种是一样的，我们需要解决的只是集合。

带标号组合类中无所谓可不可重，对带标号组合类中集合的理解大致类似于无标号中的可重集：每个对象可以组合多次。

对于一个大小为 x 的有标号计数对象集合，有 x! 种序列可以生成它，所以其生成函数为：

\sum_{i=0}^\infty \dfrac{A^i(x)}{i!}=\exp(A(x))

这东西还是好算的。

理解一下它的实际意义：将 A 这个组合类中的对象有标号但是无序地并入 B 的对象中。

或者反过来，将有标号组合类 B 中的每个对象划分成无序集合，集合中每个元素都是 A 的对象。

这类似于第二类斯特林数，举例：

这样我们得到了对于 EGF，\exp 运算的直观理解。

例题

求有多少 f:[n]\to [n]，使得：f^k=f^{k-1}，其中次幂是若干次复合映射。

看到 k\le 3 果断先考虑分讨，首先 k=1 是平凡的。

对于 k=2，问题的限制就是像中的每个元素都会射到自己，所以最终形态就像一棵有根菊花森林。

我超时限有 20s，什么勾八，那就不用优化了![](https://啧.tk/hanx) $k=3$ 就是一个类似于菊花的东西：深度不超过 $2$ 的有根树。 不难发现这又是一个 $\exp$。这样其实把 $k\le 3$ 去掉也是能做的，EGF 满足： $$ F_k(x)=x\exp F_{k-1}(x) $$ - [CF891E Lust](https://www.luogu.com.cn/problem/CF891E) 不难发现操作后的答案就是**最后所有项的乘积**减去原来所有项的乘积，所以我们求最后所有项的乘积的期望即可。 这个东西的分子其实可以用解析方法用 EGF 表示为： $$ [x^k]\prod_{i=1}^n\left(\sum_{j\ge 0}(a_i-j)\dfrac{x^j}{j!}\right) $$ 看起来十分棘手。 **这时我们可以尝试化成封闭形式。**记括号里的式子为 $F_i(x)$，有： $$ F_i(x)=\sum_{j\ge 0} a_i\dfrac{x^j}{j}-\sum_{j\ge 0} j\dfrac{x^j}{j}=a_ie^x-xe^x=(a_i-x)e^x $$ 这样就可以乘起来了！ $$ [x^k]\left(e^{nx}\prod_{i=1}^n (a_i-x)\right) $$ 我们暴力卷积卷出后面那个多项式 $G(x)$，显然它最多只有 $n$ 次。 那么上面这个式子就是： $$ V=\sum_{j=0}^{\min(n,k)}\left([x^j]G(x)\right)\times\left([x^{k-j}]e^{nx}\right) $$ 而 $$ [x^{k-j}]e^{nx}=[x^{k-j}]\sum_{i=0}^\infty \dfrac{(nx)^i}{i!}=\dfrac{n^{k-j}}{(k-j)!} $$ 我们要求的真正答案是： $$ \dfrac{k!\times V}{n^k}=\sum_{j=0}^{\min(n,k)}\left([x^j]G(x)\right)\times\dfrac{n^{k-j}}{(k-j)!}\times\dfrac{k!}{n^k} $$ 这个东西就是： $$ \sum_{j=0}^{\min(n,k)}\left([x^j]G(x)\right)\times\dfrac{k^{\underline{j}}}{n^j} $$ 总复杂度 $\mathcal O(n^2)$。 **启示：做不下去时要多考虑封闭形式和展开形式间的互化。** - [CF438E The Child and Binary Tree](https://www.luogu.com.cn/problem/CF438E) 这个题和卡塔兰数有那么一点像，考虑先写出递推式。 交换题目中 $n,m$ 的定义后，设 $a_n$ 为权值和为 $n$ 的二叉树种类数，有： $$ a_n=\sum_{i=1}^m\sum_{j=0}^{n-c_i}a_ja_{n-c_i-j} $$ 初始条件是 $a_0=1$。 那么设 $a$ 的 OGF 是 $F(x)$，我们有： $$ F(x)=1+F^2(x)\sum_{i=1}^m x^{c_i} $$ 设 $\displaystyle G(x)=\sum_{i=1}^m x^{c_i}$，我们有： $$ G(x)F^2(x)-F(x)+1=0 $$ 解得： $$ F(x)=\dfrac{1\pm \sqrt{1-4G(x)}}{2G(x)} $$ 和上面类似，取 $-$ 的一个根，用广义二项式定理展开： $$ 1-\sqrt{1-4G(x)}=1-\sum_{k\ge 0}\binom{\frac{1}{2}}{k}(-4G(x))^k=-\sum_{k\ge 1}\binom{\frac{1}{2}}{k}(-4G(x))^k $$ 一通化简，得到： $$ F(x)=\sum_{k\ge 0} \text{Cat}_k\times G^k(x) $$ 但是这不能做...... **其实很多时候不需要推式子，按照封闭形式直接算就可以了**，被诈骗了QwQ 但是这个东西需要除下去算，因为 $G(x)$ 常数项为 $0$ 不方便求逆。 ## 图的计数 这是一个难度相对一般的小专题...... 以下的图均为简单图，$n\le 10^5$。 - [P4841 [集训队作业2013]城市规划](https://www.luogu.com.cn/problem/P4841)：求 $n$ 个结点的带标号连通无向图数量。 容易发现这个东西的 $\exp$ 是带标号无向图，就是 $2^{\binom{n}{2}}$ 的 EGF，所以直接 $\ln$ 即可。 - [P4233 射命丸文的笔记](https://www.luogu.com.cn/problem/P4233)：求 $n$ 个结点的带标号强连通竞赛图数量。 我们把竞赛图缩点，所有强连通分量的可达性显然是一个偏序关系。 因此这是有标号组合类的序列，$B(x)=\dfrac{1}{1-A(x)}$，则 $A(x)=1-\dfrac{1}{B(x)}$。 - [P7364 有标号二分图计数](https://www.luogu.com.cn/problem/P7364)：如题。 一个很怪怪的题目，不知道思路是哪里来的。 设 $F(x),G(x)$ 分别为二分图与连通二分图的 EGF，$F_0(x),G_0(x)$ 是分别结点二染色使得同色点不共边的方案数的 EGF。 我们可以列出： $$ F(x)=\exp G(x),F_0(x)=\exp G_0(x),G_0(x)=2G(x) $$ 这一系列方程，得到： $$ F^2(x)=F_0(x) $$ **这给我们的的启示是：如果两个组合对象的 $\ln$ 之间有关系，那么这个关系可以被简单地转化到指数上。** 这个东西的组合意义也是明显的：我们取每个连通块中的最小编号点，若在左边便染黑，在右边便染白。 这样直接多项式开根即可。但是 $F_0$ 怎么求呢？ $$ F_0(x)=\sum_{i=0}^n\binom{n}{i}2^{i(n-i)}\dfrac{x^n}{n!}=\sum_{i=0}^n\dfrac{1}{i!(n-i)!}\times 2^{\binom{n}{2}-\binom{n-i}{2}-\binom{i}{2}}x^n $$ 不难发现我们是在用一个形似 $$ \sum_{i=0}^\infty f_i\times \dfrac{x^i}{i!\cdot2^\binom{i}{2}} $$ 的奇怪东西做卷积。这个东西之后我们还会用到，暂且照着 ix35 博客，叫他**组合型生成函数**吧。 其实我看不出这有什么实际用途，而且连续卷积的函数超过两个就没有 useful 的实际意义了。 - [P6295 有标号 DAG 计数](https://www.luogu.com.cn/problem/P6295) 枚举无入度的点有哪几个，然后二项式反演，我们有： $$ f_n=\sum_{i=1}^n(-1)^{i-1}\binom{n}{i}2^{i(n-i)}f_{n-i} $$ 又是上面那个组合型生成函数。设： $$ F(x)=\sum_{i=0}^\infty \dfrac{f_i}{i!\times 2^{\binom{i}{2}}}x^i $$ $$ G(x)=\sum_{i=1}^\infty \dfrac{(-1)^{i-1}}{i!\times 2^{\binom{i}{2}}}x^i $$ 那么 $F(x)=F(x)G(x)+1$， $F(x)=\dfrac{1}{1-G(x)}$。 由于要求弱连通，所以求个 $\ln$ 就可以了。 - 有标号强连通图计数 一个很奇怪的做法。 由于一张图里的强连通分量构成一张 DAG，而 DAG 的系数难以直接容斥，所以我们需要找到一个更好的反映强连通分量组合的函数。 我们设所有有向图的数量是 $g_n=2^{n(n-1)}$，强连通图的数量是 $f_n$。采用和上面类似的组合型生成函数技巧，设： $$ g_n=\sum_{i=0}^n h_i\times \binom{n}{i}\times g_{n-i}\times 2^{i(n-i)} $$ 这里的 $h_i$ 的意思是所有没有入度的强连通分量大小为 $i$。 这样 $G(x)=H(x)G(x)+1$，可以算 $H(x)=1-\dfrac{1}{G(x)}$ 了。 其实这个 $H$ 已经和 $\exp F$ 很接近了，不一样的是这个 $H$ 是带 $\pm 1$ 的容斥系数的，即： $$ H(x)=\sum_{i=0}^\infty (-1)^{i+1}\dfrac{F^i(x)}{i!} $$ 不能直接 $\ln$，怎么办呢？ 回想我们没学过 $\exp / \ln$ 的时候，都是枚举 $1$ 号点在哪个分量里然后容斥的。 这就是： $$ h_n=f_n-\sum_{i=1}^n\binom{n-1}{i-1}f_i h_{n-i} $$ $$ \dfrac{f_n}{(n-1)!}=\dfrac{h_n}{(n-1)!}+\sum_{i=1}^n \dfrac{f_i}{(i-1)!}\times \dfrac{h_{n-i}}{(n-i)!} $$ 这不是传统生成函数的样子，**但是我们可以干脆多设生成函数再代数分析**。 设 $\displaystyle F_0(x)=\sum_{n=1}^\infty \dfrac{f_n}{(n-1)!}x^n,H_0(x)=\sum_{n=1}^\infty \dfrac{h_n}{(n-1)!}x^n$，可以得到： $$ F_0(x)=H_0(x)+F_0(x)H(x) $$ 式子里只有一个未知量 $F_0(x)$，可以直接求。 ## 概率生成函数 ### 定义 一个奇怪的东西，和上面两个常用的没什么太大关系。 对于一个离散的随机变量 $X$，其**概率生成函数**（Probabilistic Generating Function，**PGF**）定义为： $$ F(x)=\sum_{i=0}^{\infty}P(X=i)x^i $$ 我们要尝试往里代点东西： $$ F(1)=\sum_{i=0}^{\infty}P(X=i)=1 $$ 那么 $F^\prime (1)$ 呢？ $$ F^\prime (1)=\sum_{i=0}^{\infty}P(X=i)ix^{i-1}=\sum_{i=0}^{\infty}P(X=i)i=E(X) $$ 再导！ $$ F^{\prime\prime} (1)=\sum_{i=0}^{\infty}P(X=i)\times (i-1)ix^{i-2}=E(X(X-1)) $$ 归纳可知 $F^{(n)}(1)=E(X^{\underline{n}})$，还是挺有用的。 比如，$X$ 的方差就是：$\text{Var}(X)=E(X^2)-E^2(X)=F^{\prime\prime}(1)+F^{\prime}(1)+(F^{\prime}(1))^2$。 现在再来考虑两个 PGF 做卷积的意义，不难发现，和 OGF 类似地，设两个变量分别为 $X,Y$，卷积后的意义为： $$ F(x)G(x)=\sum_{i=0}^\infty P(X+Y=i)x^i $$ ### 应用 可以看[这篇博客](https://zhuanlan.zhihu.com/p/138290902)。 简言之，经典的 PGF 应用是**求随机过程第一次匹配某种模式的期望时间**。 这个东西的常见做法是，设在第 $i$ 次恰好结束的概率是 $f_i$，在第 $i$ 次还没结束的概率是 $g_i$，PGF 分别为 $F(x),G(x)$。 **注意：$f_i+g_i\ne 1$，因为可以在前面已经结束！！！** 用一个经典问题做例子： > 有一个 $m$ 面的骰子，求连续出现 $n$ 次结果相同的期望时间。 可以列出： $$ F(x)+G(x)=xG(x)+1 $$ 这个式子在绝大部分这类题中都适用，它的意义是再投一次是否会结束。 第二个方程是： $$ G(x)\times\left(\dfrac{1}{m}\times x\right)^n=\sum_{i=1}^n F(x)\left(\dfrac{1}{m}\times x\right)^{n-i} $$ 就是考虑做到哪次之后刚好停止，然后为了使两边平衡把剩余的系数也乘上。 这样就可以解出 $F,G$ 了。 来几个题： - [P3334 [ZJOI2013] 抛硬币](https://www.luogu.com.cn/problem/P3334)（改） > 感觉这个题出的很没马，不如改成 $n\le 10^5,P=998244353$。 记 $\displaystyle S_i=\prod_{j=i+1}^n \dfrac{p_{s_i}x}{p_0+p_1}$，那么第二个方程就是： $$ G(x)S_1=\sum_{i=1}^n F(x)S_{i+1}\times \zeta(i) $$ 注意如果前 $[1\cdots i]$ 要想成立，必须满足 $i\in \mathbf{Bd}_n$。所以 $\zeta(i)=[i\in \mathbf{Bd}_n]$。 代入第一个方程中得到的关系： $$ G(x)S_1=\sum_{i=1}^n (x-1)G(x)S_{i+1}\zeta(i)+S_{i+1}\zeta(i)=\left(\sum_{i=1}^n S_{i+1}\zeta(i)\right)\left((x-1)G(x)+1\right) $$ 设 $\displaystyle T=\sum_{i=1}^n S_{i+1}\zeta(i)$，得到： $$ G(x)=\dfrac{T}{S_1+T-Tx} $$ 这题就做完了。 其实这题还可以不多项式求逆，由于只需要求 $F^\prime(1)$ 所以直接代入也是可以的。 具体地，我们把第一个方程两边求导，得到： $$ F^{\prime}(x)+G^{\prime}(x)=xG^{\prime}(x)+G(x) $$ 代入 $x=1$，再代入 $G$ 的式子，可以得到： $$ F^{\prime}(1)=G(1)=\dfrac{T}{S_1} $$ - [P4548 [CTSC2006]歌唱王国](https://www.luogu.com.cn/problem/P4548)：其实和上面的题是一样的。 - 一个牛牛题，可以去上面那篇知乎里找 `[趣题]一个有趣的概率小问题 · 改`。 > 有一个骰子、一个计数器 $cnt$，扔到奇数 $cnt$ 清零，扔到偶数 $cnt$ 加一，求第一次扔到 $n$ 时 $cnt$ 的期望。 主要思路是，这个计数器会多次到达一个位置，所以直接设时间会寄。 我们考虑倒过来，设 $f_x$ 为扔到 $x$ 时结束的概率，$g_x$ 为扔到 $x$ 时没有结束的**期望次数**（就是达到这个位置的次数）。这样： $$ F(x)+G(x)=1+\dfrac{x}{2}G(x)+\dfrac{G(1)}{2} $$ 而： $$ F(x)=\dfrac{x}{n}G(x) $$ 就可以解了，好奇怪的做法啊。 为什么要考虑设这个期望次数呢？因为**计数器会多次到达一个位置**，这个东西本质上就是给转移附上一个系数。 - [P3706 [SDOI2017]硬币游戏](https://www.luogu.com.cn/problem/P3706) 碰到这种普通做法做不来的一定要考虑 PGF，而且 PGF 一般来讲**一定要设成无限维！！！** 如果题中没有明显的无限维就尝试设时间，我们设 $f_k(i)$ 为走 $i$ 步后在 $k$ 停止的概率，$g(i)$ 为走 $i$ 步后仍为停止的概率。 设出 PGF $F_k(x),G(x)$，可以得到： $$ G(x)+\sum_{k=1}^n F_k(x)=xG(x)+1 $$ $$ G(x)\times \dfrac{1}{2^m}=\sum_{i=1}^m \dfrac{1}{2^{m-i}}\left(\sum_{S_k[1\cdots i]\in \text{Suf}(S_t)} F_t(x)\right) $$ 后面那个方程的括号实际上就是 ACAM 中的祖先关系。 我们要解出所有 $F_k(1)$，但是这要求 $G(1)$，但是 $G(1)$ 在第一个方程中约掉了，怎么办呢？ 注意到所有第二组方程中的 $n$ 个式子都是相等的，可以把它们联立，外加一个 $\sum_{k=1}^nF_k(1)=1$ 凑成 $n$ 个方程高斯消元。 ## 题目 得了得了别学了，做点题得勒。 - [P3784 [SDOI2017] 遗忘的集合](https://www.luogu.com.cn/problem/P3784) 就是一个逆欧拉变换的没什么意思的题。 这题模数不是 $998244353$，要三模 MTT。**比赛碰到这种尽可能不写！！！** `double` 的精度掉得太快，只能过 $20$，蚌埠住力！ 于是代码就咕了。 - [P5488 差分与前缀和](https://www.luogu.com.cn/problem/P5488) 刚开始想用一个初等方法做，发现我还是 naive 了。 注意到 $F(x)$ 的前缀和可以被表示为 $\displaystyle \sum_{i=0}^n x^iF(x)=\dfrac{1}{1-x}\times F(x)$，差分就是倒一下。 可以多项式快速幂直接搞，代码咕了。 - [P5219 无聊的水题 I](https://www.luogu.com.cn/problem/P5219) 有标号无根树，考虑 Prufer 序列。 先容斥把问题转成每个点度数不超过 $m$，这就是每个点在 prufer 出现次数不能超过 $m-1$。 于是这个东西就是： $$ [x^{n-2}]\left(\sum_{i=0}^{m-1} \dfrac{x^i}{i!}\right)^n\times (n-2)! $$ 直接多项式快速幂一波带走。[Code](https://www.luogu.com.cn/record/80288919) - [P4451 [国家集训队]整数的lqp拆分](https://www.luogu.com.cn/problem/P4451) 我们发现这就是序列式的组合，因此答案为 $[x^n]\dfrac{1}{1-\dfrac{x}{1-x-x^2}}=[x^n]\dfrac{1-x-x^2}{1-2x-x^2}$。 由于分母中有三项，直接二项式展开是困难的，考虑打开推通项。 设这个东西为 $F(x)$，那么： $$ F(x)=1-\dfrac{x}{x^2+2x-1}=1-\dfrac{x}{(x-\lambda_1)(x-\lambda_2)},\lambda_{1,2}=-1\pm\sqrt{2} $$ 那么： $$ F(x)=1+\dfrac{A}{\lambda_1-x}+\dfrac{B}{\lambda_2-x},(A,B)=\dfrac{\sqrt{2}\mp 1}{2\sqrt{2}} $$ 因此 $\forall x \ge 1,f_x=\dfrac{A}{\lambda_1}\left(\dfrac{1}{\lambda_1}\right)^x+\dfrac{B}{\lambda_2}\left(\dfrac{1}{\lambda_2}\right)^x$。 不会二次剩余，但是 $\bmod 10^9+7$ 意义下的 $\sqrt 2$ 可以暴力求。 - [P4491 [HAOI2018]染色](https://www.luogu.com.cn/problem/P4491) 考虑恰好 $K$ 种出现次数为 $S$ 很难算，不如先二项式反演转为求钦定 $K$ 个出现 $S$ 次的方案数。 这样问题转化成求用 $M-K$ 种颜色填满长为 $N-KS$ 的序列的方案数再乘上一个系数，这是容易用初等方法计算的。 完了式子是一个类似于： $$ g_i=\sum_{j=i}^m(-1)^{j-i}\binom{j}{i}f_j $$ 的形式，移移项可以得到： $$ (-1)^i\times i!\times g_i=\sum_{j=i}^m((-1)^{j}\times j!\times f_j)\times \dfrac{1}{(j-i)!} $$ 这是一个差卷积的形式，可以 NTT 带走。复杂度 $\mathcal O(n+m\log m)$。 - [P5900 无标号无根树计数](https://www.luogu.com.cn/problem/P5900) 感觉是不那么套路的一个题。 直接计数无标号无根树这种混乱的结构显然是困难的，我们看看能不能找到一个合适的分治点。 怎么找到无标号无根树的一个唯一的特征点作为根呢？**重心！！！** 但是一棵树可以有两颗重心啊？ 我们可以先计数只有一颗重心的情况，再加上两边各一棵 $\dfrac{n}{2}$ 的树，容易发现只有这种情况会导致有两颗重心。 这样问题转化为计算无标号有根树，分治特征点就明显了。 设这东西的生成函数是 $F(x)$，有： $$ F(x)=x\mathcal E(F(x)) $$ 直接 $\mathcal O(n^2)$ 完全背包是可行的，但是不够。 尝试来解一下这个东西，考虑： $$ F(x)=x\exp \sum_{j=1}^\infty \dfrac{F(x^j)}{j} $$ 解多项式方程可以牛迭，构造： $$ G(F(x))=x\exp \sum_{j=1}^\infty \dfrac{F(x^j)}{j}-F(x) $$ 考虑求 $G^\prime(F(x))$，有： $$ G^\prime(F(x))=x\exp \left(\sum_{j=1}^\infty \dfrac{F(x^j)}{j}\right)^\prime-F(x) $$ 然后我完全不会，看了题解。 注意到我们可以在解方程前求出 $\displaystyle \sum_{j\ge 2} \dfrac{F(x^j)}{j}$，所以可以直接把它当作一个常数，设： $$ H(x)=\displaystyle \sum_{j\ge 2} \dfrac{F(x^j)}{j} $$ 我们有： $$ G(F(x))=x\exp (H(x)+F(x))-F(x)=x\exp H(x)\times \exp F(x)-F(x) $$ 这时候： $$ G^\prime(F(x))=x\exp H(x)\times \exp F(x)-1 $$ **启示：多项式方程中有 $F(x^j)$ 形式的可以考虑拎出来当常数。** 但是直接这样会被卡常，因为 $\exp$ 太慢了。考虑： $$ F(x)=x\exp \sum_{j=1}^\infty \dfrac{F(x^j)}{j} $$ 这里两边取 $\ln$，得到： $$ \ln \dfrac{F(x)}{x}=\sum_{j=1}^\infty \dfrac{F(x^j)}{j} $$ 然后牛迭式子转成： $$ G(F(x))=\sum_{j\ge 2} \dfrac{F(x^j)}{j}+F(x)-\ln \dfrac{F(x)}{x} $$ 那么 $$ G^\prime(F(x))=1-\dfrac{1}{F(x)} $$ 这样就避免了 $\exp$，但是由于有 $\dfrac{F(x)}{x}$ 所以取模会挂掉。 我们设 $P_0(x)=\dfrac{F_0(x)}{x},P(x)=\dfrac{F(x)}{x},H(x)=\sum_{j\ge 2} \dfrac{F(x^j)}{j}$，那么： $$ F(x)=F_0(x)-\dfrac{H(x)+F_0(x)-\ln P_0(x)}{1-\dfrac{1}{F_0(x)}} $$ 两边同除以 $x$ 得到： $$ P(x)=P_0(x)-\dfrac{H(x)+xP_0(x)-\ln P_0(x)}{x-\dfrac{1}{P_0(x)}} $$ 可以迭代了。 **启示：多项式方程中尽量避免 $\exp$ 的出现。** 还有一种做法是求导然后分治 NTT，不过没什么区别。 - [P4705 玩游戏](https://www.luogu.com.cn/problem/P4705) 直接拆式子，有： $$ \dfrac{1}{nm}\sum_{i=1}^n\sum_{j=1}^m\sum_{t=0}^k \binom{k}{t}x_i^t y_j^{k-t}=\dfrac{k!}{nm}\sum_{t=0}^k\dfrac{\sum_{i=1}^n x_i^t}{t!}\times \dfrac{\sum_{j=1}^m y_j^{k-t}}{(k-t)!} $$ 显然是一个卷积的形式。问题转化为对 $m\in [1,n]$ 求 $\sum_{i=1}^n a_i^m$。 猴嘴巴和我嘴了一个做法，感觉很牛。注意到这个东西就是求： $$ [x^m]\sum_{i=1}^n \sum_{j=0}^\infty (a_ix)^m=[x^m]\sum_{i=1}^n\dfrac{1}{1-a_ix} $$ 这个东西可以分治 NTT，具体做法是每次分成左右两半然后合并 $\dfrac{A}{B}+\dfrac{C}{D}$。 复杂度 $\mathcal O(n\log^2 n)$。 ## 符号化方法 之前讲的都是符号化方法中相对基础的一部分。 先咕着，以后更。 [一篇不错的博客](http://zhylj.cc/index.php/archives/87/)。