关于一个数学问题

学术版

MornStar @ 2024-10-14 21:56:00

现已知道 f(0),f(1) 的值，k 是常数。

f(n)=\sum_{\begin{align} x_1+x_2+\cdots+x_k=n-1\\ x_1\ge 0,x_2\ge 0 ,\cdots,x_k\ge 0 \end{align}}{\prod_{i=1}^k f(x_i)}

有没有可以快速求出任意 f(x) 的方法，最好低于 O(n^2)。个人感觉可以分治 FFT。

by Grammar_hbw @ 2024-10-14 21:56:20

希望更丰富的展现？使用 Markdown、KaTeX。

@MornStar

by Leaf59 @ 2024-10-14 21:56:42

@MornStar
请用\LaTeX

by MornStar @ 2024-10-14 21:57:11

LaTeX 挂了

by Leaf59 @ 2024-10-14 21:59:47

@MornStar
求解this

by 飞雨烟雁 @ 2024-10-14 22:51:49

@MornStar 有 \Theta(n\log n) 的做法，记：

F=\sum_{n=1}^\infty f(n)x^n

首先如果 f(1)=0，则 F=0。故以下不妨设 f(1)\neq 0。

根据递推式可知：

F-f(1)x=x(F+f(0))^k-f(0)^kx

若记：

G(x)=\dfrac{x}{(x+f(0))^k-f(0)^k+f(1)}

则 G(F)=x，直接求复合逆是 \Theta(n\log^2n) 的。不过 G 的形式比较简单，可以牛顿迭代，最后时间复杂度为 \Theta(n\log n)。

by 小粉兔 @ 2024-10-15 00:58:01

@MornStar 补充一下，只求单项的话，可以考虑 Lagrange 反演。

相当于求 \frac1n[x^{n - 1}] ((x + a)^k + b)^n，可以用二项式定理展开。

如果恰好有 f(0)^k = f(1)，则上式简化为 \frac1n[x^{n - 1}] (x + f(0))^{k n}。可得一个简单的类似 \frac1n\binom{n k}{n - 1} 的式子。k = 2 时与 Catalan 数吻合。