先對(duì)反演和一些簡(jiǎn)單的應(yīng)用總結(jié)一些吧，更高的東西聯(lián)賽前來(lái)不及搞了（悲）

二項(xiàng)式反演

概要

二項(xiàng)式反演可以看作是一種特殊的子集反演，特殊之處在于一個(gè)集合的價(jià)值只與這個(gè)集合的大小有關(guān)。

• $f(n)=\sum\limits_{i=0}^n (-1)^i\dbinom{n}{i} g(i) \iff g(n)=\sum\limits_{i=0}^n (-1)^i\dbinom{n}{i}f(i) $

  • 最對(duì)稱的形式，證明就讓關(guān)系矩陣相乘，證明所得的矩陣是單位矩陣即可。
    關(guān)系矩陣\(A[n][i]=(-1)^i\dbinom{n}{i},A^{-1}[n][i]=(-1)^i\dbinom{n}{i}\)

• $f(n)=\sum\limits_{i=0}^n \dbinom{n}{i} g(i) \iff g(n)=\sum\limits_{i=0}^n (-1)^{n-i}\dbinom{n}{i}f(i) $

  • 一般來(lái)說(shuō)不會(huì)在左邊湊出\(-1\)，既然反演的充要條件是關(guān)系矩陣互逆，那么在矩乘的時(shí)候，把左邊的\((-1)^i\)直接推到右邊變成\((-1)^n\)那么右邊就變?yōu)榱?span id="w0obha2h00" class="math inline">\((-1)^{n+i}\)即\((-1)^{n-i}\)
    關(guān)系矩陣\(A[n][i]=\dbinom{n}{i},A^{-1}[n][i]=(-1)^{n-i}\dbinom{n}{i}\)
  • 這里的\(f(n)\)表示如果欽定某n個(gè)元素被選，實(shí)際上不一定把這n個(gè)元素全選上，而是選這n個(gè)元素的一個(gè)子集的方案數(shù)，\(g(n)\)表示恰好選某n個(gè)元素的方案數(shù)

• $f(n)=\sum\limits_{i=n}^N \dbinom{i}{n} g(i) \iff g(n)=\sum\limits_{i=n}^N (-1)^{i-n}\dbinom{i}{n}f(i) $

  • 先證明一個(gè)引理: 一對(duì)互逆的矩陣，轉(zhuǎn)置后仍然互逆

  \(AB=I\iff B^TA^T=I\iff A^TB^T=I\),第一步是根據(jù)轉(zhuǎn)置矩陣的性質(zhì)，第二步是因?yàn)樽竽娴扔谟夷?/p>

  因此這個(gè)式子就是上個(gè)式子的關(guān)系矩陣轉(zhuǎn)置后得到的,至于求和上下界的改變，只是把二項(xiàng)式系數(shù)值為0的部分給去掉了而已
  關(guān)系矩陣\(A[n][i]=\dbinom{i}{n},A^{-1}[n][i]=(-1)^{i-n}\dbinom{i}{n}\)

  • 這里的\(f(n)\)表示欽定某n個(gè)元素被選的方案數(shù)

NTT優(yōu)化

注意，把反演后式子中的二項(xiàng)式系數(shù)拆開(kāi)，就會(huì)發(fā)現(xiàn)一個(gè)加法卷積的形式，可以用ntt優(yōu)化。

單位根反演

就是一個(gè)式子：
\([n|k]=\dfrac{1}{n}\sum\limits_{i=0}^{n-1}(\omega_n^k)^i\)
證明分類討論\(n\)是否整除\(k\)，然后一個(gè)用等比數(shù)列求和公式，另一個(gè)值全為\(1\)

應(yīng)用

1. 一般用法就是把求和中含有取模的東西給換掉。
   但是一般來(lái)說(shuō)真正用單位根的情況很少，一般都是用膜意義下具有相同性質(zhì)的東西——原根
   原根的知識(shí)點(diǎn)這里
2. 用來(lái)加速加法卷積(即多項(xiàng)式乘法)