求 F(x)=\sum\limits_{i=1}^\infty i!x^i 的复合逆 G(x)。
$1.$ 找出 $F(x)$ 的 ODE。
$$x^2F'(x)+(x-1)F(x)+x=0$$
$2.$ 代入 $G(x)$。
$$G^2(x)F'(G(x))+(G(x)-1)F(G(x))+G(x)=0$$
$$G^2(x)\dfrac{(F(G(x)))'}{G'(x)}+x(G(x)-1)+G(x)=0$$
$$G^2(x)+(x+1)G(x)G'(x)-xG'(x)=0$$
$3.$ 展开卷积。
令 $g_i=[x^i]G(x)$。有 $g_0=0,
\sum\limits_{i=1}^{n} ig_ig_{n-i+1}+\sum\limits_{i=1}^{n-1} (i+1)g_ig_{n-i}-ng_n=0
g_n=-\sum\limits_{i=2}^{n-1}ig_ig_{n-i+1}-\sum\limits_{i=1}^{n-1}(i+1)g_ig_{n-i}
直接推是 O(n^2)，也可以分治 FFT 做到 O(n\log^2 n)。
求
F(x)=\sum\limits_{i=0}^m\dbinom{n}{i}(1-x)^i(1+x)^{n-i}
对着 F(x) 求导然后乱搞，时间复杂度 O(n)。
求长度为 n 的且满足 \forall i\in [1,n),|p_i-p_{i+1}|\neq 1 的排列 p 数量。
首先考虑容斥，钦定一部分 i 满足 |p_i-p_{i+1}|=1。
设原问题的生成函数为 F(x)，全排列的生成函数为 G(x)，容斥系数的生成函数为 H(x)。
注意这里讨论的生成函数常数项都为 0。
可以得到
F(x)=G(H(x))
H(x)=\dfrac{x-x^2}{1+x}
H'(x)=\dfrac{1-2x-x^2}{(1+x)^2}
考虑 G(x) 的 ODE
x^2G'(x)+(x-1)G(x)+x=0
代入 H(x) 可得
H^2(x)G'(H(x))+(H(x)-1)G(H(x))+H(x)=0
H^2(x)\dfrac{F(x)}{H'(x)}+(H(x)-1)G(H(x))+H(x)=0
H^2(x)F'(x)+(H(x)-1)H'(x)F(x)+H(x)H'(x)=0
\dfrac{(x-x^2)^2}{(1+x)^2}F'(x)-\dfrac{(1+x^2)(1-2x-x^2)}{(1+x)^3}F(x)+\dfrac{(x-x^2)(1-2x-x^2)}{(1+x)^3}=0
(x-x^2)^2(1+x)F'(x)-(1+x^2)(1-2x-x^2)F(x)+(x-x^2)(1-2x-x^2)=0
(x^5-x^4-x^3+x^2)F'(x)+(x^4+2x^3+2x-1)F(x)+(x^4+x^3-3x^2+x)=0
f_1=1,f_2=0,f_3=0,f_4=0
(n-4)f_{n-4}-(n-3)f_{n-3}-(n-2)f_{n-2}+(n-1)f_{n-1}+f_{n-4}+2f_{n-3}+2f_{n-1}-f_n=0
f_n=(n+1)f_{n-1}-(n-2)f_{n-2}-(n-5)f_{n-3}+(n-3)f_{n-4}
时间复杂度 O(n)。
Binomial Sum 学习笔记
求 [x^n]F(G(x))，其中 n 较小，F(x) 的次数比较大。
设 c=G(0)。
对于 F(x+c) 来说，所有超过 n 次的项对答案都没有贡献。
设 \mathcal{F}(x+c)=F(x+c)\bmod x^{n+1}。
需要注意，\mathcal{F}(x)\neq F(x)\bmod x^{n+1}。
可以发现 \mathcal{F}(x) 的次数不超过 n。
经过这一系列变换，我们把次数巨大的 F(x) 转化为了次数不超过 n 的 \mathcal{F}(x)，这便是这一技巧的关键点。
现只需求出 \mathcal{F} 即可。
考虑 F(x+c) 的微分方程
\sum\limits_{i=0}^mp_i(x+c)F^{(i)}(x+c)=0
由于 \mathcal{F}(x+c) 是 F(x+c) 截取的结果，所以如果将它代入微分方程会产生一个扰动因子 D(x) 来修正结果，即
\sum\limits_{i=0}^mp_i(x+c)\mathcal{F}^{(i)}(x+c)=D(x)
\sum\limits_{i=0}^mp_i(x)\mathcal{F}^{(i)}(x)=D(x-c)
利用 \mathcal{F}'(x+c)=(\mathcal{F}(x+c))' 求出 D(x)，进而求出 D(x-c)，根据它可以递推出 \mathcal{F}(x)，这样就完成了问题的转化。
F_i(x)=A_1(x)F_{i-1}'(x)+A_2(x)F_{i-1}(x)
给定 F_0(x) 求 F_m(x)。
设
G_i(x)=B_1(x)F_i(B_2(x))
我们希望
G_i(x)=xG'_{i-1}(x)+kG_{i-1}(x)
B_1(x)F_i(B_2(x))=x(B'_1F_{i-1}(B_2(x))+B_1(x)B'_2(x)F'_{i-1}(B_2(x)))+kB_1(x)F_{i-1}(B_2(x))
\begin{cases}xB_1(x)B'_2(x)=A_1(B_2(x))\\ xB'_1(x)+kB_1(x)=A_2(B_2(x))\end{cases}
能不能解出这个微分方程，以及解完了之后怎么算复合，那就自求多福吧（
在 O(m) 的时间复杂度内求出 [x^n]\dfrac{1}{(1-x)(1-ax)^m}。
用组合数写出式子
\sum\limits_{i=0}^n\dbinom{m+i-1}{i}a^i
可以得到递推式
f_{n,m}=f_{n,m-1}+a\times f_{n-1,m}
特别地，f_{0,m}=f_{n,-1}=1。
将 m 这一维写成生成函数可以得到
(1-x)F_n(x)=aF_{n-1}(x)+1
F_n(x)=\dfrac{(1-x)^{n+1}-a^{n+1}}{(1-x)^{n+1}(1-x-a)}
=\dfrac{1}{1-x-a}-\dfrac{a^{n+1}}{(1-x)^{n+1}(1-x-a)}
只需求
[x^m]F(x)
其中
F(x)=\dfrac{1}{(1-x)^n(1-x-a)}
对 F(x) 求导得到
F'(x)=\dfrac{n}{(1-x)^{n+1}(1-x-a)}+\dfrac{1}{(1-x)^n(1-x-a)^2}
F'(x)=\dfrac{F(x)}{1-x-a}+\dfrac{nF(x)}{1-x}
(x^2-(a-2)x+1)F'(x)=(-(n+1)x-na+n+1)F(x)
f'_{m-2}+(a-2)f'_{m-1}+f'_m=-(n+1)f_{m-1}-(na-n-1)f_m
f_{m+1}=\dfrac{((m-n)a+n-2m+1)f_{m}-(n+1)f_{m-1}}{m+1}
实际上也可以直接计算
\sum\limits_{i=0}^m\dbinom{n+i-1}{i}\dfrac{1}{(1-a)^{m-i+1}}
求
\prod\limits_{i=1}^n \dfrac{1-e^{ix}}{ix}
的 0\sim m 次项。
=\exp\left(\sum\limits_{i=1}^n \ln\left(\dfrac{1-e^{ix}}{ix}\right)\right)
设 \ln\left(\dfrac{1-e^{x}}{x}\right)=\sum\limits_{i=0}^\infty f_ix^i。
=\exp\left(\sum\limits_{i=1}^n\sum\limits_{j=0}^\infty f_j(ix)^j\right)
=\exp\left(\sum\limits_{j=0}^\infty f_jx^j\sum\limits_{i=1}^n i^j\right)
只需要保留 f_{0\dots m}，暴力完成所有操作即可做到 O(m^2)。
求
\sum\limits_{i=0}^{\infty}a^ii^n
设
F(x)=\dfrac{1}{1-ax}
我们相当于是要求 n![x^n]F(e^x)。
因为 e^x 的常数项为 1，所以对于 F(x+1) 来说，所有超过 n 次的项都没有贡献。
设 \mathcal{F}(x+1)=F(x+1)\bmod x^{n+1}。
由
F(x+1)=\dfrac{1}{1-a-ax}
可以得到
\mathcal{F}(x+1)=\dfrac{1}{1-a}\sum\limits_{i=0}^n\left(\dfrac{ax}{1-a}\right)^i
设
f_k=[x^k]\mathcal{F}(x)=\dfrac{1}{1-a}\sum\limits_{i=k}^n\dbinom{i}{k}\left(\dfrac{a}{1-a}\right)^i
答案即为
n![x^n]\mathcal{F}(e^x)=\sum\limits_{i=0}^nf_ii^n
问题转化为对于每个 k\in [0,n] 求出 f_k，
设
b=\dfrac{a}{1-a}
g_k=\sum\limits_{i=k}^n\dbinom{i}{k}b^i
只需要求出 g 就可以求出 f。
实际上，与 g 类似的式子我们已经在前面的内容中分析过如何快速求了，这里我们再给出一种类似但又不全相同的解法。
显然有 g_0=\dfrac{1-x^m}{1-x}。我们考虑找出 g 的递推式
g_k=\sum\limits_{i=k}^n\dbinom{i}{k}b^i
=\sum\limits_{i=k}^n\left(\dbinom{i-1}{k}+\dbinom{i-1}{k-1}\right)b^i
=b\left(\sum\limits_{i=k}^{n-1}\dbinom{i}{k}b^i+\sum\limits_{i=k-1}^{n-1}\dbinom{i}{k-1}b^i\right)
=b\left(g_k+g_{k-1}-\left(\dbinom{n}{k}+\dbinom{n}{k-1}\right)b^n\right)
g_k=\dfrac{b\left(g_{k-1}-\dbinom{n+1}{k}b^n\right)}{1-b}
因此我们可以在 O(n) 的时间复杂度内对于每个 k\in [0,n] 求出 g_k。
总时间复杂度 O(n)。
我们希望 $F(0)=0$。设实际上 $F(0)=c$。则：
$$F(x)^k=\sum\limits_{i=0}^k\dbinom{k}{i}(F(x)-c)^ic^{k-i}$$
因此我们可以用一次卷积的代价归约到 $F(0)=0$ 的情况。
令 $G$ 为 $F$ 的复合逆。则由拉格朗日反演得：
$$[x^n]F(x)^k=[x^{n-1}]\dfrac{kx^{k-1}}{n}\left(\dfrac{x}{G(x)}\right)^n$$
$$=[x^{n-k}]\dfrac{k}{n}\left(\dfrac{x}{G(x)}\right)^n$$
因为 $F$ d-finite，所以 $G$ 可以用之前提到的方法快速计算。再利用多项式求逆，快速幂即可得到答案。除了求复合逆的部分之外时间复杂度为 $O(n\log n)$。
---
有 $m$ 个多项式 $F_1\dots F_m$，它们满足 $m$ 个方程 $f_i(F)=0$。求 $F_1\dots F_m$ 的前 $n$ 次项。
考虑牛顿迭代。假设已知前 $n$ 项，考虑求前 $2n$ 项。
设 $F_i$ 截取前 $n$ 项为 $A_i$，截取前 $2n$ 项为 $B_i$。
考虑第 $i$ 个方程 $f_i(B)\equiv 0\pmod{x^{2n}}$，依次将它在每个 $A_i$ 处泰勒展开。
注意到 $x^n\mid B_i-A_i$，而我们只关心前 $2n$ 次项。因此关于 $B_i-A_i$ 的非线性项均可省略。
考虑 $f_i(X)$。此时只需要考虑满足 $x^n\mid X_i-A_i$ 的情况。依次将它在每个 $A_i$ 处泰勒展开。因此在满足 $x^n\mid X_i-A_i$ 展开的结果可以简写为如下形式：
$$
f_i(X)\equiv f_i(A)+\sum\limits_{i=1}^m\left(\dfrac{\partial}{\partial X_i}f_i(A)\right)(X_i-A_i)
$$
令 $D_i=X_i-A_i$。
现在得到了 $m$ 个关于 $D_i$ 的线性方程。高斯消元即可求出一组解。
最后令 $B_i=A_i+D_i$ 即可。