二项式反演
引入
错排问题：\(n\) 个人排列。第 \(i\) 个人不能在位置 \(i\)，求合法排列数。
钦定 \(k\) 个人在自己位置上：
\[\sum_{k = 0}^n (-1)^k \begin{pmatrix}n\\k\end{pmatrix}(n - k)! \]定义 \(f(n)\) 为 \(n\) 个人的排列数，\(g(n)\) 为 \(n\) 个人的错排数。
\[\begin{aligned} f(n) &= \sum_{k = 0}^n \begin{pmatrix}n\\k\end{pmatrix} g(k)\\ \\ g(n) &= \sum_{k = 0}^n (-1)^{n - k} \begin{pmatrix}n\\k\end{pmatrix}f(k) \end{aligned} \]问题在于 \(f\) 能够快速计算，如何通过 \(f\) 反求 \(g\)。
有组合恒等式
\[\sum_{k = 0}^n(-1)^k\begin{pmatrix}n\\k\end{pmatrix} = [n = 0] \]说一句废话：
\[g(n) = \sum_{m = 0}^n [n - m = 0]\begin{pmatrix}n\\m\end{pmatrix} g(m) \]把 \([n - m = 0]\) 用上面的恒等式带掉：
\[\begin{aligned} g(n) &= \sum_{m = 0}^n \sum_{k = 0}^{n - m}(-1)^k\begin{pmatrix}n - m\\k\end{pmatrix}\begin{pmatrix}n\\m\end{pmatrix} g(m)\\ \\ &= \sum_{m = 0}^n \sum_{k = 0}^{n - m}(-1)^k\begin{pmatrix}n\\k\end{pmatrix}\begin{pmatrix}n - k\\m\end{pmatrix} g(m) & \text{考虑两个组合数的意义}\\ \\ &= \sum_{k = 0}^{n} (-1)^k\begin{pmatrix}n\\k\end{pmatrix}\sum_{m = 0}^{n - k}g(m)\begin{pmatrix}n - k\\m\end{pmatrix} \\ \\ &= \sum_{k = 0}^{n} (-1)^k\begin{pmatrix}n\\k\end{pmatrix}\sum_{m = 0}^{n - k}g(m)\begin{pmatrix}n - k\\m\end{pmatrix} \\ \\ &= \sum_{k = 0}^{n} (-1)^k\begin{pmatrix}n\\k\end{pmatrix}f(n - k) = \sum_{k = 0}^{n} (-1)^{n - k}\begin{pmatrix}n\\k\end{pmatrix}f(k) \\ \end{aligned} \]莫比乌斯反演
引入
周期问题：求长度为 \(n\) 的字符串且周期（最小循环节）恰为 \(n\) 的字符串个数，仅包含小写字母。
定义 \(f(n)\) 为长度为 \(n\) 的字符串个数，\(g(n)\) 为长度为 \(n\) 且周期恰为 \(n\) 的方案数。
\[f(n) = \sum_{d \mid n} g(n) \]显然有 \(f(n) = 26^n\)，怎么反演求 \(g\)？
设函数 \(\mu\) 满足
\[\sum_{d \mid n} \mu(d) = [n = 1] \]说一句废话：
\[\begin{aligned} g(n) &= \sum_{m \mid n} [\dfrac{n}{m} = 1] g(m)\\ \\ &= \sum_{m \mid n} \sum_{d \mid \frac{n}{m}}\mu(d) g(m)\\ \\ &= \sum_{m \mid n} \sum_{d \mid \frac{n}{m}}\mu(d) g(m)\\ \\ &= \sum_{d \mid n}\mu(d) \sum_{m \mid \frac{n}{d}} g(m)\\ \\ &= \sum_{d \mid n}\mu(d) f(\dfrac{n}{d}) = \sum_{d \mid n}\mu(\dfrac{n}{d}) f(d)\\ \end{aligned} \]子集反演
高维前缀和
二维前缀和：
for(int i = 1; i <= n; ++ i) {
for(int j = 1; j <= n; ++ j) {
a[i][j] += a[i - 1][j];
}
}
for(int i = 1; i <= n; ++ i) {
for(int j = 1; j <= n; ++ j) {
a[i][j] += a[i][j - 1];
}
}
三维前缀和：
for(int i = 1; i <= n; ++ i) {
for(int j = 1; j <= n; ++ j) {
for(int k = 1; k <= n; ++ k) {
a[i][j][k] += a[i - 1][j][k];
}
}
}
for(int i = 1; i <= n; ++ i) {
for(int j = 1; j <= n; ++ j) {
for(int k = 1; k <= n; ++ k) {
a[i][j][k] += a[i][j - 1][k];
}
}
}
for(int i = 1; i <= n; ++ i) {
for(int j = 1; j <= n; ++ j) {
for(int k = 1; k <= n; ++ k) {
a[i][j][k] += a[i][j][k - 1];
}
}
}
子集和：
用偏序的形式表示子集和，可以发现他就是一个 \(n\) 维，每个维度只有 01 的前缀和。
\[\sum_{T \subseteq S} a_T = \sum_{T_1 \le S_1\land T_1 \le S_1\land\cdots T_n \le S_n} a_T \]for(int i = 0; i < n; ++ i) { // 枚举维度，1011 用数组表示为 a[1][1][0][1]
for(int s = 0; s < 1 << n; ++ s) {
if(s >> i & 1) a[s] += a[s ^ 1 << i];
}
}
引入
题意：两个长度为 \(2^n\) 的数列 \(a_0, a_1, \cdots, a_{2^n - 1}\) 和 \(b_0, b_1, \cdots, b_{2^n - 1}\)。
求数列 \(c\)，其中
\[c_r= \sum_{p, q}[p\text{ or } q = r]a_pb_q \]把下标看作集合，拆开算贡献。
原式的 \(p \cup q = r\) 很难算，不妨先求出 \(c_r' = \sum_{p, q}[p\cup q \subseteq r]a_pb_q\) 之后再考虑反演。
\[\begin{aligned} c_r' &= \sum_{p, q}[p\cup q \subseteq r]a_pb_q\\ \\ &= \sum_{p}[p\subseteq r]a_p\sum_{q}[q\subseteq r]b_q\\ \\ &= a_p'b_q' \end{aligned} \]其中 \(a_p' = \sum_{i \subseteq p} a_i\)，显然可以高维前缀和 \(O(n2^n)\) 求出。
标签：begin,end,组合,20240820,mid,计数,pmatrix,aligned,sum From： https://www.cnblogs.com/Luxinze/p/18369306