修订日期：2023.12.3. 更改了很多本质上的错误。
建议首先阅读组合数学相关 Part 3. 容斥原理。
1. 本质与第一反演公式1.1. 定义反演是 (f) 表示 (g) ( o) (g) 表示 (f)。
已知 (g(n) = sum_{\i = 1} ^ n c_{n, i} f(i))，根据系数 (c_{i, j}) 可以反推出用 (g) 表示 (f) 的方法：(f(n) = sum_{\i = 1} ^ n d_{n, i} g(i))。这样，就算 (f) 无法直接求，也可以通过所有 (g(i)) 推出 (f(n))。上述二式互为反演公式。
1.2. 第一反演公式直接给出定理：如果存在 (n) 次多项式 (p, q) 分别满足以下公式：([x ^ n]p = sum_{\i = 1} ^ n c_{n, i} imes [x ^ i]q) 以及 ([x ^ n]q = sum_{\i = 1} ^ n d_{n, i} imes [x ^ i]p)，且 (c_{i, i}) 和 (d_{i, i} eq 0)，那么对于任意序列 (u, v)，都有：
[v_n = sum_{i = 1} ^ n c_{n, i} u_i Leftrightarrowu_n = sum_{i = 1} ^ n d_{n, i} v_i]如果将 (c, d) 写成矩阵 ( extbf{C}, extbf{D})，那么它是下三角矩阵。将 (p, q) 写成列向量 ( extbf{p}, extbf{q})，那么条件中的两个公式可以表示为 ( extbf{p} = extbf{Cq})，( extbf{q} = extbf{Dp})，即 ( extbf{p} = extbf{CDp} Rightarrow extbf{CD} = extbf{I})。由于 ( extbf{C}) 与 ( extbf{D}) 互逆，所以它们的行列式不为 (0)，而因为它们是下三角矩阵，因此一定有对角线元素不为 (0)，这解释了为什么 (c_{i, i}) 和 (d_{i, i} eq 0)。
只要我们找到任何一组符合条件的 (p, q) 与 (c, d)，就可以将 (p, q) 推广至任意 (n) 次多项式，因为 ( extbf{C}) 与 ( extbf{D}) 恒互逆，不随 (p, q) 的改变而改变。这说明为了证明某个反演公式成立，我们只需考虑一种方便的特殊非平凡情况即可。
[egin{bmatrix}c_{1, 1} & 0 & cdots & 0 & 0 \c_{2, 1} & c_{2, 2} & cdots & 0 & 0 \vdots & vdots & ddots & vdots & vdots \c_{n - 1, 1} & c_{n - 1, 2} & cdots & c_{n - 1, n - 1} & 0 \c_{n, 1} & c_{n, 2} & cdots & c_{n, n - 1} & c_{n, n}end{bmatrix}egin{bmatrix}q_1 \ q_2 \ vdots \ q_{n - 1} \ q_nend{bmatrix} =egin{bmatrix}p_1 \ p_2 \ vdots \ p_{n - 1} \ p_nend{bmatrix}][egin{bmatrix}c_{1, 1} & 0 & cdots & 0 & 0 \c_{2, 1} & c_{2, 2} & cdots & 0 & 0 \vdots & vdots & ddots & vdots & vdots \c_{n - 1, 1} & c_{n - 1, 2} & cdots & c_{n - 1, n - 1} & 0 \c_{n, 1} & c_{n, 2} & cdots & c_{n, n - 1} & c_{n, n}end{bmatrix}egin{bmatrix}d_{1, 1} & 0 & cdots & 0 & 0 \d_{2, 1} & d_{2, 2} & cdots & 0 & 0 \vdots & vdots & ddots & vdots & vdots \d_{n - 1, 1} & d_{n - 1, 2} & cdots & d_{n - 1, n - 1} & 0 \d_{n, 1} & d_{n, 2} & cdots & d_{n, n - 1} & d_{n, n}end{bmatrix}= mathbf{I}]2. 二项式反演2.1. 引入在把玩二项式定理的时候，尝试把 (x) 变成 (1+(x - 1)) 可能会有新的收获：
[x ^ n = (1 + x - 1) ^ n = sum_{i = 0} ^ n dbinom n i 1 ^ {n - i} (x - 1) ^ i = sum_{i = 0} ^ n dbinom n i (x - 1) ^ i]嗯？和反演公式的形式长得很像！那么试试能不能用 (x) 表示 (x - 1)：
[(x - 1) ^ n = sum_{i = 0} ^ n dbinom n i (-1) ^ {n - i} x ^ i]很好，令 (p_i = x ^ i)，(q_i = (x - 1) ^ i)，(c_{i, j} = dbinom i j)，(d_{i, j} = dbinom i j ( - 1) ^ {i - j})，那么我们就成功找到了一组反演公式，称为形式一。
[f_n = sum_{i = 0} ^ n dbinom n i g_i Leftrightarrowg_n = sum_{i = 0} ^ n (-1) ^ {n - i} dbinom n i f_i]代数化证明：
[egin{aligned}f_n = & sum_{i = 0} ^ n dbinom n i sum_{j = 0} ^ i (-1) ^ {i - j} dbinom i j f_j \= & sum_{j = 0} ^ n f_j sum_{i = j} ^ n (-1) ^ {i - j} dbinom n i dbinom i j \= & sum_{j = 0} ^ n f_j dbinom n j sum_{i = j} ^ n (-1) ^ {i - j} dbinom {n - j} {i - j} \= & sum_{j = 0} ^ n f_j dbinom n j sum_{t = 0} ^ {n - j} (-1) ^ t dbinom {n - j} tend{aligned}]众所周知，右边的 (sum) 当且仅当 (n - j = 0) 即 (j = n) 时为 (1)，否则为 (0)。因此 (f_n = sum_{\j = 0} ^ n f_n dbinom n j [n = j] = f_n)，证毕。
[egin{bmatrix}dbinom 0 0 & 0 & cdots & 0 & 0 \dbinom 1 0 & dbinom 1 1 & cdots & 0 & 0 \vdots & vdots & ddots & vdots & vdots \dbinom {n - 1} 0 & dbinom {n - 1} 1 & cdots & dbinom {n - 1} {n - 1} & 0 \dbinom n 0 & dbinom n 1 & cdots & dbinom n {n - 1} & dbinom n nend{bmatrix}egin{bmatrix}dbinom 0 0 & 0 & cdots & 0 & 0 \-dbinom 1 0 & dbinom 1 1 & cdots & 0 & 0 \vdots & vdots & ddots & vdots & vdots \(-1) ^ {n - 1}dbinom {n - 1} 0 & (-1) ^ {n - 2}dbinom {n - 1} 1 & cdots & dbinom {n - 1} {n - 1} & 0 \(-1) ^ n dbinom n 0 & (-1) ^ {n - 1} dbinom n 1 & cdots & -dbinom n {n - 1} & dbinom n nend{bmatrix}= mathbf{I}]如果将矩阵转置，那么还可以得到另一种更常用表示，形式二：
[f_i = sum_{j = i} ^ n dbinom j i g_j Leftrightarrowg_i = sum_{j = i} ^ n (-1) ^ {j - i} dbinom j i f_j][egin{bmatrix}dbinom 0 0 & dbinom 1 0 & cdots & dbinom {n - 1} 0 & dbinom n 0 \0 & dbinom 1 1 & cdots & dbinom {n - 1} 1 & dbinom n 1 \vdots & vdots & ddots & vdots & vdots \0 & 0 & cdots & dbinom {n - 1} {n - 1} & dbinom n {n - 1} \0 & 0 & cdots & 0 & dbinom n nend{bmatrix}egin{bmatrix}dbinom 0 0 & -dbinom 1 0 & cdots & (-1) ^ {n - 1}dbinom {n - 1} 0 & (-1) ^ n dbinom n 0 \0 & dbinom 1 1 & cdots & (-1) ^ {n - 2}dbinom {n - 1} 1 & (-1) ^ {n - 1} dbinom n 1 \vdots & vdots & ddots & vdots & vdots \0 & 0 & cdots & dbinom {n - 1} {n - 1} & -dbinom n {n - 1} \0 & 0 & cdots & 0 & dbinom n nend{bmatrix}= mathbf{I}]2.2. 组合意义二项式反演的本质是容斥原理。(f_i) 表示钦定选 (i) 个的方案数，(g_i) 表示恰好选 (i) 个的方案数。对于任意的 (igeq n) ，(g_i) 在 (f_n) 中被计算了 (dbinom{i}{n}) 次，故 (f_n=sum_{\i=n} ^ mdbinom i n g_i) ，其中 (m) 是数目上界，恰好对应形式二。这说明可以使用 (sum_{\i = n} ^ m (-1) ^ {i - n} dbinom i n f_i) 求出 (g_n)。
注意：在定义中，(f_n) 表示先钦定 (n) 个，再统计钦定情况如此的方案数，其中会包含重复的方案，因为一个方案可以有多种钦定情况。具体地，对于恰好选择 (i) 个的方案，钦定情况数为 (dbinom i n) ，故 (g_i) 在 (f_n) 中被计算了 (dbinom n i) 次。切勿将 (f_n) 理解为普通的 (g_i) 的后缀和。
很多初学者最大的误区在于将 (f_n) 理解为至少选 (n) 个的方案数，这是完全错误的（如果真是这样那么 (g_n) 不就等于 (f_n-f_{n+1}) 么，还要二项式反演干啥 = . =）。
2.3. 应用OI 界二项式反演的应用常结合动态规划：DP 求出钦定选择 (i) 个元素时的总方案，然后就可以通过二项式反演得到恰好选择 (i) 个元素时的方案数。综上所述，我们总结出二项式定理的核心：通过二项式系数的容斥进行 “钦定” 和 “恰好” 的转换。
2.3.1. 错排问题(n) 个人排列，求每个人都恰好站错的方案数。即求 (sum_{\p} [forall i, p_i eq i])。
设 (g_n) 表示 (n) 个人的错排方案数，而 (f_n) 表示所有排列方案数即 (n!)。那么有 (f_n = sum_{\i = 0} ^ n dbinom n i g_i)，(i) 的意义是枚举站错的人的个数。反演得到 (g_n = sum_{\i = 0} ^ n (-1) ^ {n-i} dbinom n i f_i = sum_{i=0} ^ n (-1) ^ {n - i} dfrac {n!} {(n-i)!})（组合数分母上的 (i!) 与 (f_i) 抵消了）。
2.3.2. 染色问题 I（一维）(n) 个格子，(k) 种颜色，相邻格子颜色不同，每个颜色至少出现一次，求方案数。
设 (g_k) 表示恰好出现 (k) 个颜色的方案数，(f_k) 表示 (k) 个颜色的总方案数，即 (k imes (k - 1) ^ {n - 1})。有
[f_k = sum_{\i = 0} ^ k dbinom k i g_i]反演得到 (g_k = sum_{\i = 0}^k(-1) ^ {k - i} dbinom k i f_i)。可以 (mathcal{O}(klog n)) 计算。
2.3.3. 染色问题 II（二维）(n imes m) 个格子，(1) 种颜色，每行和每列至少有一个格子被涂色，求方案数。
设 (g_{i, j}) 表示恰好有 (i) 行 (j) 列被涂色的方案数，(f_{i, j}) 表示 (i) 行 (j) 列被涂色的方案数即 (2 ^ {ij})，有
[f_{n, m} = sum_{\i = 0} ^ n dbinom n i sum_{\j = 0} ^ m dbinom m j g_{i, j}]对 (i) 和 (j) 分别二项式反演，有
[g_{n, m} = sum_{\i = 0} ^ n sum_{\j = 0} ^ m (-1) ^ {(n - i) + (m - j)} dbinom n i dbinom m jf_{i,j}]2.3.4. 染色问题 III（三维）(n imes m) 个格子，(k) 种颜色，每行和每列至少一个格子被涂色，每个颜色至少出现一次，格子可不被涂色，求方案数。
请读者结合染色问题 I. 与 II. 自行思考。设 (g_{n, m, k}) 表示恰有 (n) 行 (m) 列至少有一个格子被涂上颜色，且恰有 (k) 种颜色的方案数，(f_{n, m, k}) 表示总方案数 ((k + 1) ^ {nm})。
[f_{n, m, k} = sum_{i = 0} ^ n sum_{j = 0} ^ m sum_{p = 0} ^ k dbinom n i dbinom m j dbinom k p g_{i, j, k}][g_{n, m, k} = sum_{i = 0} ^ n sum_{j = 0} ^ m sum_{p = 0} ^ k (-1) ^ {n + m + k - i - j - p} dbinom n i dbinom m j dbinom k p (p + 1) ^ {ij}]直接计算 (n ^ 3)，可以通过二项式定理化简减小复杂度。
2.4. 参考文章GXZlegend —— 二项式反演及其应用（推荐）。liu_jiangwen ——111111 组合数学——二项式反演。Icyfrog —— 二项式反演入门。WAautomaton —— 反演定理及其应用。2.5. 例题*I. P6478 [NOI Online #2 提高组] 游戏很不错的题目，可以用来入门二项式反演。设 (f_x) 为钦定 (x) 对祖先关系的情况总数，(g_x) 为答案，那么根据二项式反演有 (g_x = sum_{\i = x} ^ n (-1) ^ {i - x} dbinom i xf_i)。(f_x) 可以树形背包求，别忘了最后乘上 ((m-x)!)，因为剩下 (m-x) 对点对顺序任意。时间复杂度 (mathcal{O}(n^2))。
*II. P4859 已经没有什么好害怕的了和例题 I. 极度类似。DP 方法几乎一样，最后也都要乘以阶乘作为系数。实际上，上一题就是把本题搬到了树上。
const int mod = 1e9 + 9;const int N = 2e3 + 5;int n, k, ans, a[N], b[N], num[N], f[N], fc[N], ifc[N];void add(int &x, int y) {x += y, x >= mod && (x -= mod);}int ksm(int a, int b) {int s = 1;while(b) {if(b & 1) s = 1ll * s * a % mod;a = 1ll * a * a % mod, b >>= 1;} return s;}int main(){cin >> n >> k;if((n & 1) != (k & 1)) return puts("0"), 0;k = n + k >> 1, fc[0] = 1;for(int i = 1; i a[i];for(int i = 1; i > b[i];sort(a + 1, a + n + 1), sort(b + 1, b + n + 1);for(int i = 1; i b[num[i] + 1]) num[i]++;} f[0] = 1;for(int i = 1; i p >> k, w = ksm(3, (mod - 1) / k);ans = n * p % mod * ksm(p + 1, n - 1) % mod;for(int x = 0; x < k; x++) {ll om = ksm(w, x), pw = ksm(p * om + 1, n), c = inv(om);if(c == 1) sub = (sub + pw * (k * (k - 1) / 2 % mod)) % mod;else sub = (sub + pw * k % mod * inv(mod + c - 1)) % mod;} cout 1,d^2mid n \(-1)^{omega(n)}&mathrm{otherwise}end{cases})，其中 (omega(n)) 表示 (n) 本质不同质因子个数。它的积性是显然的。4.1.2. 狄利克雷卷积由于学习莫比乌斯反演之前需要学会狄利克雷卷积，所以就放在这了。狄利克雷卷积竟沦落到给莫比乌斯反演作铺垫（大雾）。
定义：设 (f,g) 是数论函数，定义它们的狄利克雷卷积为 (h(x)=sum_{\a imes b=x}f(a)g(b))，写作 (h=f*g)。显然的，狄利克雷卷积具有交换律，结合律和乘法分配律。它的另一种表达形式为 (h(x)=sum_{\dmid x}f(d)gleft(dfrac x d ight))，非常有用。
FMT 和 FWT 叫位运算卷积，FFT 和 NTT 叫加法卷积，不难发现狄利克雷卷积实际上是乘法卷积。它有如下性质：两个积性函数的狄利克雷卷积也是积性函数，积性函数的逆元也是积性函数。证明略。
4.1.3. 莫比乌斯函数因为莫比乌斯函数是积性函数，所以它可以由线性筛求得。莫比乌斯函数有以下几条性质：
[sum_{dmid n}mu(d)=egin{cases}1&n=1\0&n eq 1end{cases} ag{4.1}]首先 (n=1) 时显然，否则我们令 (n) 的本质不同质因数分别为 (p_1,p_2,cdots,p_k)，从中选取 (i) 个质数的方案数为 (dbinom ki)。由选奇数个方案数之和等于选偶数个方案数之和可知和为 (0)：(k>0) 时 (sum_{i=0}^k1^{k-i} imesdbinom k i imes (-1)^{i}=(1+(-1))^k=0)（二项式定定理）。因而证明了 (mu*1=epsilon)。
[varphi(n)=sum_{dmid n}d imes muleft(dfrac n d ight) ag{4.2}]该式子在推式子时比较有用。可以先证明 (varphi*1=mathrm{id})，两边同时卷积 (mu) 有 (varphi*(1*mu)=varphi*epsilon=varphi=mathrm{id}*mu)。得证。
变式：
[dfrac{varphi(n)}n=sum_{dmid n} dfrac{mu(d)}{d} ag{4.2.2}]令上式两端同除 (n) 即得。
[sum_{dmid gcd(i,j)}mu(d)=[gcd(i,j)=1] ag{4.3}]极其重要的一个柿子，是莫比乌斯反演的核心。将 (gcd(i,j)) 带入式 (4.1) 即得。
线性筛莫比乌斯函数：根据 (mu(n) imes mu(p)=-mu(n)=mu(np) (gcd(n,p)=1)) 可得。
mu[1] = 1;for(int i = 2; i < N; i++) {if(!vis[i]) pr[++cnt] = i, mu[i] = -1;for(int j = 1; j 3) 时画不出来，不过可以理解一下）。(k) 个集合相交形成的所有子集就是 (n) 的所有约数。比如说，如果有一块区域落在集合 (p_1) 和集合 (p_3) 中，那么它所表示的约数就是 (p_1p_3)。显然，如果 (xmid y)，那么区域 (y) 包含于区域 (x)。这里放上一张图，