M_sea

各种反演的总结
由于一些原因,本篇文章没有证明。反演如果有应用可以用来求一些和子集有关的东西。参考文章http://vfleaki...
扫描右侧二维码阅读全文
16
2019/07

各种反演的总结

由于一些原因,本篇文章没有证明。

反演

如果有

$$ f_n=\sum_{i=0}^na_{n,i}g_i $$

已知 $g$ 求 $f$ 当然很简单了,而已知 $f$ 求 $g$ 的过程就叫做反演

一般来说反演只能上高斯消元,但是有一些特殊的形式可以很方便的反演。

二项式反演

内容

如果

$$ f_n=\sum_{i=0}^n\binom{n}{i}g_i $$

那么

$$ g_n=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f_i $$

应用

求不存在 $p_i=i$ 的排列 $p$ 的个数。

考虑设 $f_i$ 表示 $n$ 个数的排列的答案。

可以得到

$$ n!=\sum_{i=0}^n{n\choose i}f_i $$

设 $g_i=i!$ ,二项式反演得到

$$ f_n=\sum_{i=0}^n(-1)^{n-i}{n\choose i}g_i $$

暴力化简得到

$$ f_n=n!\sum_{i=0}^n\frac{(-1)^i}{i!} $$

莫比乌斯反演

内容

方向1

如果

$$ g(n)=\sum_{d|n}f(d) $$

那么

$$ f(n)=\sum_{d|n}\mu\left(\frac{n}{d}\right)g(d) $$

方向2

如果

$$ g(n)=\sum_{n|d}f(d) $$

那么

$$ f(n)=\sum_{n|d}\mu\left(\frac{n}{d}\right)g(d) $$

应用

用来求一些和约数有关的东西。

可以康康这里面的题目。

斯特林反演

内容

如果

$$ f_n=\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}g_i $$

那么

$$ g_n=\sum_{i=0}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}f_i $$

应用

一些组合计数题里可能会用到?

单位根反演

内容

$$ [n|k]=\frac{1}{n}\sum_{i=0}^{n-1}\omega_n^{ki} $$

应用

可以用来求一些和同余有关的东西。

一道毒瘤题

子集反演

内容

如果

$$ f(S)=\sum_{T\subseteq S}g(T) $$

那么

$$ g(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}f(T) $$

应用

可以用来求一些和子集有关的东西。

参考文章

最后修改:2019 年 07 月 23 日 07 : 23 PM

5 条评论

  1. Itst

    开头是不是写反了……

    1. M_sea
      @Itst

      我的锅,确实写反了 QAQ

      还有神仙 Itst 怎么看我的垃圾总结啊 /kel

  2. smy

    白兔之舞毒瘤?

    其实是不会做

    1. M_sea
      @smy

      不会做 + 1

      1. Karry5307
        @M_sea

        不会做+2

发表评论