update:
2024.12.11 重新整理了 二项式反演
1. 反演的定义
反演就是从 \(g\) 表示 \(f\) 变为从 \(f\) 表示 \(g\) 。
当已知 \(f(n) = \displaystyle\sum_{i=1}^{n} {c_{n,i}}g(i)\) 时。若可以推出 \(g(n) = \displaystyle\sum_{i=1}^{n} {d_{n,i}}f(i)\) 时，可以由 \(f\) 推出 \(g\)。
则称这两式互为反演公式。
利用反演的本质是由于其反演后的 \(f(n)\) 较容易得到，进而反演出 \(g(n)\)。
2. 二项式反演
2.1 概念
从容斥原理开始。
我们假设有 \(n\) 个集合 \(\{S_1,S_2,...,S_{n-1},S_n\}\)，设全集为 \(U\)，且其中任意 \(i\) 个集合的交集，并集的大小都相等。
我们设 \(g(x)\) 是任意 \(x\) 个元素的交集大小，\(f(x)\) 是任意 \(x\) 个元素补集的交集大小。
普通容斥原理就是
\[\left|\displaystyle\bigcup_{i=1}^n S_i\right| = (-1)^{|T| - 1}\left|\displaystyle\bigcap_{i=1}^{|T|} S_{T_i}\right|
\]
我们设 \(|S_i|\) 的补集为 \(|\overline{S_i}|\)。则
\[\left|\displaystyle\bigcup_{i=1}^n S_i\right| = |U| - \left|\displaystyle\bigcap_{i=1}^n \overline{S_i}\right|
\]
即
\[\begin{aligned}\left|\displaystyle\bigcap_{i=1}^n \overline{S_i}\right|
&= |U| - \left|\displaystyle\bigcup_{i=1}^n S_i\right|
\end{aligned}\]
类似的可以得到
\[\begin{aligned}\left|\displaystyle\bigcap_{i=1}^n S_i\right|
&= |U| - \left|\displaystyle\bigcup_{i=1}^n \overline{S_i}\right|
\end{aligned}\]
我们把 \(f(0)\) 与 \(g(0)\) 设为 \(|U|\)。则
\[f(n) = \left|\displaystyle\bigcap_{i=1}^n S_i\right| = |U| - \left|\displaystyle\bigcup_{i=1}^n \overline{S_i}\right| = |U| + (-1)^{|T|}\left|\displaystyle\bigcap_{i=1}^{|T|} \overline{S_{T_i}}\right| = \sum_{i=0}^{n} (-1)^i\dbinom{n}{i}g(i)
\]
\[g(n) = |U| - (-1)^{|T| - 1}\left|\displaystyle\bigcap_{i=1}^{|T|} S_{T_i}\right| = |U| + (-1)^{|T|}\left|\displaystyle\bigcap_{i=1}^{|T|} S_{T_i}\right| = \sum_{i=0}^{n} (-1)^i\dbinom{n}{i}f(i)
\]
我们就得到了优美的初始二项式反演式子：
\[f(n) = \sum_{i=0}^{n} (-1)^i\dbinom{n}{i}g(i) \Leftrightarrow g(n) = \sum_{i=0}^{n} (-1)^i\dbinom{n}{i}f(i)
\]
适当转换一下：
\[f(n) = \sum_{i=0}^{n}\dbinom{n}{i}g(i) \Leftrightarrow g(n) = \sum_{i=0}^{n} (-1)^{n-i}\dbinom{n}{i}f(i)
\]
再变一下：
\[f(n) = \sum_{i=m}^{n} \dbinom{n}{i}g(i) \Leftrightarrow g(n) = \sum_{i=m}^{n} (-1)^{n-i} \dbinom{n}{i}f(i)
\]
最后可以得到最常用的式子：
\[f(n) = \sum_{i=n}^m \dbinom{i}{n}g(i) \Leftrightarrow g(n) = \sum_{i=n}^m (-1)^{i-n} \dbinom{i}{n}f(i)
\]
证明：将右式代入左式得：
\[\begin{aligned} f(n)
&= \sum_{i=n}^m \dbinom{i}{n}\sum_{j=i}^{m}(-1)^{j - i} \dbinom{j}{i}f(j) \\
&= \sum_{i=n}^m\sum_{j=i}^{m}f(j)(-1)^{j - i} \dbinom{j}{i}\dbinom{i}{n} \\
&= \sum_{j=n}^{m}f(j)\sum_{i=n}^j(-1)^{j - i} \dbinom{j}{n}\dbinom{j - n}{j - i}\\
&= \sum_{j=n}^{m}\dbinom{j}{n}f(j)\sum_{i=n}^j(-1)^{j - i}\dbinom{j - n}{i - n} \\
&= \sum_{j=n}^{m}\dbinom{j}{n}f(j)\sum_{i=0}^{j-n}(-1)^{j - n + i}\dbinom{j - n}{i} \\
&= \sum_{j=n}^{m}\dbinom{j}{n}f(j)(-1)^{j-n}\ \boxed{\sum_{i=0}^{j-n}(-1)^i\dbinom{j - n}{i}} \\
&= \sum_{j=n}^{m}\dbinom{j}{n}f(j)(-1)^{j-n}\ \boxed{(1 - 1)^{j - n}} \\
&= \sum_{j=n}^{m}\dbinom{j}{n}f(j)(-1)^{j-n}[j = n] \\
&= \dbinom{n}{n}(-1)^0f(n) \\
&= f(n) \\
\end{aligned}\]
利用二项式定理证明，这也是其名字的由来，得证。
注：以上四个式子都可以用上述方法证明
2.2 应用与扩展
一般来说，我们将 \(f(n)\) 表示钦定选 \(n\) 个，剩下的随便，\(g(n)\) 表示恰好选定 \(n\) 个，则对于 \(i\geq n\) 都有 \(\dbinom{i}{n}\) 的贡献，即：
\[f(n) = \displaystyle\sum_{i=n}^{m}\dbinom{i}{n}g(i)
\]
注意，\(f(n)\) 不可被理解为至少选 \(n\) 个，不是简单的后缀和，\(f(n)\) 中的方案是有重复的，即一种方案有多种钦定方式。具体的，恰好选定 \(i\) 个的方案中，有 \(\dbinom{i}{n}\) 中钦定方式。
运用这个式子我们可以反演出 \(g(n)\) 的表达式，从而求出答案，至于 \(f\) 的求法，一般为推式子或 DP。
例题：P10596 BZOJ2839 集合计数
设 \(f(n)\) 表示钦定选 \(n\) 个的方案数，则有 \(f(i) = \dbinom{n}{i}(2^{2^{n - i}} - 1)\)，钦定后所有包含 \(i\) 个元素的集合有 \(2^{n - i}\) 个。
答案就是 \(g(n)\) 表示恰好选定 \(n\) 个的方案数，有 \(g(n) = \displaystyle\sum_{i=n}^m (-1)^{i-n}\dbinom{i}{n}f(i)\)。
复杂度 \(\mathcal{O}(n\log{V} + k\log{V})\)。
代码
2.2.1 多维二项式反演
形如 \(f(n,m) = \displaystyle\sum_{i=n}^x\displaystyle\sum_{j=m}^y\dbinom{i}{n}\dbinom{j}{m}g(i,j) \Leftrightarrow g(n,m) = \displaystyle\sum_{i=n}^x(-1)^{i-n}\dbinom{i}{n}\displaystyle\sum_{j=m}^y(-1)^{j-m}\dbinom{j}{m}f(i,j)\)
2.3 例题
I P4859 已经没有什么好害怕的了
首先有若 \(2 \nmid n - k\)，则一定无解，否则有 \(\frac{n + k} 2\) 组 \(a_i > b_i\)，考虑将问题转化为钦定 \(k\) 组。
考虑 DP，先排个序，设 \(f_{i,j}\) 表示前 \(i\) 组，钦定有 \(j\) 组 \(a_i > b_i\) 的方案数，有转移：
\(f_{i,j} = f_{i-1,j} + f_{i-1,j-1} \times x\)，其中 \(x\) 表示 \(b\) 中 \(\leq a_i\) 的数的个数。
设 \(F(i)\) 表示钦定 \(n\) 组中钦定 \(i\) 组 \(a > b\) 的方案数，则有 \(F(i) = f_{n,i} \times (n - i)!\)。
反演下，得到 \(G(n) = \displaystyle\sum_{i=n}^m (-1)^{i-n}\dbinom{i}{n}F(i)\)，答案即为 \(G(\frac {n + k} 2)\)。
复杂度 \(\mathcal{O}(n^2)\)。
代码
II [ABC266G] Yet Another RGB Sequence
我们设 \(f(n)\) 为钦定 \(n\) 个 rg 的方案数，有 \(f(n) = \dbinom{R + G + B - n}{n}\dbinom{R + G + B - 2n}{R - n}\dbinom{G + B - n}{G - n}\)。
然后反演即可，复杂度 \(\mathcal{O}(n)\)。
代码
III P6076 [JSOI2015] 染色问题
三个限制，每个限制单独看都很能反演，考虑多维二项式反演。
设 \(f(n,m,k)\) 表示钦定 \(n\) 行不染色，\(m\) 列不染色，\(k\) 种颜色不选，则有 \(f(i,j,k) = (c - k + 1)^{(n - i)(m - j)}\dbinom{n}{i}\dbinom{m}{j}\dbinom{c}{k}\)。
反演下，得到
\[g(n,m,k) = \sum_{i=n}^x\sum_{j=m}^y\sum_{l=k}^z(-1)^{(i-n)+(j-m)+(l-k)} \dbinom{i}{n}\dbinom{j}{m}\dbinom{l}{k} f(i,j,l)
\]
我们要求的答案即为：
\[\begin{aligned}
g(0,0,0) &= \sum_{j=0}^y\sum_{l=0}^z(-1)^{j+l}\dbinom{c}{l}\dbinom{m}{j}\boxed{\sum_{i=0}^x\dbinom{n}{i}(-1)^{i}(c - l + 1)^{(n - i)(m - j)}}\\
&= \sum_{j=0}^y\sum_{l=0}^z(-1)^{j+l}\dbinom{c}{l}\dbinom{m}{j}[(c - l + 1)^{m - j} - 1]^n \\
\end{aligned}
\]
复杂度 \(\mathcal{O}(nm\log{V})\)。
代码
IV P6478 [NOI Online #2 提高组] 游戏
恰好不是很好求，转为求钦定非平局回合数为 \(k\) 的方案数，可以树形 DP \(\mathcal{O}(n^2)\) 求。
具体的，设 \(f_{i,j}\) 表示在 \(i\) 这棵子树内钦定非平局回合数为 \(j\) 的方案数。
对于 \(x\)，若 \(x\) 不造成贡献，可以直接背包，否则设 \(c_{x,0/1}\) 表示 \(x\) 子树内 0/1 的节点个数，有：\(f_{i,j} = f_{i,j-1} \times (c_{x,a_x \bigoplus 1} - j + 1)\)。
Trick，树形背包 \(\mathcal{O}(n^2)\) 写法： \(\max(1,i - siz_x) - \min(i,siz_y)\)。
对于每个询问，直接反演即可，复杂度 \(\mathcal{O}(n^2)\)。
代码
V CF1228E Another Filling the Grid
裸的，可以做到 \(\mathcal{O}(n\log{V})\)。
VI P10597 BZOJ4665 小 w 的喜糖
刚开始看错题了，难甭
首先，正面不是很好做，考虑有 \(k\) 个人与原来的种类数相同。
设 \(f(n)\) 表示钦定 \(k\) 与原来相同的方案数，这样答案就为 \(g(0) = \displaystyle\sum_{i=0}^n(-1)^if(i)\)。
考虑如何求 \(f\)，设 \(f_{i,j}\) 表示前 \(i\) 种糖钦定有 \(j\) 个人与原来相同，对于每一种颜色，我们枚举该颜色与原来相同的人数 \(k\)，有：
\[f_{i,j} = \displaystyle\sum_{k=0}^{\min(c_i,j)}f_{i,j - k}\dbinom{c_i}{k}\dbinom{s - k}{c_i - k}
\]
其中 \(s\) 表示前 \(i\) 个 \(c_i\) 的和，总复杂度 \(\mathcal{O}(n^2)\)。
代码
VII CF997C Sky Full of Stars
正着做比较难，考虑总数减去 恰好没有一行或一列是同一种颜色 的方案数。
设 \(f(i,j)\) 表示钦定 \(i\) 行 \(j\) 列是同一种颜色，其他随意选的方案数，有：
\[f(i,j) = \begin{cases}
3^{i + j} \times 3^{(n - i)(n - j)}\dbinom{n}{i}\dbinom{n}{j} &{i = 0 \lor j = 0} \\
3 \times 3^{(n - i)(n - j)}\dbinom{n}{i}\dbinom{n}{j} &{\mathrm{other}} \\
\end{cases}\]
反演下我们要的是 \(g(0,0) = \displaystyle\sum_{i=0}^n(-1)^i\ \boxed{\displaystyle\sum_{j=0}^n(-1)^jf(i,j)}\)，框里的式子先将 \(\dbinom{n}{i}\) 提出来，得到：
\[\begin{aligned}
&= \boxed{\sum_{j=0}^n\dbinom{n}{j}(-1)^j 3\times3^{(n-i)(n-j)}} - 3^{1 + n(n-i)} + 3^{i + n(n-i)} \\
&= 3 \times \left(3^{n - i} - 1\right)^n - 3^{1 + n(n-i)} + 3^{i + n(n-i)}
\end{aligned}\]
将 \(i = 0\) 的单独算，最后即 \(3^{n^2} - ans\)，总复杂度 \(\mathcal{O}(n\log{V})\)。
代码
VIII P3270 [JLOI2016] 成绩比较
首先恰好 \(k\) 位同学被碾压不好求，考虑反演，设 \(f(i)\) 表示钦定 \(i\) 位同学被碾压的方案数，\(g(i)\) 表示恰好 \(i\) 位同学被碾压的方案数，有。
\[f(k) = \displaystyle\sum_{i=k}^n\dbinom{i}{k}g(i) \Leftrightarrow g(k) = \displaystyle\sum_{i=k}^n(-1)^{i-k}\dbinom{i}{k}f(i)
\]
然后考虑 \(f(k)\) 怎么求，每个课程是独立的，可以先只考虑一个，最后将所有课程的方案数乘一起即可。
设当前课程最高分为 \(U\)，\(B\) 神排名为 \(R\)，则除了我们钦定的 \(k\) 个人分数比 \(B\) 神小，还存在 \(n - 1 - (R - 1) - k\) 个人分数比 \(B\) 神小，有 \(\dbinom{n - 1 - k}{n - k - R}\) 种方案，然后我们可以枚举 \(B\) 神此课程的分数，即 \(\displaystyle\sum_{i=1}^Ui^{n - R}(U - i)^{R - 1}\)，这样枚举是基于值域的，考虑怎么优化，先推下式子。
\[\begin{aligned}\displaystyle\sum_{i=1}^Ui^{n - R}(U - i)^{R - 1}
&= \displaystyle\sum_{i=1}^Ui^{n - R}\sum_{j=0}^{R-1}\dbinom{R - 1}{j}U^j\ \color{Red}\boxed{(-i) ^{R - 1 - j}} \\
&= \sum_{j=0}^{R-1}\dbinom{R - 1}{j}U^j(-1)^{R - j - 1}\displaystyle\sum_{i=1}^Ui^{n - j - 1} \\
\end{aligned}
\]
左边可以直接枚举，右边是一些自然数次幂和的形式，可以直接拉插。
前半部分复杂度是 \(\mathcal{O}(n^2)\) 的，后半部分仅与每门课程相关，复杂度 \(\mathcal{O}(n^3\log{n})\)。
总复杂度 \(\mathcal{O}(n^3\log{n})\)，但是这个傻子懒，拉插写的 \(\mathcal{O}(n^2)\)，总 \(\mathcal{O}(n^4)\)，也能过。
自己犯的几个错误：二项式定理没拆 \(-1\)（上述框住的），打代码拉插的 \(y\) 没乘（难绷）。
代码
2.4 参考文章
二项式反演及其应用 - GXZlegend
反演与狄利克雷卷积 - Alex_wei
容斥与反演技巧（一）- 云浅知处
3. 莫比乌斯反演
3.4 杜教筛
4.1 杜教筛算法
一个求积性函数前缀和的优化方法 \(O(n^{\frac{2}{3}})\)
建议先学前面的反演知识。
杜教筛的式子是很自然的推法，首先我们假设要求 \(f(n)\) 的前缀和(一般求前缀和是为了用于整除分块)，我们需要找到另一个积性函数 \(g\)，使得 \(g\) 与 \((f \ast g)\) 的前缀和都很好求(例如 \(I\) 或 \(id\))，我们设 \(S(n) = \sum_{i=1}^{n} f(i)\)。
则
\[\begin{aligned}\sum_{i=1}^{n} (f \ast g)(i) & = \sum_{i=1}^{n} \sum_{xy=i} g(x) \times f(y)\\
& = \sum_{i=1}^{n} \sum_{j=1}^{\lfloor \frac{n}{i}\rfloor} g(i) \times f(j)\\
& = \sum_{i=1}^{n} g(i) \sum_{j=1}^{\lfloor \frac{n}{i}\rfloor} f(j)\\
& = \sum_{i=1}^{n} g(i)S(\lfloor\frac{n}{i}\rfloor)\\
& = g(1)S(n) + \sum_{i=2}^{n} g(i)S(\lfloor\frac{n}{i}\rfloor)\\
\end{aligned}\]
移一下项得：
\[g(1)S(n) = \sum_{i=1}^{n} (f \ast g)(i) - \sum_{i=2}^{n} g(i)S(\lfloor\frac{n}{i}\rfloor)
\]
右边可以整除分块，直接求时间复杂度 \(O(n^{\frac{3}{4}})\)
可以先预处理前 \(n^{\frac{2}{3}}\)，再进行杜教筛，时间复杂度 \(O(n^{\frac{2}{3}})\)
证明：不会微积分，看不懂证明
4.2 小推柿子
\(\mu \cdot id^k,\varphi \cdot id^k\)
直接卷上 \(id^k\):
\((\mu \cdot id^k) \ast id^k = (\mu \cdot id^k) \ast (I \ast id^k) = (\mu \ast I) \cdot id^k = \epsilon\)
\((\varphi \cdot id^k) \ast id^k = (\varphi \cdot id^k) \ast (I \ast id^k) = (\varphi \ast I) \cdot id^k = id^{k+1}\)
\(\mu^2 \ast (\mu \cdot id)\)
卷上 \(id\)
\(\mu^2 \ast (\mu \cdot id) \ast id = \mu^2 \ast \epsilon = \mu^2\)
\(\mu^2\) 是好求的。
\(\sigma^k\)
由定义得： \(\sigma^k = \sum_{d|n} id^k = I \ast id^k\)
我们正着用杜教筛公式：
\(\sigma^k = I \ast id^k = \sum\limits_{i=1}^n i^k S(\left\lfloor\frac n i\right\rfloor) = \sum\limits_{i=1}^n i^k\left\lfloor\frac n i\right\rfloor\)
4.3 例题
I P4213 【模板】杜教筛
求 \(\mu\) 与 \(\varphi\) 的前缀和。
我们知道 \(\mu \ast I = \epsilon\)，设 \(S(n) = \sum_{i=1}^{n} \mu(i)\)
直接运用杜教筛公式得
\[\begin{aligned}
S(n) & = \sum_{i=1}^{n} \epsilon(i) - \sum_{i=2}^{n} 1 \times S(\lfloor\frac{n}{i}\rfloor)\\
& = 1 - \sum_{i=2}^{n} S(\lfloor\frac{n}{i}\rfloor)\\
\end{aligned}\]
我们又知道 \(\varphi \ast I = id\)，设 \(S(n) = \sum_{i=1}^{n} \varphi(i)\)
直接运用杜教筛公式得
\[\begin{aligned}
S(n) & = \sum_{i=1}^{n} i - \sum_{i=2}^{n} 1 \times S(\lfloor\frac{n}{i}\rfloor)\\
& = \frac{n(n+1)}{2} - \sum_{i=2}^{n} S(\lfloor\frac{n}{i}\rfloor)\\
\end{aligned}\]
预处理一下，用 \(map\) 或 \(unordered\) 记忆化即可。
代码
II [cogs] 3352. 平方前缀和
求 \(\sum_{i=1}^{n} \varphi(i^2)\)
基本上是裸的杜教筛
一个关于 \(\varphi\) 的性质：\(\varphi(ij) = \frac{\varphi(i)\varphi(j)gcd(i,j)}{\varphi(gcd(i,j))}\)
证明：该式本质上是容斥，\(\varphi\) 的原式子是，当 \(n = {p_1}^{c_1}\times {p_2}^{c_2} \times ··· \times {p_m}^{c_k}\)
\(\varphi(n) = n \times \prod_{i=1}^{m} (1 - \frac{1}{p_i})\)
这里式子就表示为先把 \(i\) 和 \(j\) 的质因数乘上在除去 \(i,j\) 的共同质因数，即 \(\varphi(gcd(i,j))\)，最后再消掉 \(gcd(i,j)\) 即可得到该式。
然后开始推式子：
\[\sum_{i=1}^{n} \varphi(i^2) = \sum_{i=1}^{n} i \times \varphi(i)
\]
不难发现该式等于 \(\varphi \cdot id\)
\[(\varphi \cdot id) \ast id = \sum_{d\mid n} d * \varphi(d) * \frac{n}{d} = n \times \sum_{d\mid n} \varphi(d) = id^2
\]
我们设 \(f(n) = n \times \varphi,S(n) = \sum_{i=1}^{n} f(i)\)
运用杜教筛公式可得：
\[S(n) = \sum_{i=1}^{n}i^2 - \sum_{i=2}^{n} i * S(\lfloor\frac n i\rfloor)
\]
\[= \frac{n(n+1)(2n+1)}{6} - \sum_{i=2}^{n} i * S(\lfloor\frac n i\rfloor)
\]
线性筛出前 \(n^{\frac{2}{3}}\) 项，整除分块即可
III P3768 简单的数学题
求 \(\sum_{i=1}^{n}\sum_{j=1}^{n} ij \times gcd(i,j)\)
类似这样直接加上 \(gcd(i,j)\) 的式子用欧拉反演会更容易些。
\[\begin{aligned}\sum_{i=1}^{n}\sum_{j=1}^{n} ij \times gcd(i,j)
& = \sum_{i=1}^{n}\sum_{j=1}^{n} ij \times \sum_{d\mid gcd(i,j)} \varphi(d)\\
& = \sum_{d=1}^{n}\varphi(d)d^2 \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor} i \times \sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}j\\
& = \sum_{d=1}^{n}\varphi(d)d^2 (\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor} i)^2\\
& = \sum_{d=1}^{n}\varphi(d)d^2 \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor} i^3\\
\end{aligned}\]
显然可以整除分块，数据范围很大，需要杜教筛。
只需考虑 \(f(n) = \sum_{d=1}^{n}\varphi(d)d^2\) 即 \(f = \varphi \cdot id^2\)。
这里的 \(id^2\) 很烦，考虑把它消去，只需卷积一个 \(id^2\) 即可。
证明：\((\varphi \cdot id^2) \ast id^2 = \sum_{d\mid n} \varphi(d)d^2(\frac{n}{d})^2 = n^2\sum_{d\mid n}\varphi(d) = n^3 = id^3\)，证毕。
推广一下：\((\varphi \cdot id^k) \ast id^k = id^{k+1}\)，直接用即可。
所以 \(f \ast id^2 = id^3\)，设 \(S(n) = \sum_{i=1}^{n}f(i)\)
。
则运用杜教筛公式得：
\[\begin{aligned}S(n)
& = \sum_{i=1}^n i^3 - \sum_{i=2}^n i^2 S(\lfloor\frac{n}{i}\rfloor)\\
& = (\frac{n(n+1)}{2})^2 - \sum_{i=2}^n i^2 S(\lfloor\frac{n}{i}\rfloor)\\
\end{aligned}\]
整除分块即可，注意取模求逆元。
代码