一道牛客题相关的思考

牛客多校 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))\)，可以代入算出。