二项式反演

老是记反,存一下推导过程。

至少转恰好。

\[\begin{aligned} f_{i}&=\sum^{i}_{j=0}\binom{i}{j}g_{j}\&\sum^{i}_{j=0}(-1)^{j-i}\binom{i}{j}f_{j}\&=\sum^{i}_{j=0}(-1)^{j-i}\binom{i}{j}\sum^{j}_{k=0}g_{k}\binom{j}{k}\&=\sum^{i}_{j=0}\sum^{j}_{k=0}(-1)^{j-i}\binom{i}{j}\binom{j}{k}g_{k}\&=\sum^{i}_{k=0}g_{k}\sum^{i}_{j=k}(-1)^{j-i}\binom{i}{j}\binom{j}{k}\&=\sum^{i}_{k=0}g_{k}\sum^{i-k}_{j=0}(-1)^{j+i}\binom{i-k}{j}\frac{i!j!}{(i-k)!(j+k)!}\binom{j+k}{k}\&=\sum^{i}_{k=0}g_{k}\sum^{i-k}_{j=0}(-1)^{j+i}\binom{i-k}{j}\binom{i}{k}\&=\sum^{i}_{k=0}\binom{i}{k}g_{k}\sum^{i-k}_{j=0}(-1)^{j+i}\binom{i-k}{j}\&=\sum^{i}_{k=0}\binom{i}{k}g_{k}(1-1)^{i-k}\&=g_{i} \end{aligned} \]

至多转恰好。

\[\begin{aligned} f_{i}&=\sum^{n}_{j=i}\binom{j}{i}g_{j}\&\sum^{n}_{j=i}(-1)^{j-i}\binom{j}{i}f_{j}\&=\sum^{n}_{j=i}(-1)^{j-i}\binom{j}{i}\sum^{n}_{k=j}\binom{k}{j}g_{k}\&=\sum^{n}_{k=i}g_{k}\sum^{k}_{j=i}(-1)^{j-i}\binom{j}{i}\binom{k}{j}\&=\sum^{n}_{k=i}g_{k}\sum^{k}_{j=i}(-1)^{j-i}\binom{j}{i}\binom{k-i}{j-i}\frac{k!(j-i)!}{(k-i)!j!}\&=\sum^{n}_{k=i}g_{k}\sum^{k}_{j=i}(-1)^{j-i}\binom{k}{i}\binom{k-i}{j-i}\&=\sum^{n}_{k=i}\binom{k}{i}g_{k}\sum^{k-i}_{j=0}(-1)^{j}\binom{k-i}{j}\&=\sum^{n}_{k=i}\binom{k}{i}g_{k}(1-1)^{k-i}\&=g_{i} \end{aligned} \]

二项式反演

上一篇:20 秒识别、准确率96%!河南"小汤山"引入阿里 AI


下一篇:Qt5 编译.exe成品, 将.exe和一堆.dll合成一个.exe进行发布