文档章节

拉格朗日反演证明

o
 osc_w9s1w4o0
发布于 2019/04/04 06:53
字数 459
阅读 9
收藏 0

精选30+云产品,助力企业轻松上云!>>>

感谢 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)={1\over F^n(x)}$$

两边取 x 的 -1 次项:

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

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

$$F^{i-n-1}(x)F'(x)={1\over 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}·{1\over 1+{a_2\over a_1}x+{a_3\over a_1}x^2+...}$$

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

那么原来的式子就是:

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

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

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

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

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

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

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
@总结 - 11@ 拉格朗日反演与复合逆

[toc] @0 - 参考资料@ 参考博客-1zjt 的博客地址挂掉了,所以这里暂时没有。 @1 - 问题描述@ 我们知道,有时候可以使用牛顿迭代法求 G(F(x)) = 0 的某个根 F0(x)。 但是有时候函数 G 是一个非...

osc_0cqshtia
2019/09/26
4
0
[总结]其他杂项数学相关(定理&证明&板子)

[toc] 写在前面 这是继数论和组合计数类数学相关与多项式类数学相关后的第三篇数学方面内容总结。主要记录自己近期学习的一些数学方法。内容比较杂,同时也起到对前文的一些补充作用。 若文章...

osc_b0nm4mbd
2018/06/29
2
0
bzoj3684: 大朋友和多叉树(拉格朗日反演+多项式全家桶)

题面 传送门 题解 首先你得知道什么是拉格朗日反演->这里 我们列出树的个数的生成函数 $$T(x)=x+prod_{iin D}T^i(x)$$ $$T(x)-prod_{iin D}T^i(x)=x$$ 我们记$F(x)=T(x)$,$G(x)=x-prod_{iin...

osc_1v2pb1nt
2019/03/05
1
0
一些算法学习的推荐博文阅读(数论居多,图论没有)

上面是自己的学习笔记,下面是推荐博文阅读 关于每个知识点的阅读顺序若不加序号一般是并列的,有序号的话一般是推荐看(当然一知半解的话可以从头看起也可以从中间开始) 另外,有的链接放在...

osc_bt2kdd6q
2019/02/28
1
0
loj#6363. 「地底蔷薇」(拉格朗日反演+多项式全家桶)

题面 传送门 题解 肝了一个下午……我老是忘了拉格朗日反演计算的时候多项式要除以一个$x$……结果看它推倒简直一脸懵逼…… 做这题首先你得知道拉格朗日反演是个什么东西->这里 请坐稳,接下...

osc_shz3aep4
2019/03/05
1
0

没有更多内容

加载失败,请刷新页面

加载更多

Saga分布式事务框架

1优点 1、避免服务之间的循环依赖,因为saga协调器会调用saga参与者,但参与者不会调用协调器 2、集中分布式事务编排 3、降低参与者的复杂性 4、回滚更容易管理 Saga模式的一大优势是它支持长...

战略板儿砖
15分钟前
11
0
为什么要使用static_cast (x)而不是(int)x? - Why use static_cast(x) instead of (int)x?

问题: I've heard that the static_cast function should be preferred to C-style or simple function-style casting. 我听说static_cast函数应该比C样式或简单的函数样式转换更可取。 Is......

fyin1314
17分钟前
14
0
最难的几道Java面试题,看看你跪在第几个?

这是我收集的10个最棘手的Java面试问题列表。这些问题主要来自 Java 核心部分 ,不涉及 Java EE 相关问题。你可能知道这些棘手的 Java 问题的答案,或者觉得这些不足以挑战你的 Java 知识,但...

码农突围
18分钟前
3
0
浅谈Spring核心技术 IOC与AOP

IOC: IOC(Inversion Of Controll,控制反转)是一种设计思想,将原本在程序中手动创建对象的控制权,交由给Spring框架来管理。IOC容器是Spring用来实现IOC的载体,IOC容器实际上就是一个M...

创业789
19分钟前
13
0
智能金融丨神州信息助某省联社实现一体化智能运维建设

近日,由神州信息实施的某省联社“IT服务管理平台项目”顺利通过验收,并获得客户的高度认可。该项目是神州信息在农信领域打造的又一标杆项目,为客户实现了IT运维流程标准化及运维系统一体化...

脉脉小达人
21分钟前
20
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部