三亩地 三亩地SAN MU DI · CODE DIARY
ARTICLE DETAIL

日记详情

真实记录编程学习的某一天,欢迎挑你感兴趣的翻一翻。

拉格朗日反演

拉格朗日反演

参考 command_block 的多项式。

考虑 \(G(x),F(x)\) 互为复合逆,且没有常数项,\([x]F\) 和 \([x]G\) 非 \(0\)。

基础形式

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

类似的

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

proof

引理:\([x^{-1}]F'F^n=[n=-1]\)

证明: 考虑 \(F=xH\),那么 \(H\) 有常数项,那么就变成了 \([x^{-1}]F'x^nH^n\),若 \(n\not=-1\),这之中一定没有 \(-1\) 项,否则就为 \(1\)。

\[\begin{align*} G(F(x))&=x \\ \sum_i G_iF^i&=x\\ \sum_i G_iiF'F^{i-1}&=1\\ \sum_i G_iiF'F^{i-n-1}&=F^{-n}\\ [x^{-1}]\sum_i G_iiF'F^{i-n-1}&=[x^{-1}]F^{-n}\\ [x^{-1}]\sum_i G_iiF'F^{i-n-1}&=[x^{-1}]F^{-n}\\ \sum_i G_ii[i-n-1=-1]&=[x^{-1}]F^{-n}\\ G_nn&=[x^{-1}]F^{-n}\\ G_n&=\frac{1}{n}[x^{-1}]F^{-n}\\ \end{align*} \]

← 返回列表