科技学习系列 V 符号化方法和拉格朗日反演

Edward1002001 · 2024-01-14 17:34:15 · 算法·理论

OGF 部分

定义：A=\sum_{a\in \widehat A} z^{|a|}，那么 A 是组合类 \widehat A 的生成函数。这里不用普遍使用的花体是因为手写写不出花体。

有很多不严谨的地方，以实用为主。

一些基础无标号类。

记 \epsilon 为中性对象，\widehat E=\{\epsilon\} 为中性类，那么 E=1。

记 \bullet 为原子对象，\widehat Z=\{\bullet\} 为中性类，那么 Z=z。

一些无标号构造。

无交并.\widehat A \cup \widehat B=A+B

笛卡尔积.\widehat A \times \widehat B=AB

一些部分构造.

速记： \text{MSET} 和 \text{CYC} 可以用 Polya 原理计算，然后 \text{PSET} 相当于给 \text{MSET} 每个 A(z^\text{even}) 上乘 -1.

以下是部分例题

二叉树.\widehat S=\widehat E + (\widehat S \times \widehat Z \times \widehat S)

无标号有序有根树.\widehat S=\widehat E + (\widehat Z \times \text{SEQ}(\widehat S))

无标号有根树.\widehat S=\widehat Z \times \text{MSET}(\widehat S)

无标号无根树.\widehat T=\widehat S - \text{PSET}_{2}(\widehat S)

注意 \text{PSET}_{2}(\widehat S) 代表选择两个相异子树拼起来的方案，那么根不是重心的情况就会恰被减掉，而两个等价树相拼的话第一个式子只会计算一次，这样的情况就不会被减掉。

包含 abb 的所有字符串.写出正则表达式 b*aa*b(aa*b)*b(a|b)*，则有 \widehat S=\text{SEQ}(\widehat Z) \times \widehat Z \times \text{SEQ}(\widehat Z) \times \widehat Z \times \text{SEQ}(\widehat Z \times \text{SEQ}(\widehat Z) \times \widehat Z) \times \widehat Z \times \text{SEQ}(\{0,1\})

Longest run(不包含连续 k个 0 的 01 串).\widehat L_{<k}=\text{SEQ}_{<k}(\{0\}) \times \text{SEQ}(\{1\} \times \text{SEQ}_{<k}(\{0\}))

串-并联网络.\widehat S=\widehat Z+\text{SEQ}_{k\ge 2}(\widehat P),\widehat P=\widehat Z+\text{MSET}_{k \ge 2}(\widehat S),\widehat{Ans}=\widehat S+\widehat P-\widehat Z

红黑树,生成函数指标为叶子个数.\widehat R=\widehat Z+(\widehat R \circ \{2,3,3,4\})

分拆数.\widehat L=\text{MSET}(\text{SEQ}_{\ge 1}(\widehat Z))

烷基计数.\widehat L=\widehat E+(\widehat Z \times \text{MSET}_3(\widehat L))

每个点的子树个数在 \Omega 内的树.记 \phi(z) 为 \sum\limits_{a\in\Omega}z^a，\widehat L=\widehat Z \times \text{SEQ}_{\Omega}(\widehat L)，L=z\phi(L)

被括号包含.\widehat T=\widehat Z+\text{SEQ}_{\ge 2}(\widehat T)

系数在质数阶有限域 F_p 内的素多项式. 考虑所有首一多项式的组合类 \widehat P=\text{SEQ}(\widehat Z)，则 \widehat P=\text{MSET}(\widehat Q)，\widehat Q 即为所求

无标号有根仙人掌.\widehat P=\widehat Z \times \text{MSET}(\widehat P+\text{SEQ}_{\ge 2}(\widehat P)/2)

每个环的大小在 \Omega 内的无标号有根仙人掌.\widehat P=\widehat Z \times \text{MSET}(\widehat P+\text{SEQ}_{\Omega-1}(\widehat P)/2)

EGF 部分

一些基础无标号类。

记 \epsilon 为中性对象，\widehat E=\{\epsilon\} 为中性类，那么 E=1。

记 ① 为原子对象，\widehat Z=\{①\} 为中性类，那么 Z=z。

无交并.\widehat A \cup \widehat B=A+B

有序积.\widehat A \times \widehat B=AB

Boxed-Product 构造.\widehat A^{\square}\star \widehat B=\int A'Bdz

Boxed-Product 构造表示钦定最小元在 \widehat A 中的有序积方案

以下是部分例题

错位排列.\widehat D=\text{SET}(\text{CYC}_{\ge 2}(\widehat Z))=\frac{e^{-z}}{1-z}

有标号连通图.记有标号图的组合类为 \widehat F，则 \widehat G=\text{SET}^{-1}(\widehat F)

