• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

注释-「拉格朗日反演」注释与注解


Recommended Posts

正在建设中。

对于常数项为(0)且首项不为(0)的多项式(F,G ),定义复合运算并满足

\[(f \ CIRC g)(x)=g(f(x))=\ sum _ { I \ ge 0}g_if^i(x).

\]

对于定义域\ (\(\mathbb F\),设\(\mathcal S\)是\ (\ mathbf [[x]] \)中满足上述条件的所有多项式的集合。对于任意多项式\(F\in \mathcal S\),我们有一个强构造方法来唯一地确定\(G\)使得\(F\circ G=x\),所以\(\circ\)在\(\mathcal S\)上是可逆的。那么就不难解释\ (\ mathcals,\ circ) \)构成了一个群体,即多项式复合群.

注意在群的意义上,\(F,G\)满足\(F\circ G=x\)应该是互易元素,所以有个小结论。

\[F \ CIRC G=x \ left right arrow G \ CIRC F=x

\]

这时,\(F,G\)也被称为复合逆.

拉格朗日反演表明,对于(F,G ),当满足(F CIRC G=x)时,存在

\[[x^n]g(x)=\frac{1}{n}[x^{-1}]f^{-n}(x).

\]

涉及到一个比较诡异的“\ ([x {-1}] \)”。其实这些运算都是在分数域\(\mathbb F(x)\)的分式域.下进行的,任何非零代数表达式\(F(x)\)都有乘法逆。因为我们总能在\(\mathbb F[[x]]\)下找到可逆的代数表达式\ (g (x)=f (x)/x k \),那么\ (f {-1} (x)=x {-k} g {-1。

接下来试着证明反演公式。先证明引理:对于\ (k \ in \ mathbz,f \ in \ mathcals \),有

\[[x^{-1}]F'(x)F^{k}(x)=[k=-1].

\]

当\(k\neq-1\),\(f '(x)f k(x)=\ left(\ frac { f { k 1 }(x)} { k 1 } \ right)' \)。按照上面的科普,这个结果是代数表达式,所以\ ([x {-1}]=0 \)。

当\(k=-1\),\ ([x {-1}] f' (x) f {-1 }(x)=[x 0]f '(x)(f(x)/x){-1 } \),\ \([x 0]f '(x)=[x 0](f(x)/x)=[x 1]f(x)\)被观测到时,所以\([x {-1 }]f '(x)f {-1)

接下来证明原命题。已知的

\[(g \ CIRC f)(x)=\sum_{i\ge1}f_ig^i(x)=x.

\]

对两边求导,

\[\sum_{i\ge1}if_ig^{i-1}(x)g'(x)=1.

\]

通过证明目标,将两边(分数域下)除以\ (g n (x) \)并取\ ([x {-1}] \),

\[[x^{-1}]\sum_{i\ge1}if_ig^{i-1-n}g'(x)=[x^{-1}]g^{-n}(x).

\]

使用左边的引理,当且仅当\(I=n \)\([x {-1 }]g { I-1-n } g '(x)=1 \ neq 0 \),因此

\[nf_n=[x^{-1}]G^{-n}(x)\\

\向右箭头

\begin{cases}

[x^n]f(x)=\frac{1}{n}[x^{-1}]g^{-n}(x)\\

[x^n]g(x)=\frac{1}{n}[x^{-1}]f^{-n}(x]

\结束{病例}。~ ~ ~ ~ \正方形

\]

作为代数表达式的爱好者,你可以把这个结论变成

\[[x^n]g(x)=\frac{1}{n}[x^{n-1}](f(x)/x)^{-n}.

\]

其中\(F(x)/x\)代数表达式是可逆的,避开了分数场。

扩展的拉格朗日反演:对于\(F,G\in\mathcal S\)和满足\(F\circ G=x\)的任意多项式,有

\[[x^n](g\circ h)(x)=\frac{1}{n}[x^{-1}]h'(x)f^{-n}(x).

\]

证明画一瓢叭,首先

\[F \ CIRC G=x \ right arrow(F \ CIRC G)\ CIRC H=F \ CIRC(G \ CIRC H)=H。

\]

扩展导数,

\[\sum_{i\ge1}i\cdot[x^i](g\circ h)(x)\ cdot f^{i-1}(x)f'(x)=h'(x).

\]

除以\ (f n (x) \)并取\ ([x {-1}] \),顺便用引理,

\[n[x^n](g\circ h)(x)=[x^{-1}]h'(x)f^{-n}(x)\\

\右箭头[x^n](g\circ h)(x)=\frac{1}{n}[x^{-1}]h'(x)f^{-n}(x).~ ~ ~ ~ \正方形

\]

当然也很好看。版本:

\[[x^n](g\circ h)(x)=\frac{1}{n}[x^{n-1}]h'(f(x)/x)^{-n}.

\]

好像什么都没做。)

最喜欢的例子的时间。

" Bzoj # 3684"/"Ouroj # 17684 "大朋友和多棵树

一定要看样本解释。(

设\(G(x)\)为答案的GF,\ (f (x)=\ sum _ ix {d _ i} \),显然

\[G(x)=x F(G(x))\\

\右箭头G(x)-F(G(x))=x。

\]

设\(H(x)=x-F(x)\),拉格朗日的反应是

\[[x^n]g(x)=\frac{1}{n}[x^{n-1}](h(x)/x)^{-n}.

\]

正好,\ ([x 0] (h (x)/x)=1 \),规范整数多项式的快幂。复杂性\(\mathcal O(n\log n)\)。

(下面是草稿。jpg)

\[P(x)=\frac{x-x^{k 1}}{1-x}\\

f(x,y)=\sum_{i\ge0}p^{i}(x)y^{i}=\frac{1}{1-p(x)y}\\

[x^{n 1}]F(x,y)=\ frac { 1 } { n 1}[x^n]\frac{y}{(1-xy)^2}(q(x)/x)^{-n-1}\\

\frac{q(x)-q^{k 1 }(x)} { 1-q(x)}=x \

x-(x ^ 1)q(x)q^{k 1 }(x)=0 \

q _ { 2n }(x)=q _ n(x)\ frac { x-(x ^ 1)q _ n(x)q_n^{k 1 }(x)} { x ^ 1-(k 1)q_n^k(x)}

\]

Link to comment
Share on other sites