[多项式] 生成函数题目集

· · 个人记录

搞一个生成函数计数题目集，，，不定期更新

P3978 [TJOI2015]概率论

题解区有更优美的通项解释方法，然而我只会暴力推式子

设 f_i,g_i 分别表示 i 个点的二叉树形态个数及其叶子总数量，F(x),G(x) 为它们的 \operatorname {OGF}。

经典枚举左子树大小，有：

\begin{aligned} f_i &= \sum_{j=0}^{i-1}f_jf_{i-1-j}+[i = 0]\\ F(x) &= \sum_{i=0}^{+ \infty} ( \sum_{j=0}^{i-1}f_jf_{i-1-j}) x^i+1\\ &= xF^2(x)+1\\ F(x) &= \frac{1 \pm \sqrt{1-4x}}{2x} \end{aligned}

显然当 \lim_{x \to 0} 时 取加号会导致 F(x) \to +\infty，故 F(x)= \dfrac{1- \sqrt{1-4x}}{2x}，实际上这就是卡特兰数的 \operatorname{OGF}。

再看 g_i，依然枚举左子树的大小：

\begin{aligned} g_i &= 2 \sum_{j=0}^{i-1} f_jg_{i-1-j}+[i=1]\\ G(x) &= 2 \sum_{i=0}^{+ \infty} ( \sum_{j=0}^{i-1}f_jg_{i-1-j})x^i+x\\ &= 2xF(x)G(x)+x\\ G(x) &= \frac{x}{1-2xF(x)}\\ &= x (1-4x)^{- \frac{1}{2}}\\ &= x \sum_{i=0}^{+ \infty} \binom{- \frac{1}{2}}{i}(-4x)^i\\ &= \sum_{i=0}^{+ \infty} \binom{2i}{i}x^{i+1} \end{aligned}

最后的推导用到了牛顿二项式定理。
于是我们得到 g_i=\binom{2i-2}{i-1}，ans=\dfrac{g_n}{f_n}=\dfrac{n^2+n}{4n-2} .

CF438E The Child and Binary Tree

一道经典题目。

由于节点数没有限制，直接设 f_i 为权值为 i 时的树的个数，再设 g_i=[i \in \{c_{1...n}\}]，F(x)，G(x) 分别为它俩的 \operatorname {OGF}。
话不多说，暴力列式子硬刚就完了：

\begin{aligned} f_i &= \sum_{j=0}^{i}g_{i-j} \sum_{k=0}^{j}f_kf_{j-k}+[i=0]\\ F(x) &= \sum_{i=0}^{+ \infty} (\sum_{j=0}^{i}g_{i-j} \sum_{k=0}^{j}f_kf_{j-k})x^i+1\\ &= G(x)F^2(x)+1\\ \end{aligned}

我们得到：

G(x)F^2(x)-F(x)+1 = 0

到这里，我们有两种做法：