贝尔数.\widehat B=\text{SET}(e^z-1)

基环树.设有根树的组合类为 \widehat T,则 \widehat G=\text{CYC}_{\text{flip},\ge 3}(\widehat T)=\frac{1}{2}(-\ln(1-z)-A-A^2/2)

有标号荒漠计数.\widehat G=\widehat Z \times \text{SET}(\widehat G+\text{SEQ}_{\ge 2}(\widehat G)/2),\widehat{Ans}=\text{SET}(\Theta^{-1}G)

仙人掌少女.\widehat G=\widehat Z \times \text{SET}(\widehat G+\text{SEQ}_{\Omega}(\widehat G)/2),\widehat{Ans}=\text{SET}(\Theta^{-1}G)

拉格朗日反演

若 F(G(z))=z，且 f_0=0，则 [z^n]G(z)=\frac{1}{n}[z^{-1}](1/F(z))^n=\frac{1}{n}[z^{n-1}](z/F(z))^n

若 F(G(z))=z，则 [z^n]H(G(z))=\frac{1}{n}[z^{n-1}]H'(z)(z/F(z))^n

若 F(G(z))=H(z)，则 [z^n]G(z)=\frac{1}{n}[z^{n-1}]H'(z)(z/F(z))^n

特殊地，[z^n]G(z)^k=\frac{k}{n}[z^{n-k}](z/F(z))^n

另类拉格朗日反演.

若 F(G(z))=z，则 [z^n]G(z)=[z^{n-1}]F'(z)(z/F(z))^{n+1}，且 [z^n]H(G(z))=[z^n]H(z)F'(z)(z/F(z))^{n+1}

特殊地，[z^n]G(z)^k=[z^{n-k}]F'(z)(z/F(z))^{n+1}

一个基于多项式的证明[10].

首先我们有引理 若 F(z) 无常数项而有一次项则 [z^{-1}]F'F^k=[k=-1]，考虑 k \neq -1 时左边为 (F^{k+1})'/(k+1) 即得证。

考虑若 G(F(z))=H(z)，则有

另一方面，考虑不进行两侧求导而是直接把导数乘上去，得到另类拉格朗日反演。

一个基于留数定理的证明(来自 jerryTcl 和 [19])

直接导出了另类拉格朗日反演，其中 C 是围绕着 z=0 的微小圆弧围道，而 C' 是其复合了 F(z) 的结果。由于 F(z) 的最低次项为 z，可以近似为同样半径的微小圆弧。

进行换元积分可以导出原版拉格朗日反演：

注：以上的换元积分可类比 \int_a^bu\text{d}v=[uv]_a^b-\int_a^bv\text{d}u，前一项消去是由于 C' 为闭合环路，且H(z)F(z)^{-n} 为单值函数，于是起始和末尾值一致并抵消。

有标号有根树.F=z\exp F，故 z=\frac{F}{\exp F}，[n!z^n]F(z)=\frac{1}{n}[z^{n-1}](\exp z)^n=\frac{n^{n-1}}{(n-1)!n}=n^{n-1}

有标号仙人掌.G=z\exp(\frac{2G-G^2}{2-2G})，[z^n]G(z)=\frac{1}{n}[z^{n-1}](\exp(n\frac{2z-z^2}{2-2z}))，注意到后者是微分有限的，则可对一项 O(n) 求出.

例题

其中很大一部分来源于[7]，按牛顿迭代法规定一些多项式操作的常数如下：

注：下列题目的常数均未计算 \text{MSET} 变换时 O(n\ln n) 累加的时间复杂度。

1. LGOJT4451 [国家集训队] 整数的lqp拆分

题意简述：设 f_n 为下标从一开始的斐波那契数列，求 \sum\limits_{\sum a_i=n,a_i>0} \prod f_{a_i} \bmod 10^9+7，其中 a_i 有顺序之分，n \le 10^{10000}。

一句话题解：令 F=\frac{x}{1-x-x^2},\widehat{Ans}=\text{SEQ}(\widehat F)，注意到 \sqrt 2 \equiv 59713600 \pmod{mod}，直接快速幂计算即可，复杂度 O(\log n)。

2. LGOJT7592 数树 [2021 CoE-II E]

题意简述：设每个非叶节点有 k_1 或 k_2 个子节点的树权值为 k_1 叉点个数乘 a 加上 k_2 叉点个数乘 b，求所有 n 个点的该类树权值期望模 998244353，k_1 \neq k_2,1 \le k_1,k_2 < n \le 10^7。

一句话题解：注意到 k_1 的点数确定后 k_2 叉的点数叶随之确定了，因为叶节点个数也只与其相关，令 y 计数 k_1 叉点的个数，则 G=x(yG^{k_1}+G^{k_2}+1)，拉格朗日反演有 [x^n]G=\frac{1}{n}[x^{n-1}](yx^{k_1}+x^{k_2}+1)^n，枚举取 x^{k_1} 的个数，则剩下那部分最多有一项，这样使用组合数计算即可，复杂度 O(n)。

