介绍

二项式反演是一种特殊的容斥，用来解决 “恰好选 $k$ 个的方案有多少种” 的问题。

一般，我们可以求出 “至多/至少选 $k$ 个的方案有多少种” 的问题，由此可以得出恰好选 $k$ 个有多少种。

公式

设 $g_k$ 表示 至多 选 $k$ 个的方案数，$f_k$ 表示恰好选 $k$ 个的方案数。

$$f_k = \sum\limits_{i=0}^k (-1)^{k-i}C_k^i g_i$$

设 $g_k$ 表示 至少 选 $k$ 个的方案数，$f_k$ 表示恰好选 $k$ 个的方案数。

$$f_k = \sum\limits_{i=k}^n (-1)^{i-k}C_i^k g_i$$

其中，$n$ 是物品的总数量。

证明见这里。

例题

例1 错排问题

题意

求长度为 $n$ 的错排 permutation 的数量。

一个permutation 是错排permutation，当且仅当它不存在 $i$ 使得 $p_i=i$。

题解

求出 $g_i$ 代表最多有 $i$ 个 fixed point的数量，就有 $g_i = C_n^i (n-i)!$。

然后让 $f_i$ 为恰好有 $i$ 个 fixed point的数量。

求 $f_0$ 即可，复杂度为 $O(n)$。

例2 CF1342E

题意

给定一个 $n \times n$ 的国际象棋棋盘，要放 $n$ 个车在棋盘上，使得：

  1. 每个点都被覆盖到。
  2. 恰好有 $k$ 对车互相攻击（两个车互相攻击当且仅当两个车能直接攻击，比如中间隔了一个车就不算）。

求方案数，对 998244353 取模。

其中，$1 \leq n \leq 200000, 0 \leq k \leq \frac{n(n-1)}{2}$。

题解

首先，每个点都要被覆盖到说明要么每一行都有车，要么每一列都有车，并且这两种不能同时存在，除非 $k=0$。

所以我们假设每一行都有车，答案 $*2$ 即可（因为棋盘翻转一下就是每一列都有车了）。

现在每一行都有车了，可以发现要恰好 $k$ 对车互相攻击，我们需要恰好把这些车放进 $n-k$ 列。

但这样还是不好算，所以考虑二项式反演。

设 $g(i)$ 为：至少有 $i$ 个冲突（也就是至多放进 $n-i$ 列）中的方案数。

则 $g(i) = C_{n}^{n-i} * (n-i)^n$。

解释：先从 $n$ 列里面选择 $n-i$ 列，得到 $C_{n}^{n-i}$，然后每一行对应一个车，这个车可以放进选择的 $n-i$ 列里的任何一个，所以是 $(n-i)^n$。

然后根据

$$f_k = \sum\limits_{i=k}^n (-1)^{i-k}C_i^k g_i$$

容斥即可，答案为 $f_k*2$。

代码 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
 
Z fac[maxn], ifac[maxn];
Z C(int a, int b) {
    if (a < b) return 0;
    return fac[a] * ifac[b] * ifac[a-b];
}
 
int n;
ll k;
Z g(int i) {
    return C(n, n-i) * qpow(Z(n-i), n);
}
int main() {
    cin >> n >> k;
    k %= mod;
    fac[0] = ifac[0] = 1;
    for (int i = 1; i <= 2e5; i++) fac[i] = fac[i-1] * i;
    ifac[maxn-5] = 1/fac[maxn-5];
    for (int i = 2e5-1; i >= 1; i--) ifac[i] = ifac[i+1] * (i+1);
 
    if (k == 0) {
        cout << fac[n] << endl;
        return 0;
    }
 
    Z ans = 0;
    for (int i = k; i <= n; i++) {
        ans = ans + (((i-k)&1) ? -1 : 1) * C(i, k) * g(i);
    }
    cout << ans*2 << endl;
}