$$F \equiv F_0-\frac{GF_0^2-F_0+1}{2GF_0-1}$$ 求出至少模 $x^{m+1}$ 意义下的答案即可，复杂度 $O(n \log n)$，没什么好说的。 $2)$ 直接解二次方程 $$F=\frac{1 \pm \sqrt{1-4G}}{2G}$$ 验证 $\lim_{x \to 0}$ 的情况可以舍去加号，即 $F=\dfrac{1 - \sqrt{1-4G}}{2G}$ . 但是注意到 $[x^0]G(x)$ 一定等于 $0$， 似乎没办法求逆了……吗？ $$ \begin{aligned} F &= \frac{1 - \sqrt{1-4G}}{2G}\\ &= \frac{2}{1+ \sqrt{1-4G}} \end{aligned} $$ 分母无理化，神不神仙我不知道，反正我想不到。 这时候我们猛然发现，分母的常数项变成了 $2$ ！结合多项式求根+求逆即可在 $O(n \log n)$ 时间内解决。 ------------------- [射命丸文的笔记](https://www.luogu.com.cn/problem/P4233) 来道 $\operatorname{EGF}$ . 注意到计算点数为 $n$ 的所有竞赛图的总哈密顿回路个数是平凡的，为 $(n-1)! \cdot 2^{\binom{n}{2}-n}$，即选定一个哈密顿回路，计算其在多少个竞赛图中出现。 接下来我们的任务变为了计算出 $n$ 个点的强连通竞赛图数量。 设 $f_i$ 表示 $i$ 个点的强连通竞赛图数量, $g_i=2^{\binom{i}{2}}-[i=0]$，有： $$ f_i = g_i- \sum_{j=0}^{i} \binom{i}{j} f_jg_{i-j} $$ 这是图计数中的常见思路：枚举图的某一特征，具有这一特征的图的计数是平凡的，且每个图有且只有一个特征。比如在经典老番[P4841 城市规划](https://www.luogu.com.cn/problem/P4841)中，我们枚举一号点所在的连通块大小；而在本题中，我们可以先缩点，然后枚举拓扑序最小的强连通分量的大小，只要它的大小小于 $i$，那它一定全是出边，其它的点任意连边，得到的一定是不合法的方案总数，总方案数减去即可。 书接上式，辨认出二项卷积形式，应当使用 $\operatorname{EGF}$。设 $F(x),G(x)$ 分别为 $f_i,g_i$ 的 $\operatorname{EGF}$，接着上面的式子： $$ \begin{aligned} F(x) &= \sum_{i=0}^{+\infty}\frac{g_i- \sum_{j=0}^{i} \binom{i}{j} f_jg_{i-j}}{i!}x^i\\ &= G(x)-F(x)G(x)\\ F(x) &= \frac{G(x)}{G(x)+1}\\ &= 1-(G(x)+1)^{-1} \end{aligned} $$ 结合多项式求逆即可在 $O(n \log n)$ 时间内解决。 -------------------------- [P5219 无聊的水题 I](https://www.luogu.com.cn/problem/P5219) $n$ 个点最大度数恰好为 $m$ 的有标号无根树个数。 每次我们取出树中度数为 $1$ 的编号最小的点，删掉并记录唯一一个与其相邻的节点编号，得到的就是这棵树的 $\operatorname {Pr\ddot{u}fer}$ 序列，一个数在 $\operatorname {Pr\ddot{u}fer}$ 序列中出现的次数 $+1$ 就等于其度数，同样，每次我们将当前度数等于 $1$ 的编号最小的点与当前序列的第一个点连边，删掉序列开头并将对应点的当前度数 $-1$，就得到了该 $\operatorname {Pr\ddot{u}fer}$ 序列对应的树。显然，$\operatorname {Pr\ddot{u}fer}$ 序列建立了所有长度为 $n-2$、值域为 $[1,n]$ 的整数序列与所有 $n$ 个点的有标号无根树之间的**双射**。 在该题中，就是多了度数限制，即每个点最多在 $\operatorname {Pr\ddot{u}fer}$ 序列中出现 $m-1$ 次。设 $\operatorname{EGF} F_m(x)= \sum_{i=0}^{m-1}\frac{1}{i!} x^i$，因为要求最大度数**恰好**为 $m$，所以容斥一下最大度数，答案就是 $[x^{n-2}](F_m^{n-2}(x)-F_{m-1}^{n-2}(x))$ . ~~确实挺水~~ 另外关于 $\operatorname {Pr\ddot{u}fer}$ 序列，一个结论是完全图 $K_n$ 的生成树个数为 $n^{n-2}$，更进一步，将 $m$ 个大小分别为 $a_{1...m}(\sum a_i=n)$ 的联通块联通的方案数为（证明见 [OI Wiki](https://oi-wiki.org/graph/prufer/)）： $$n^{m-2}\prod_{i=1}^ma_i$$ ----------------------- [P7275 计树](https://www.luogu.com.cn/problem/P7275) $\operatorname {Pr\ddot{u}fer}$ 序列与容斥结合。 我们将一条编号连续的链称为连续链，观察到一颗树必然可以剖成若干条长度 $\ge 2$ 的极长连续链。结合刚才 $\operatorname {Pr\ddot{u}fer}$ 序列的结论，我们看似有答案： $$n^{-2}[x^n]\frac{1}{1-\sum_{i\ge 2}nix^i}$$ 然而直接这样算会寄掉，原因是会有若干条连续链拼成一整条更长的连续链，这样我们计算的就不是极长连续链了。 考虑给每个长度的连续链配上容斥系数，这里介绍一种机械的容斥系数求法： 首先要明确，一种长度为 $i$ 的连续链的组成方案的容斥系数为参与构成的连续链的容斥系数的乘积，而我们希望的是找到一组系数 $\langle S_i \rangle$，使得所有组成长度为 $i(i\ge 2)$ 的连续段的方案的系数之和为 $1$，其余为 $0$. 所以我们有： $$\sum_{i\ge 1}S^i=\frac{1}{1-S}-1=\frac{x^2}{1-x}$$ 解得 $S=\frac{x^2}{x^2-x+1}$，运用多项式求逆可以得到 $S=\langle 0,0,1,1,0,-1,-1,0,1,1,0,-1,-1,0,...\rangle$ . 所以真正的答案就是 $$n^{-2}[x^n]\frac{1}{1-\sum_{i\ge 2}S_inix^i}$$ 结合多项式求逆在 $O(n\log n)$ 时间内解决（[杜爷直接用线性递推 $O(\log n)$ 完爆](https://www.luogu.com.cn/blog/qwaszx/solution-p7275)，可是我太蒻了，根本看不出来用线性递推怎么做到 $O(\log n)$）。 ----------------------- [P5434 有标号荒漠计数](https://www.luogu.com.cn/problem/P5434) 首先考虑计算 $n$ 个点带标号仙人掌数量。 设 $f_i$ 为强制钦定一个根节点后的数量，这样每个仙人掌会重复计算 $i$ 次，最后除以 $i$ 即可。 ![](https://pic.imgdb.cn/item/629d60960947543129b76e86.png) 如图，对于一个根节点，其可以接入若干个单个的仙人掌，也可以接入若干个仙人掌串。那么我们可以得到 dp 式子： $$ \begin{aligned} f_i= \sum_{j=0}^{i-1} &\left(\sum_{k=0}^{j} \frac{1}{k!} \sum_{p_1+...+p_k=j,p_x>0} \binom{j}{p_1,...,p_k} \prod_{x=1}^{k}f_{p_x} \right) \cdot\\ &\left( \sum_{k=0}^{i-1-j} \frac{1}{k!} \sum_{p1+...+p_k=i-1-j, p_x>0} \binom{i-1-j}{p_1,...,p_k} \prod_{x=1}^{k} \frac{1}{2} \sum_{l=2}^{p_x} \sum_{q_1+...+q_l=p_x, q_y>0} \binom{p_x}{q_1,...,q_l} \prod_{y=1}^{l} f_{q_y} \right) \end{aligned} $$ 从中辨认出多项式 $\exp$ 以及多项卷积，选用 $\operatorname{EGF}$，设 $F(x)$ 为 $f_i$ 的 $\operatorname{EGF}$，有： $$ \begin{aligned} F&=x \cdot \exp F \cdot \exp \left(\frac{1}{2} \sum_{i=2}^{+ \infty} F^i \right)\\ &=x \cdot \exp \left(F+\frac{F^2}{2}\frac{1}{1-F} \right)\\ &=x \cdot \exp \left(\frac{2F-F^2}{2-2F} \right) \end{aligned} $$ 这时候生成函数强大的功能体现得淋漓尽致，我们只需要大力牛顿迭代即可~~就是这么大坨东西求起导来比较恶心~~。 最后得到这个式子： $$ F \equiv F_0-\frac{x\exp \left(\frac{2F_0-F_0^2}{2-2F_0} \right)-F}{x\exp \left(\frac{2F_0-F_0^2}{2-2F_0} \right)\left(\frac{1}{2}+\frac{1}{2(F_0-1)^2} \right)-1} $$ 最后 $F$ 的第 $i$ 项除以 i，荒漠个数即为 $n![x^n]\exp F$ . ----------------- [P5401 [CTS2019] 珍珠](https://www.luogu.com.cn/problem/P5401) 经典题目。 不难发现能够得到 $m$ 个合法瓶子当且仅当出现奇数次的变量个数 $\le n - 2m$，那么我们可以暴力写出 $\operatorname{EGF}$ ： $$ ans=\sum_{i=0}^{n-2m}\binom{D}{i} [x^n]\left( \frac{e^x+e^{-x}}{2} \right)^{D-i}\left( \frac{e^x-e^{-x}}{2} \right)^i $$ 然而这样会发现 $[x^n]\left( e^x+e^{-x} \right)^{D-i}\left( e^x-e^{-x} \right)^i$ 根本没法算，展开都难。 这种情况下可以考虑二项式反演，它可以把这个东西变成 $[x^n](e^x)^{D-i}\left( e^x-e^{-x} \right)^i$ 这样就只需要展开一个二项式了。 套路地设 $f_k$ 为至少有 $k$ 个出现奇数次的变量的方案数，$g(k)$ 则是恰好有 $k$ 个。 那么有： $$ \begin{aligned} g(k)&=\sum_{i \ge k} \binom{i}{k}(-1)^{i-k}f(i)\\ f(k)&=\binom{D}{k}n![x^n](e^x)^{D-k}\left( \frac{e^x-e^{-x}}{2} \right)^k\\ &=\binom{D}{k}2^{-k}n![x^n](e^x)^{D-k}\sum_{i=0}^{k}\binom{k}{i}(-1)^i(e^x)^{k-i}e^{-ix}\\ &=\binom{D}{k}2^{-k}\sum_{i=0}^k\binom{k}{i}(-1)^in![x^n]e^{\left(D-2i \right)x}\\ &=\binom{D}{k}2^{-k}\sum_{i=0}^k\binom{k}{i}(-1)^i(D-2i)^n \end{aligned} $$ 利用二项卷积即可在 $O(D\log D)$ 时间内解决。 ------------------ [P4389 付公主的背包](https://www.luogu.com.cn/problem/P4389) 我们知道，多项式 $\exp$ 的组合意义可以理解为将 $n$ 个带标号小球放入若干个无标号盒子（每个盒子非空）中的方案数，这点在上一题荒漠计数中就有体现，而当去掉小球编号时，我们就要引入一个叫做 $\operatorname{Euler}$ 变换的东西，记作 $\mathcal{E}(F(x))$，它是这样定义的： $$\mathcal{E}(F(x))=\prod_{i=1}^{+\infty}\frac{1}{(1-x^i)^{[x^i]F(x)}}$$ 其中 $[x^i]F(x)$ 表示大小为 $n$ 的集合有多少种，实际上这就是完全背包的生成函数，$i$ 代表物品体积，$[x^i]F(x)$ 代表体积为 $i$ 的物品有多少种，最后卷起来就行，$[x^i]\mathcal{E}(F(x))$ 就代表了物品总体积为 $i$ 的选择方案数。 然而我们发现这个定义式无法在较低复杂度内算出来，所以我们要把它化成更实用的形式，记 $G(x)=\mathcal{E}(F(x))$： $$ \begin{aligned} \ln G(x) &= -\sum_{i=1}^{+\infty} [x^i]F(x)\ln(1-x^i)\\ (\ln G(x))' &= \sum_{i=1}^{+\infty} \frac{[x^i]F(x) \cdot ix^{i-1}}{1-x^i} \\ &=\sum_{i=1}^{+\infty} [x^i]F(x) \cdot ix^{i-1}\sum_{j=0}^{+\infty} x^{ij}\\ &=\sum_{i=1}^{+\infty} \sum_{j=0}^{+\infty}[x^i]F(x) \cdot ix^{i (j+1)-1}\\ \ln G(x) &= \sum_{i=1}^{+\infty} \sum_{j=0}^{+\infty}[x^i]F(x) \frac{x^{i (j+1)}}{j+1} \\ &= \sum_{j=1}^{+\infty}\frac{1}{j} \sum_{i=0}^{+\infty}[x^i]F(x)(x^j)^i\\ &= \sum_{i=1}^{+\infty}\frac{F(x^j)}{j}\\ G(x) &= \exp \left(\sum_{i=1}^{+\infty}\frac{F(x^i)}{i}\right) \end{aligned} $$ 这样我们想得到模 $x^m$ 意义下的 $\mathcal{E}(F(x))$ 只需要 $O(m \ln m)$ 计算 $\sum_{i=1}^{+\infty}\frac{F(x^i)}{i}$，$O(m \log m)$ 计算 $\exp$ 即可。 --------------------- 2022 山东一轮省队集训【整数拆分（partition)】 根据题意，不难写出答案： $$[x^n]\frac{1}{(1-x)^{k+1}\prod_{i \ge 1}(1-x^{m^i})^k}$$ $n,m$ 都在 $10^{18}$ 量级，观察到这就是线性递推的形式，直接套用线性递推的处理方式： $$ \begin{aligned} &[x^n]\frac{P(x)}{(1-x)^{c}\prod_{i \ge 1}(1-x^{m^i})^k}\\ =&[x^n]\frac{P(x)\left(\frac{1-x^m}{1-x}\right)^c}{(1-x^m)^{c+k}\prod_{i\ge 2}(1-x^{m^i})^k}\\ =&[x^{\lfloor \frac{n}{m} \rfloor}]\frac{\left[P(x)\left(\frac{1-x^m}{1-x}\right)^{k+1} \right]_{n \bmod m}}{(1-x)^{c+k}\prod_{i \ge 1}(1-x^{m^i})^k} \end{aligned} $$ $[F]_r$ 表示提取 $F$ 的 $kr(k\in \mathbb{N})$ 项得到的多项式~~自个发明的，不知道有没有正式记法~~，注意这里计算分子时先计算 $P(x)(1-x)^{-c}$ 即可做到每层 $O(c^2)$ 时间花费，当 $n=0$ 时直接返回 $[x^0]P(x)$ 即可，总复杂度 $O(k^2\log^3n)$。 --------------------- [AGC060D Same Descent Set](https://atcoder.jp/contests/agc060/tasks/agc060_d) 这题主要是容斥，GF部分是次要的。 设 $f(S)$ 表示下降集为 $S$ 的集合个数，$g(S)$ 表示下降集是 $S$ 的子集的排列个数。 根据子集反演，有： $$ \begin{aligned} g(S) &= \sum_{T \subset S} f(T)\\ f(S) &= \sum_{T \subset S} (-1)^{|T|-|S|} g(T) \end{aligned} $$ 接下来是推式子时间： $$ \begin{aligned} \sum_{S} f^2(S) &= \sum_{S} (\sum_{T \subset S} (-1)^{|T| - |S|} g(T))^2\\ &= \sum_{S} \sum_{T_1 \subset S} (-1)^{|T_1| - |S|} g(T_1) \sum_{T_2 \subset S} (-1)^{|T_2| - |S|} g(T_2)\\ &= \sum_{S} \sum_{T_1, T_2 \subset S} (-1)^{|T_1| + |T_2|} g(T_1)g(T_2)\\ &= \sum_{T_1, T_2} (-1)^{|T_1|+|T_2|} g(T_1)g(T_2) \sum_{S \supseteq T_1 \cup T_2 } 1\\ &= \sum_{T_1, T_2} (-1)^{|T_1|+|T_2|} g(T_1)g(T_2) 2^{n-1-|T_1 \cup T_2|}\\ &= \sum_{T_1, T_2} (-1)^{|T_1|+|T_2|} g(T_1)g(T_2) 2^{n-1-|T_1|-|T_2| + |T_1 \cap T_2|}\\ &= 2^{n+1} \sum_{T_1, T_2} (-1)^{|T_1|+|T_2|} g(T_1)g(T_2) 2^{-|T_1|-1-|T_2|-1} \sum_{S \subset |T_1 \cap T_2|} 1\\ &= 2^{n+1} \sum_{S} \left (\sum_{T \supseteq S} \left ( -\dfrac{1}{2} \right )^{|T|+1}g(T) \right )^2\\ &= 2^{n+1}(n!)^2 \sum_{ s_1+s_2+\dots +s_{m}=n, s_i>0 } \prod_{i=1}^m h^2(s_i)\\ h(n) &= \sum_{ s_1+s_2+\dots +s_{m}=n, s_i>0 } \left( -\dfrac{1}{2} \right)^{m} \dfrac{1}{\prod_{i=1}^m s_i!}\\ A(x) &= \sum_{i \ge 1} -\dfrac{1}{2i!}x^i\\ H'(x) &= \sum_{i \ge 1} h(i)x^i\\ &= \sum_{i \ge 1} A^i(x)\\ &= \dfrac{A(x)}{1-A(x)}\\ H(x) &= \sum_{i \ge 0} h^2(i)x^i\\ ans &= 2^{n+1}(n!)^2 [x^n] \sum_{i \ge 1} H^i(x) = 2^{n+1}(n!)^2 [x^n] \dfrac{H(x)}{1-H(x)} \end{aligned} $$ 过程中将集合并的大小转化为交的大小是关键一步。 使用多项式求逆即可在 $O(n \log n)$ 时间内解决。 -------------------------------- [bzoj3305](https://hydro.ac/d/bzoj/p/3305) 不难设计 dp：$f_{i,j}$ 表示考虑了前 $i$ 个位置，左括号减右括号数量为 $j$，有转移： $$ f_{i,j} = f_{i,j-1} + (j+1)f_{i,j+1} $$ 设 $F_{i}(x) = \sum_{j \ge 0} f_{i,j}x^j$，可以得到： $$ F_{i} = xF_{i-1}+F'_{i-1} $$ 两侧同时乘上 $e^{\frac{x^2}{2}}$，设 $G_i = e^{\frac{x^2}{2}} F_{i}$，恰好能配出来： $$ G_i = G'_{i-1} $$ $G_0 = e^{\frac{x^2}{2}}$，$2n$ 阶导的常数项即为 $\dfrac{(2n)^{\underline{n}}}{2^{n}}$。 upd:GF太不优美了，JOISC 2023 D1T2 有完美的组合解释。