3. LGOJT3784 [SDOI2017] 遗忘的集合

题意简述：求字典序最小的 \widehat F，使得 \text{MSET}(\widehat F)=S，1 \le \text{max}(S) < 2^{18},10^6 < p < 2^{30},p \in \mathbb{P}

一句话题解：按上文所述计算 \text{MSET}^{-1}(\widehat S) 即可，使用 MTT 下的多项式 ln，复杂度 O(n\log n)，常数 4.5。

4. LGOJT5900 无标号无根树计数

题意简述：计数无标号无根树，答案对 998244353 取模，1 \le n \le 2*10^5

一句话题解：按上文所述计算，对 \ln(F/z)-P(z)-z(F/z)=0 使用牛顿迭代，其中 P(z)=\acute{\text{Eul}}(F)，核心公式为 Fs=F0-(ln(F0)-P(z)-zF0(z))/(1/F0-z)。注意求 ln 时可以顺便求出 F0 的逆元，最后一步不需要卷积出每一项，手动容斥一下，复杂度 O(n\log n)，常数 9.5。

5. LGOJT5434 有标号荒漠计数

题意简述：计数有标号荒漠(仙人掌森林)，答案对 998244353 取模，3 \le n \le 10^5

做法一：按上文所述计算，那么有标号有根仙人掌偏移一位后的生成函数满足 F_s=\exp(\frac{2zF_s-z^2F_s^2}{2-2zF_s})，对 ln(F_s)-(\frac{z^2F_s^2}{2-2zF_s}+zF_s)=0 使用牛顿迭代，然后去根，再进行 exp，即可得到荒漠的结果，复杂度 O(n\log n)，常数 18+5/6。

做法二：我们试图提取一项系数，但是我们注意到 exp 过程关联了仙人掌的每项系数，而且那个 \Theta^{-1} 妨碍了我们提取系数，考虑设 H(F(z))=\Theta^{-1}F(z) [12,13]，那么求导有 F(x)=xF'(x)H'(F(x))，设 E(x)=\frac{2x-x^2}{2-2x}，注意到

又 H'(F(x))=F(x)/(xF'(x))=1-F(x)E'(F(x))，故 H'(x)=1-xE'(x)。而且，H(x)=\int H'(x)=x-xE(x)+B(x)，不过 H(x) 在后续推导中除了导出微分有限性质后就不需要计算了。

令 \widehat H=\exp H，那么，[x^n]\widehat H(F(x))=\frac{1}{n}[x^{n-1}]\widehat H'(x)\exp nE(x)=\frac{1}{n}[x^{n-1}]\exp(H(x)+nE(x))H'(x)

这时可以直接算出 H',H,E，然后使用多项式解决，复杂度 O(n \log n)，常数 7。

做法三：注意到 E(x) 是代数的，H'(x) 是微分有限的，经计算 B(x)=1/4(-2x+x^2-2\ln(1-x))，因取 H(x)=\exp(x-E(x)+1/4(-2x+x^2)) (1-x)^{-1/2} 就是微分有限的。下面我们手动计算整式递推式，以锻炼我们的数学功底。

令 P(x)=\exp(H(x)+nE(x))H'(x)，则

求得 E(x)=\frac{2x-x^2}{2-2x},E'(x)=\frac{1}{2}\left(\frac{1}{(x-1)^2}+1\right),E''(x)=-\frac{1}{(x-1)^3}，代入有

设 A(x)=-\frac{x^3}{2}+2x^2-3x+1,B(x)=x^2+2-2x,C(x)=-\frac{x^4}{2}+2x^3-\frac{5}{2}x^2+2x-1，计算得知括号后半部的常数项也恰为 A(x)，则

其中，(x-1)^2A(x)=-\frac{x^5}{2}+3x^4-\frac{15}{2}x^3+9x^2-5x+1,A(x)B(x)=\frac{1}{2}(-x^5+6x^4-16x^3+22x^2-16x+4),C(x)+A(x)^2=\frac{1}{4}(x^6-8x^5+26x^4-44x^3+42x^2-16x)

那么，左侧最高项五次，右侧最高项六次，这是一个涉及 p_{k-7} 的整式递推，同时注意到 [x^{k-t}]P'(x)=(k-t+1)p_{k-t+1}，取 [x^{k-1}] 项则有：

之前一直看大家的前几项计算量好大，不过其实只给定 p_0=1 的话正确性也是对的，因为毕竟整个微分方程只有 p_0 无法确定嘛。

6. 9019T7007 仙人掌少女

