拉格朗日反演证明

感谢 BZT 大仙的细心指导: →_→

求函数 G 满足:

[G(F(x))=x ]

**其中 G 和 F 都要满足常数项为 0 且 1 次项不为 0 **

(G(x)=sum_{i>=1} a_i x^i)

那么原式就是:

[sum_{i=1}^infty a_i F^i(x)=x ]

然后我们两边取导:

[sum_{i=1}^infty i·a_i F^{i-1}(x) F'(x)= 1 ]

然后左右除去 (F^n(x))

[sum_{i=0}^{infty}i·a_i F^{i-n-1}(x) F'(x)={1over F^n(x)} ]

两边取 x 的 -1 次项:

[[x^{-1}]sum_{i=0}^{infty}i·a_i F^{i-n-1}(x) F'(x) =[x^{-1}]{1over F^n(x)} ]

这时候我们江 i 不等于 n 的情况讨论一下:

[F^{i-n-1}(x)F'(x)={1over i-n} (F^{i-n}(x))' ]

这里我们从右往左推就好了,用链式法则

然后我们发现一个多项式求导后的 -1 次项系数为 0 ,就不用考虑了

对于 i=n 的情况:

[F^{-1}(x)F'(x)={a_1+2a_2x+2a_3x^2+...over a_1x+a_2x^2+a_3x^3+...} ]

[={a_1+2a_2x+2a_3x^2+...over a_1x}·{1over 1+{a_2over a_1}x+{a_3over a_1}x^2+...} ]

后面的多项式常数项为 1,可逆,逆完之后常数项还是 1, 那么前面的式子中 x 的 -1 次项系数为 1

那么原来的式子就是:

[a_n = [x^{-1}] {1over F^n(x)} ]

那么这也就证明出了拉格朗日反演中的定理:

[[x^n] G(x) = [x^{-1}] {1over n} {1over F^n(x) } ]

然后我们让 f(x) 表示 F(x) 除去 x 后的多项式,那么原本的答案就是:

[[x^n] G(x) = [x^{n-1}] {1over n} {1over f^n(x) } ]

然后我也不知道这玩意儿为什么是对的,反正这样的情况下我们就可以 (O(n log n)) 求解(多项式快速幂+多项式求逆)了

原文地址:https://www.cnblogs.com/Judge/p/10652738.html