【学习笔记】反演杂烩
若有 $g_n = \sum\limits_{i = 1}^n a_{n, i} f_i$, 并且 $f_n = \sum\limits_{i = 1}^n b_{n, i} g_i$，则称 $f$ 和 $g$ 可以反演。证明带就完事了。
经典套路是 dp 容斥系数。
二项式反演
广义容斥。
「恰好」与「至多」：
$$f_n = \sum\limits_{i = 0}^n \binom{n}{i} g_i \Longleftrightarrow g_n = \sum\limits_{i = 0}^n (-1)^{n - i} \binom{n}{i} f_i$$
「恰好」与「至少」：
$$f_k = \sum\limits_{i = k}^n \binom{i}{k} g_i \Longleftrightarrow g_k = \sum\limits_{i = k}^n (-1)^{i - k} \binom{i}{k} f_i$$
$\min-\max$ 容斥
$$max(S) = \sum\limits_{T \subseteq S} (-1)^{|T| + 1} min(T) \Longleftrightarrow min(S) = \sum\limits_{T \subseteq S} (-1)^{|T| + 1} max(T)$$
证明大概考虑设 $\max(S) = x$，只有 $T = {x}$ 时的 $\min(T)$ 为 $x$，其余时候必然存在一个 $y$ 使得 $\min(T \cup {y}) = \min(T)$，就抵消了
这玩意还能应用到期望上去：套个 $E()$ 就好。
一般来说不用真的枚举集合，信息只和集合大小有关。
推广：通过求 $\min$ 来求 $kth\ \max$
$$kth\ \max(S) = \sum\limits_{T \subseteq S} (-1)^{|T| - k} \binom{|T| - 1}{k - 1} \min(T)$$
子集反演
就是 FMT 和 FMI。
$$f_S = \sum\limits_{T \subseteq S} g_T \Longleftrightarrow g_S = \sum\limits_{T \subseteq S} (-1)^{|S| - |T|} f_T$$
特别的：
$$\sum\limits_{T \subseteq S} (-1)^{|T|} = [S == \emptyset]$$
莫比乌斯反演
本质是质因子集合的 FMT 和 FMI。
$$f(n) = \sum\limits_{d | n} g(d) \Longleftrightarrow g(n) = \sum\limits_{d | n} \mu(d) f(\frac{n}{d})$$
$$f(n) = \sum\limits_{n | d} g(d) \Longleftrightarrow g(n) = \sum\limits_{n | d} \mu(n) f(\frac{d}{n})$$
最常用的：
$$\sum\limits_{d \mid n} \mu(d) = [n == 1]$$
斯特林反演
$$f_n = \sum\limits_{i = 1}^n {n \brace i} g_i \Longleftrightarrow g_n = \sum\limits_{i = 1}^n (-1)^{n - i} {n \brack i} f_i$$
单位根反演
$$[k \mid n] = \frac{1}{k} \sum\limits_{i = 0}^{k - 1} \omega_k^{ni}$$
证明：若 $k \mid n$，那么：
$$\frac{1}{k} \sum\limits_{i = 0}^{k - 1} \omega_k^{ni} = \frac{1}{k} \sum\limits_{i = 0}^{k - 1} (\omega_k^n)^i = \frac{1}{k} \sum\limits_{i = 0}^{k - 1} \omega_k^0 = 1$$
若 $k \nmid n$，那么根据等比数列求和有：
$$\frac{1}{k} \sum\limits_{i = 0}^{k - 1} \omega_k^{ni} = \frac{1}{k} \frac{\omega_k^{nk} - \omega_k^0}{\omega_k^n - 1} = 0$$
应用于 $O(k)$ 提取多项式所有下标为 $k$ 倍数的项或系数（设第 $i$ 项系数为 $a_i$，下面是提系数）：
$$\sum\limits_{i = 0}^{n / k} [x^{ik}] f(x)$$
$$= \sum\limits_{i = 0}^n [k \mid i] [x^i] f(x)$$
$$= \sum\limits_{i = 0}^n \frac{1}{k} \sum\limits_{j = 0}^{k - 1} \omega_k^{ij} [x^i] f(x)$$
$$= \frac{1}{k} \sum\limits_{j = 0}^{k - 1} \sum\limits_{i = 0}^n a_i (\omega_k^j)^i$$
$$= \frac{1}{k} \sum\limits_{j = 0}^{k - 1} f(\omega_{k}^j)$$
现推也非常方便！「提取项」一个道理，就现推一下吧，总是能把单位根搞成函数自变量的。
sol: 题意真是文字游戏。就是选若干个子集满足交集大小是 $k$ 的倍数的方案数。本题 $k = 4$。
交集至少为 $k$ 的方案数为 $f(k) = \binom{n}{k} (2^{2^{n - k}} - 1)$，恰好为 $k$ 的方案数为 $g(k)$，可以二项式反演出来，但 1e7…… 你也没法 NTT 是吧，所以我们只能把 $f$ 带到 $g$ 里去啦：
$ans = \sum\limits_{4 \mid k} g(k)$
$= \frac{1}{4} \sum\limits_k \sum\limits_{i = 0}^3 \omega_4^{ki} g(k)$
$= \frac{1}{4} \sum\limits_k \sum\limits_{i = 0}^3 \omega_4^{ki} \sum\limits_{j = k}^n \binom{j}{k} (-1)^{j - k} f(j)$
$= \frac{1}{4} \sum\limits_{j = 0}^n (-1)^j f(j) \sum\limits_{i = 0}^3 \sum\limits_{k = 0}^j (-1)^k \binom{j}{k} \omega_4^{ki}$
$= \frac{1}{4} \sum\limits_{j = 0}^n (-1)^j f(j) \sum\limits_{i = 0}^3 (-\omega_4^i + 1)^j$
$O(nK)$
题解里说的「构造容斥系数」也是实用 trick！