题意简述：计数有标号，环长在 \Omega 内的荒漠，答案对 998244353 取模，1 \le n \le 2*10^5。

一句话题解：按上一题做法二进行，将 \text{SEQ} 换成 \text{SEQ}_{\Omega} 即可，复杂度 O(n \log n)，常数 7。

7. LGOJT5401 [CTS2019] 珍珠

题意简述：有 n 个在范围 [1,D] 内的整数均匀随机变量，求至少能选出 m 个瓶子，使得存在一种方案，选择一些变量，并把选出来的每一个变量放到一个瓶子中，满足每个瓶子都恰好装两个值相同的变量的方案数，答案对 998244353 取模，0 \le m \le 10^9,1 \le n \le 10^9,1 \le D \le 10^5。

做法一：计入答案相当于 \sum_{i\in [1,D]} \lceil cnt_i/2 \rceil \ge m，实际上这能转化成 \sum_{i\in [1,D]} \text{isodd}_i \le n-m，这就相当于 2^{-D}[x^n/n!]\sum{i \le k}\binom{D}{i}(e^x-e^{-x})^i(e^x+e^{-x})^{D-i}，在这里已经可以二项式定理第一次卷积出 [(e^x+e^{-x})^i]F，第二次卷积出 [e^x]F 做到 O(n\log n)，常数 2。

做法二：在此处换元并变换得到 e^{-Dx}G(e^{2x})，其中 G(x)=\sum_{i \le k}(x-1)^i(x+1)^{D-i}，求导递推即可，复杂度 O(D)。

8. LGOJT6049 燔祭

题意简述：计数带点权有标号无序有根树 T，使得每个点的点权为 [1,m] 内整数，且父亲的点权大于等于儿子，答案对 998244353 取模，1 \le n \le 400,1 \le m < mod。

一句话题解：注意到 n 确定时答案是关于 m 的 n 次多项式。考虑求出 m\in [0,n] 的点值。那么我们有 \widehat{F_m}=\text{SET}(\sum\limits_{i\le m}\widehat{F_i})，进行 O(n^2) 递推即可。也可以 O(n^2 \log n) 牛顿迭代，但没写。

