各种反演

· · 算法·理论

子集反演

公式

G _ S = \sum _ {T \subseteq S} F _ T \Longleftrightarrow F _ S = \sum _ {T \subseteq S} (-1) ^ {|S| - |T|} G _ T \tag {1} G _ S = \sum _ {T \supseteq S} F _ T \Longleftrightarrow F _ S = \sum _ {T \supseteq S} (-1) ^ {|T| - |S|} G _ T \tag {2}

证明

对于 (1) 式，考虑

\begin {align*} F _ S & = \sum _ {T \subseteq S} (-1) ^ {|S| - |T|} \sum _ {U \subseteq T} F _ U \\ & = \sum _ {U \subseteq S} \sum _ {U \subseteq T \subseteq S} (-1) ^ {|S| - |T|} \\ & = \sum _ {U \subseteq S} \sum _ {i = |U|} ^ {|S|} (-1) ^ {|S| - i} \binom {|S| - |U|} {|S| - i}\\ & = \sum _ {U \subseteq S} (1 - 1) ^ {|S| - |U|} \\ & = \sum _ {U \subseteq S} [|S| - |U| = 0] \\ &= F _ S \end {align*}

故原式成立。

对于 (2) 式证明同理。

二项式反演

公式

G _ i = \sum _ {j = 0} ^ i \binom i j F _ j \Longleftrightarrow F _ i = \sum _ {j = 0} ^ i (-1) ^ {i - j} \binom i j G _ j \tag {3} G _ i = \sum _ {j = i} ^ n \binom j i F _ j \Longleftrightarrow F _ i = \sum _ {j = i} ^ n (-1) ^ {j - i} \binom j i G _ j \tag {4}

证明

其实就是子集反演的特殊情况。

推导

对于 (3) 式，令 f (x) = \sum _ {n = 0} \frac {F _ n} {n!} x ^ n，g (x) = \sum _ {n = 0} \frac {G _ n} {n!} x ^ n，因为

G _ i = \sum _ {j = 0} ^ i \binom i j F _ j = \sum _ {j = 0} ^ i \frac {i!} {j! (i - j)!} F _ j \frac {G _ i} {i!} = \sum _ {j = 0} ^ i \frac 1 {(i - j)!} \cdot \frac {F _ j} {j!}

有

g (x) = f (x) \cdot \sum _ {n = 0} \frac {x ^ n} {n!} = f (x) \cdot e ^ x

故

f (x) = \frac {g (x)} {e ^ x} = g (x) \cdot e ^ {-x}

展开后

\frac {F _ i} {i!} = \sum _ {j = 0} ^ i \frac {(-1) ^ {i - j}} {(i - j)!} \cdot \frac {G _ j} {j!} F _ i = \sum _ {j = 0} ^ i (-1) ^ {i - j} \binom i j G _ j $$G _ i = \sum _ {j = i} ^ n \binom j i F _ j$$ 设 $f (x) = \sum _ {n = 0} F _ n n! x ^ n$，$g (x) = \sum _ {n = 0} G _ n n! x ^ n$，有 $$g (x) = f (x) \cdot \sum _ {n = 0} \frac {x ^ {-n}} {n!} = f (x) \cdot e ^ {\frac 1 x}$$ 则 $$g (x) = f (x) \cdot e ^ {-\frac 1 x}$$ 展开后 $$F _ i = \sum _ {j = i} ^ n (-1) ^ {j - i} \binom j i G _ j$$ $(4)$ 式得证。 ## 单位根反演 ### 公式 $$[k | n] = \frac 1 k \sum _ {i = 0} ^ {k - 1} \omega _ k ^ {in} \tag {5}$$ ### 证明 若 $k | n$，则 $\omega _ k ^ n = 1$，有 $$\frac 1 k \sum _ {i = 0} ^ {k - 1} \omega _ k ^ {in} = \frac 1 k \sum _ {i = 0} ^ {k - 1} (\omega _ k ^ n) ^ i = \frac 1 k \sum _ {i = 0} ^ {k - 1} 1 = \frac 1 k \cdot k = 1$$ 否则因为 $\omega _ k ^ {kn} = 1$，有 $$\frac 1 k \sum _ {i = 0} ^ {k - 1} \omega _ k ^ {in} = \frac 1 k \cdot \frac {1 - \omega _ k ^ {kn}} {1 - \omega _ k ^ n} = 0$$ 原式得证。 ## 莫比乌斯反演 ### 公式 $$G _ i = \sum _ {j | i} F _ j \Longleftrightarrow F _ i = \sum _ {j | i} \mu \left(\frac i j\right) G _ j \tag {6}$$ 或者也有另外一种形式 $$I * \mu = \epsilon \tag {7}$$ 即 $$[i = 1] = \sum _ {j | i} \mu (j) \tag {8}$$ ### 证明 对于 $(8)$ 式，考虑 $i$ 的每一个质因数 $p _ 1 ^ {c _ 1}, p _ 2 ^ {c _ 2}, \ldots, p _ k ^ {c _ k}$，记 $i ^ \prime = p _ 1 p _ 2 \cdots p _ k$，则 $$\sum _ {j | i} \mu (j) = \sum _ {j | i ^ \prime} \mu (j) = \sum _ {i = 0} ^ k \binom k i (-1) ^ i = (1 - 1) ^ k = [k = 0] = [n = 1]$$ 故 $(8)$ 成立，考虑证明 $(6)$： $$ \begin {align*} F _ i & = \sum _ {j | i} \mu \left (\frac i j\right) \sum _ {k | j} F _ k \\ & = \sum _ {k | i} F _ k \sum _ {k | j | i} \mu \left(\frac i j\right) \\ & = \sum _ {k | i} F _ k \sum _ {\frac i j | \frac i k} \mu \left(\frac i j\right) \\ & = \sum _ {k | i} F _ k \left[\frac i k = 1\right] \\ &= F _ i \end {align*} $$ 证毕。 ## 欧拉反演 ### 公式 $$I * \varphi = id \tag {9}$$ 即 $$i = \sum _ {j | i} \varphi (j) \tag {10}$$ ### 证明 $$ \begin {align*} i & = \sum _ {k = 1} ^ i 1 \\ & = \sum _ {k = 1} ^ i \sum _ {j = 1} ^ i [\gcd (i, k) = j] \\ & = \sum _ {j | i} \sum _ {k = 1} ^ i [\gcd (i, k) = j] \\ & = \sum _ {j | i} \sum _ {k = 1} ^ {\frac i j} \left[\gcd \left(\frac i j, k\right) = 1\right] \\ & = \sum _ {j | i} \varphi \left(\frac i j\right) \\ & = \sum _ {j | i} \varphi (j) \end {align*} $$ ## 拉格朗日反演 [见此](https://www.luogu.com.cn/article/dqgxyqx7)