牛客多校 2023 10 H：
- \(F_0(x)=x\)
- \(F_k(x)=(x^2-1)F'_{k-1}(x)\)
给定 \(x_0\)，求 \(F_n(x_0)\)。
场上我的做法：
设 \(f_{i,j}\) 为 \(F_i\) 求 \(j\) 次导后，\(x_0\) 的点值。
那可以导出递推式：
\(f_{i,j} = f_{i-1,j-1}\times j(j-1) + f_{i,j}\times j\times 2x_0 + f_{i-1,j+1}\times (x_0^2-1)\)
\(f_{0,1}=1\)
把 dp 倒过来（转置），变成初始状态为 \(f_{n,0}=1\)，答案位置为 \(f_{0,1}\)，然后：
设 \((2x_0) = B,(x_0^2-1) = A\)。
- \(f_{i,j}\times j(j-1) \to f_{i-1,j-1}\)
- \(f_{i,j}\times j\times B \to f_{i-1,j}\)
- \(f_{i,j}\times A \to f_{i-1,j+1}\)
发现这个式子非常像一个联考题。考虑这个 dp 的组合意义：
假设我们有一个有根的二叉树森林，现在有 \(j\) 个根。
新加入一个点，三种转移分别为：
- 选两个点成为新点的左右儿子。
- 选一个点成为新点的儿子，乘上系数 \(B\).
- 新点是新的叶子，乘上系数 \(A\).
最后 \(f_{1,0}\) 是形成一棵有根树的方案数。
那么，问题转化为“父亲点编号小于儿子节点”的二叉树计数，树上的点有权值。可以列出一个简单的 dp，然后 cdq NTT 解决。
- \(f_i = B\times f_{i-1} + \sum_{j=1}^{i-1}\binom{i-1}{j}f_jf_{i-1-j}\)
- \(f_1 = c\)
这个做法也可以扩展到 dp 乘的是 \(Ax^2+Bx , Cx , D\) 的情况。
当然这题有一些更通用的解法，求解带微分的迭代。
我们的式子是 \(F_i(x) = F'_{i-1}(x)\times (x^2-1)\).
考虑设计一个 \(u(x)\)，满足 \(F_i(u(x)) = F'_{i-1}(u(x))\times u(x)\).
通过这个式子进行换元，变成 \(G_i(x) = G'_{i-1}(x)\times x\).
这样如果知道了 \(G_0(x)\)，\(G_n(x)\) 只需要每一项乘上个些快速幂来得到。
那我们需要解决 \(F\to G,G\to F\) 的问题。
\(u(x)\) 的复合逆可以解出来，\(F\to G\) 就是求 \(F(u^{<-1>}(x))\)。
\(G\to F\) 就是求 \(G_n(u(x_0))\)，可以代入算出。