9. UOJT50 [UR #3] 链式反应

题意简述：一个节点被 A 型触发后可以没有儿子或有 c 个 B 型儿子和恰两个 A 型儿子，并且每个点的儿子标号必须比自己大，求有多少种方案使得所有 n 个节点恰形成一颗以 1 为根的树，其中允许的 c 是一个输入给定的集合。你需要输出 [1,n_{max}] 内所有的答案，对 998244353 取模，1 \le n \le 2*10^5。

做法一：\widehat T=\widehat Z{\square} \star (\widehat E+\text{SET}_{c}(\widehat Z)\text{SET}_2(\widehat T))，那么 T=\int (1+S(z)T(z)^2/2)\mathrm{d}z。其中 S(z) 是 c 的 EGF。那么 T'=1+ST^2/2，可以半在线卷积 O(n \log^2 n) 求出。

做法二[14]：有了上面的式子，考虑设 H(z)=S(z)z^2/2+1，并设 F_0 \equiv F \pmod{x^{\lceil x/2 \rceil}}，泰勒展开得 F'=H(F_0)+(F-F_0)H'(F_0)，即 F'-H'(F_0)F=H(F_0)+F_0H'(F_0)

令 R=\exp(-\int H'(F_0)\mathrm{d}z)，则 R'=-H'(F_0)R

两侧同乘 R，则 (FR)'=H(F_0)-F_0H'(F_0)，那么 F=\frac{\int (H(F_0)-F_0H'(F_0))R\mathrm{d}z}{R}。

在此题，即为 R=\exp(-\int S(z)F_0(z)\mathrm{d}z),F=\frac{\int (1-SF_0^2/2)R\mathrm{d}z}{R}，牛顿迭代复杂度 O(\log n)，常数 21.5。

10. LGOJT6295 有标号 DAG 计数

题意简述：分别对于 [1,n] 内的 n 计数 n 节点有标号弱联通 DAG，对 998244353 取模，1 \le n \le 2*10^5。

题解：考虑计数出所有 DAG 的方案数，然后取 ln 即得到 DAG。

考虑枚举零度点个数 i，则 g_i 为对某个确定的 n，恰有 i 个零度点的方案数，则 \binom{n}{i}2^{i(n-i)}f_{n-i}=\sum_{j\ge i} \binom{j}{i} g_j，故 g_i=\sum_{j\ge i} (-1)^{j-i}\binom{j}{i} \binom{n}{j}2^{j(n-j)}f_{n-j} ，故

故而，设 F(z)=\sum\limits_i f_iz^i/(2^{\binom{i}{2}}i!)，而 G(z)=\sum\limits_i (-1)^{i+1}/(2^{\binom{i}{2}}i!)，则 F(z)=F(z)G(z)+1，故 F(z)=\text{SEQ}(G)

然后对 f 的 EGF 做 ln 即可，复杂度 O(n \log n)，常数 4。

11. LGOJT7364 有标号二分图计数

题意简述：分别对于 [1,n] 内的 n 计数 n 节点有标号二分图，对 998244353 取模，1 \le n \le 10^5。

一句话题解：考虑所有带黑白染色的有标号二分图方案数 g_n=\sum\limits_{0\le i \le n}\binom{n}{i}2^{i(n-i)}，设其 EGF 为 G，那么 F=\exp(1/2 \ln(G))=\sqrt G，因为二分图的每个联通块恰有两种黑白染色方案。前面用 g_n/(2^{\binom{i}{2}}i!) 式生成函数计算，然后进行多项式 sqrt 即可，复杂度 O(n \log n)，常数 5.5。

12. LGOJT4233 射命丸文的笔记

题意简述：分别对于 [1,n] 内的 n 求 n 个点的所有有哈密顿回路的有标号竞赛图中，哈密顿路径数量的期望，对 998244353 取模，1 \le n \le 10^5。

一句话题解：哈密顿回路总条数是 (n-1)!2^{\binom{n-1}{2}}，考虑计数有哈密顿回路的有标号竞赛图，强连通竞赛图有哈密顿回路[15]，又有竞赛图是一列强连通竞赛图的组合，因此 F=1-1/G，其中 G=\sum 2^{\binom{n}{2}}/n!，F 是 EGF。复杂度 O(n \log n)，常数 1.5。

13. LGOJT5828 边双连通图计数

题意简述：恰五次求 n 个点的有标号边双连通图个数，对 998244353 取模，1 \le n \le 10^5。

一句话题解[16]：设 D 是一般有根联通图的生成函数，b_i 是有根有标号边双的个数，那么 D=\sum\limits_{i=1} (b_ix^i/i!)\exp(D)^i，即 D=B(x\exp D)，这是由于根所在边双上的每个点都能挂一个一般有根图集合，于是由 B(x\exp D(x))=D(x) 拉格朗日反演得到 [x^n]B(z)=\frac{1}{n}[x^{n-1}]D'(x)\exp(nD(x))，需要注意的是 b_n=n![x^n]B(z)=(n-1)![x^{n-1}]D'(x)\exp(nD(x))，然后还要再除以 n 以去掉有根。使用多项式操作，复杂度 O(n \log n)，若只求一次，则常数 9.5。

14. LGOJT5829 点双连通图计数

题意简述：恰五次求 n 个点的有标号点双连通图个数，对 998244353 取模，1 \le n \le 10^5。

一句话题解[17]：与上一题类似的，设 D 是一般有根联通图的生成函数，b_i 是有根有标号 i+1 个点的点双个数，那么 D=x \exp B(D(x))，这是由于根所在的一些点双上的每个其他点都能挂一个(包括其的)有根图，而根可以由若干个点双包含，于是拉格朗日反演得到 [x^n]B(z)=\frac{1}{n}[x^{n-1}]D'(x)(x/D(x))^{n+1}，需要注意 EGF 的阶乘和有根无根的转化。使用多项式操作，复杂度 O(n \log n)，若只求一次，则常数 12。

15. LOJT6363 [地底蔷薇]

题意简述：给定集合 S，请你求出 n 个点的所有极大点双连通分量的大小都在 S 内的不同简单无向连通图的个数对 998244353 取模的结果，1 \le n,(\sum\limits_{x\in S} x) \le 10^5。

一句话题解：D=x \exp S(D(x))，其中 S=\sum\limits_{x\in S} b_iz^i/i!，于是于是拉格朗日反演得到 [x^n]D(z)=\frac{1}{n}[x^{n-1}]\exp(nS(x))，需要注意 EGF 的阶乘和有根无根的转化。使用多项式操作，复杂度 O(n \log n)，常数 12+6=18。

16. LGOJT5448 [THUPC2018] 好图计数

题意简述：求 n 个点的无标号好图个数，其中好图的定义为，单点是好的，若干个好图分别作为联通块所形成的图是好的，好图的补图是好的。对 p 取模，1 \le n \le 23333,2^{29}<p<2^{30},p \in \mathbb{P}。

解法一：设 G 为好图的生成函数，G_{\text{con}} 为联通好图的生成函数，并令 g_0=g_{\text{con},0}=0，注意到若 n>1 则好图数量恰为联通好图数量的两倍，则有 2\widehat {G_{\text{con}}}=\text{MSET}(\widehat{G_{\text{con}}})，即 2G_{\text{con}}=\exp(\text{Eul}(G_{\text{con}}))，可以 O(n^2) 递推。

解法二：考虑 2G_{\text{con}}=\exp(\acute{\text{Eul}}(G_{\text{con}})+G_{\text{con}})，进行多项式牛顿迭代，复杂度 O(n\log n)，需要 MTT，常数 20，实测比解法一慢。

17. LOJT6684 有根无标号奇树计数

题意简述：定义一棵有根树为奇树，当且仅当其所有叶子深度都为奇数（根节点深度为 1），其中深度为奇数的点称作奇点。对 [1,n] 内的 n 求恰有 n 个奇点的无标号奇树个数，对 998244353 取模，1 \le n \le 10^5。

解法一：设 \widehat T,\widehat{Z_0},\widehat{Z_1} 分别为奇树，偶点，奇点的组合类，那么 \widehat T=\widehat{Z_1}\times\text{MSET}(\widehat{Z_0}\times(\text{MSET}(\widehat T)-\widehat E))，则 T=z\text{Euler}(\text{Euler}(T)-1)，注意只计算奇点个数，因而 \widehat{Z_0} 转写为 1 而伓是 z。可以全在线卷积解决，复杂度 O(n \log^2 n)。

解法二：设 A(z)=\acute{\text{Eul}}(T),B(z)=\acute{\text{Eul}}(\text{Euler}(T)-1)，则可以变换为 \ln(T/z)-B(z)-(\exp(T+A(z))-1)=0 的形式进行多项式牛顿迭代，导函数为 1/T-\exp(T+A(z))，复杂度 O(n\log n)，常数 24+5/6。

18. LGOJT5206 [WC2019] 数树

题意简述：对给定 T_1,T_2 其中零到两个树结构，而剩下树结构随机的情况下求 \sum_{T_1,T_2} y^{n-|T_1\cap T_2|} 对 998244353 取模的结果，1 \le n \le 10^5。

第一部分解法：遍历两棵树计算重复边即可，复杂度 O(n)。

第三部分解法：我们先乘上 y^n 再考虑令 c=y^{-1}。考虑钦定一些边是 T_1 和 T_2 的交然后我们注意到：

而钦定交之后我们的方案数由扩展 Cayley 定理[18]为 n^{2(m-2)} \prod s_i^2，因为我们有两棵树。因此我们对 c=1 特判后直接计算 n^{-4} (c-1)^n \prod_{\sum a_k=n} \frac{n^2a_k^2a_k^{a_k-2}}{c-1} 即可，使用多项式 exp，复杂度 O(n \log n)，常数 6。

第二部分解法：直接快进到 \sum_{E}\text{val}(E) (c-1)^{|E|}，然后这时我们注意到 E 必须是给定的 T_1 的子集，而 \text{val}(E)=n^{m-2} \prod s_i，于是答案就是 y^n n^{-1} \sum\limits_{S\subseteq T_1} (n/(c-1))^{|S|} \prod a_k，后面也是一个计数经典转化，将 \prod a_k 转化为在每个连通块放一个球。然后树形 DP 即可，复杂度 O(n)。

19. UOJT514 [UR #19] 通用测评号

题意简述：有 n 个燃料仓，每次等概率随机选一个没有满的燃料舱放入燃料，所有燃料仓都 \ge B 时结束，问期望有多少个仓达到了 A 的满值，对 998244353 取模，1 \le n,A,B \le 250。

一句话题解：首先转化为每次在 n 个钟随机选，求 \ge A 仓数的期望。考虑结束时第一个变量大于 A 的概率，这能转化为第一个变量到达 A 时还有 <B 变量的概率，钦定其中 k 个仓 <B，答案即为 n\sum\limits_{k=1} (-1)^{k+1} \binom{n-1}{k} f(k)，于是 f(k)=(\text{ToOGF}(SET_{<B}(\widehat Z)^k)SET_{=A-1}(\widehat Z))(\frac{1}{k+1})，考虑 DP 出 \text{ToOGF} 内的多项式，求导构造递推即可，复杂度 O(n^3)。

20. LGOJT5326 [ZJOI2019] 开关

题意简述：有 n 个开关分别有 p_i 的权值，给定初始开关状态，每次以 \frac{p_i}{\sum_i p_i} 概率改变开关 i 的状态，求期望全零时间，对 998244353 取模，1 \le n \le 100,1 \le \sum_i p_i \le 50000。

一句话题解：考虑设出达到结束状态的生成函数 F 和从结束状态返回结束状态的生成函数 G，则 Ans=F/G，而所求期望为 Ans'(1)=\frac{F'(1)G(1)-G'(1)F(1)}{G(1)^2}，注意到 F=\text{ToOGF}(\prod_i (e^{\frac{p_i}{\sum_i p_i}x}+(-1)^{s_i} e^{-\frac{p_i}{\sum_i p_i}x})/2),G=\text{ToOGF}(\prod_i (e^{\frac{p_i}{\sum_i p_i}x}+e^{-\frac{p_i}{\sum_i p_i}x})/2)，注意到 e 上的指数都以 \sum_i p_i 为分母，DP 即可，复杂度 O(n\sum_i p_i)。

21. AGC38E Gachapon

题意简述：有 n 个数分别有 p_i 的权值，每次以 \frac{p_i}{\sum_i p_i} 概率生成 i，求期望每个数分别被生成了至少 B_i 次的期望时间，对 998244353 取模，1 \le n,\sum A,\sum B \le 400。

一句话题解：考虑设出达到结束状态的生成函数 F=\text{ToOGF}(\prod_i (e^{\frac{A_i}{\sum_i A}x}-SET_{<B_i}(\widehat Z)))，则 Ans=\sum_i 1-f_i，那么从 F 中去掉一个 e^{\frac{\sum_i A}{\sum_i A}x} 后可以直接带入 -F(1)，注意到 e 上的指数都以 \sum_i A 为分母，且 x 上的指数不大于 \sum B，DP 即可，复杂度 O(n(\sum A)(\sum B))。

22. LGOJT2767 树的数量

题意简述：求出 n 点无标号有根有序 m 叉树的个数，对 10007 取模，1 \le n,m \le 127。

一句话题解：\widehat F=\widehat Z \times SEQ_m{\widehat F+\widehat E}，拉格朗日反演有 [z^n] F(z)=\frac{1}{n}[z^{n-1}](1+z)^{nm}=\frac{\binom{nm}{n-1}}{n}，注意使用 lucas 定理，复杂度 O(\min(mod,nm))。

23. LGOJT6633 抽卡

题意简述：给定 m 需要的卡的编号，以及 n=\max a_i，表示 [1,n] 均为一次可以抽到的卡，问抽到连续 k 张需要的卡的期望时间，保证存在一种方案抽到，对 998244353 取模，1 \le a_i \le 2m,1 \le m \le 10^5,2 \le k \le m。

题解：考虑抽不到连续 k 张卡对应的生成函数，注意到不同段互不相干，则 Ans=\text{ToOGF}(\prod F_{len_i}(z))(m^{-1})，其中 F_n=\text{Longest-run}(n,k)=\text{SEQ}_{<k}(\{1\}) \times \text{SEQ}(\{0\} \times \text{SEQ}_{<k}(\{1\}))，接下来我们只考虑 1 的个数，而最后再处理等价于 \text{ToOGF}((e^x-1)^r)(m^{-1}) 的情况，实际上由于每个 r 大小状态不论生死的话都等概率走到，而每次期望停留 m/(m-r) 次抽卡，因而系数是 \frac{m}{(m-r)\binom{m}{r}}。而 F_n=\sum_r [z^r](1+z+\cdots+z^{k-1})^{n+1-r}。这样的 [z^r](1+z+\cdots+z^{k-1})^{n+1-r}=[z^n] (z+\cdots+z^k)^{n+1-r}，则考虑幂的横截即可。设 H+\cdots+H^k=z，则可以使用牛顿迭代法计算，[z^n](z+\cdots+z^k)^t=\frac{1}{n}[z^{n-1}]tx^{t-1} (x/H)^n，由于最后需要分治 NTT 将其全部乘起来，故时间复杂度 O(m \log^2 m)，单 log 部分常数 32，使用预处理原根的非 DIF-DIT NTT 牛顿迭代板子用时 1.61 \text{s}。

24. LGOJT5850 calc加强版

题意简述：对 [1,n] 内的每个 n 求所有值在 [1,k] 长为 n 的互不相同序列中数的乘积的和，对 998244353 取模，1 \le n \le 5*10^5,1 \le k < mod。

一句话题解：注意到元素互不相同所以可以直接按大小排序并乘 n!，于是 Ans=n![x^n]\prod_{1 \le i \le k} (1+ix)=n![x^n]\exp(\sum_{i>0} \frac{(-1)^{i+1}\sum_{j\in [1,k]} j^i}{i})，那么我们只要对每个 n 求出 \sum_{j \in [1,k]}j^n 即可，而这是 [x^n/n!]\frac{e^{(k+1)x}-e^x}{e^x-1}，直接多项式求逆即可，然后 exp，时间复杂度 O(n \log n)，常数 9.5。

25. LGOJT5219 无聊的水题 I

题意简述：求 n 个点的有标号无序树中最大的度数恰为 m 的方案数，对 998244353 取模，1 \le n,m \le 5*10^4。

一句话题解：首先差分，转化为度数不大于 m 的方案数，考虑 \widehat F=\widehat Z \times \text{SET}_{<m}(\widehat F)，然后要求的即为 \frac{1}{n-1}[x^n/n!]F^2(x)/2=(n-2)![x^{n-2}]S(x)^n，其中 S(x)=\sum_{i<m} z^i/i!，其中 \frac{1}{n-1} 是因为我们的根限制了度数 m-1，而我们将两个根连在一起，这样根上的限制也是对的了，实际上相当于新根是一条边，因此要除以 n-1。

26. AGC19E Shuffle and Swap

题意简述：给出两个长度为 n(n\le 10^4) 的 \texttt{01} 串 A 和 B。两个串均恰有 k 个 1。令 a_{1, 2, \cdots, k} 和 b_{1, 2, \cdots, k} 分别表示 A 和 B 中所有 1 出现的位置，将 a 和 b 等概率随机排列，按 i = 1, 2, \cdots, k 的顺序交换 A_{a_i} 和 A_{b_i}。令 p 表示操作完成后 A 与 B 相等的概率，求 P\times(k!)^2 在模 998244353 意义下的值。

一句话题解：注意到 0/1 的位置无关紧要，设 r 为均为 1 的数量，s 为分别为 0/1 的数量。考察交换的情况，注意到一个位置最多有一个入边和一个出边，那么一系列交换只能是一条从 1/0 经过若干 1/1 到 0/1 的链，以及剩下的一些全 1 环，那么 Ans=[z^r/s!/(r+s)!]\exp(F_{\text{ring}})F_{\text{line}}^r，其中 F_{\text{ring}}=\sum_i (i-1)!i!z^i/i!i!,F_{\text{line}}=\sum_i i!z^i/i!(i+1)!。这是因为全 1 环上可以随意交换，而链要选定一个固定顺序进行交换，分母是因为位置和交换是两种使用 EGF 计数的顺序，注意链的交换次数是 i+1。时间复杂度 O(n \log n)，常数 8.5。

27. LGOJT7445 [EZEC-7] 线段树

题意简述：在一棵 [1,n] 上的经典线段树上进行 m 次区间加操作，每次操作会等概率地从 [1,n] 的所有 n(n+1)/2 个子区间中随机选择一个进行操作，每次加的数是 [-1,V] 之间等概率随机的整数，最后按顺序对所有非零标记的点 pushdown，问期望有多少节点被 pushdown，对 998244353 取模，1 \le n,m \le 10^5,-1 \le V <mod-2。

一句话题解：首先考虑每个点每次被覆盖到的概率，那么其为 l(n-r+1)/(n(n+1)/2)，于是设 f_k 为恰被覆盖 k 次而和为 0 的方案数（因为这样比较好算），p_k=(V^k-f_k)/V^k那么 Ans=\sum_i (1-p_i)^m \sum_{t} (p/(1-p))^t p_t=\sum_i B_i \sum_t A_i^t p_t=\sum_t p_t \sum_i B_i A_i^t=\sum_t p_t [x^t] \sum B_i/(1-A_ix)，这部分可以 O(n\log^2 n) 分治 NTT 解决。而 f_k=[x^0](x^{-1}+\cdots+x^V)^k=[x^0](x/(1+..\cdots+x^{V+1}))^-k=[x^k]H'(x)/(H(x)/x)，而 H 满足 \frac{H^{V+2}-1}{H-1}=x，这可以使用牛顿迭代法计算，总时间复杂度 O(n \log^2 n+m \log m)，O(m \log m) 部分常数为 26。

参考文献：

[1]https://zhuanlan.zhihu.com/p/31595840

[2]https://zhuanlan.zhihu.com/p/33324206

[3]https://www.cnblogs.com/joke3579/p/symbolic_method.html

[4]https://oiwiki.org/math/poly/symbolic-method

[5]https://www.cnblogs.com/zhiyangfan/p/16014630.html

[6]NOI2024冬令营讲义《第一课堂：组合数学中的递推问题》

[7]https://zhuanlan.zhihu.com/p/665999109

[8]https://zhuanlan.zhihu.com/p/665404361

[9]https://www.cnblogs.com/chasedeath/p/14421599.html

[10]https://www.luogu.com/article/oy8l7j3n

[11]https://www.cnblogs.com/rainybunny/p/16217175.html

[12]https://www.luogu.com.cn/article/wdfx41y0

[13]http://218.5.5.242:9019/article/1161

[14]https://www.cnblogs.com/Paul-Guderian/p/10487214.html

[15]https://www.cnblogs.com/A-Quark/p/16410007.html

[16]https://www.cnblogs.com/rainybunny/p/13283656.html

[17]https://www.cnblogs.com/rainybunny/p/13283555.html

[18]https://www.cnblogs.com/A-Quark/p/16417307.html

[19]https://www.luogu.com.cn/article/nn4kvg8x