跳转至

容斥和反演

容斥和反演能够将一些不易直接统计的数字，转化为一些能够直接计算的数字乘以一些容斥系数。

子集反演

设全集 \(U=\{1,2,\cdots N\}\)，函数 \(f(S)\) 定义在 \(U\) 的所有子集 \(S\) 上。那么：

对于另一函数 \(g(S)\) 满足

\[ g(S)=\sum_{S\subseteq T}f(T) \tag 1 \]

有

\[ f(S)=\sum_{S\subseteq T}(-1)^{|T|-|S|}g(T) \tag 2 \]

对于另一函数 \(g(S)\) 满足

\[ g(S)=\sum_{T\subseteq S}f(T) \tag 1 \]

有

\[ f(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}g(T) \tag 2 \]
证明

注意到形式 \(1\) 和形式 \(2\) 等价，只需 \(f(S)\gets f(\overline S),\ g(S)\gets g(\overline S)\)。

现在证明形式 \(2\)。将 \((1)\) 代入 \((2)\)，即证：

\[ f(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}\sum_{V\subseteq T}f(V) \]

考虑 \(f(V)\) 对 \(f(S)\) 的贡献系数

\[ \begin{align*} \sum_{V\subseteq T\subseteq S}(-1)^{|S|-|T|}&=(-1)^{|S|}\sum_{i=|V|}^{|S|}\binom{|S|-|V|}{i-|V|}(-1)^{i}\\ &=(-1)^{|S|-|V|}\sum_{i=0}^{|S|-|V|}\binom{|S|-|V|}{i}(-1)^i\\ &=(-1)^{|S|-|V|}\big[V=S\big]\\ &=[V=S] \end{align*} \]

因此等式恒成立，得证。

一般的题目会给我们若干条限制，然后让我们满足指定数量的限制，求方案数。此时 \(f(S)\) 可以表示恰好满足 \(S\) 集合对应的所有限制，对应的方案数。由于“恰好”的限制过于严格，我们很难保证当前方案在满足 \(S\) 的情况下是否会满足其他的若干限制。这时候，我们就可以使用形式 \(2\) 中的 \(g(S)\)，它表示钦定（至少）满足 \(S\) 中的所有限制，对应的方案数。一般 \(g\) 都是容易求出的。然后，我们再根据反演的公式，就可以得到对应的 \(f\)。形式 \(2\) 的应用同理。

二项式反演

设函数 \(f(n)\) 是定义在 \([0,N]\) 的全体整数上，那么：

对于另一函数 \(g(n)\) 满足

\[ g(n)=\sum_{k=n}^{N}\binom{k}{n}f(k) \]

有

\[ f(n)=\sum_{k=n}^{N}\binom{k}{n}(-1)^{k-n}g(k) \]

对于另一函数 \(g(n)\) 满足

\[ g(n)=\sum_{k=0}^{n}\binom{n}{k}f(k) \]

有

\[ f(n)=\sum_{k=0}^{n}\binom{n}{k}(-1)^{n-k}g(k) \]

证明：我回头补上

二项式反演是子集反演的一种特殊形式，因此上面的那一段话仍然适用。需要注意的是，在二项式反演（形式 \(1\)）中 \(g(k)\) 不是“至少满足 \(k\) 个条件的方案数”（不然直接差分完事了），而是先随意钦定 \(k\) 个条件满足，剩下的随意；也就是说，对于每个 \(f(k)\) 都应该对 \(g(n)\) 产生 \(\binom{k}{n}\) 倍的贡献。

例题 经典错排

题意

求有多少个长度为 \(n\) 的排列，满足 \(\forall i,\ p_i\ne i\)。

有 \(n\) 个限制，第 \(i\) 个限制为 \(p_i=i\)，问恰好满足 \(0\) 个的方案数。

记钦定满足 \(k\) 个限制的方案数为 \(s_k\)，容易得到 \(s_k=\binom nk(n-k)!\)。

向后（形式 \(1\)）二项式反演即可。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#define int long long

using namespace std;
const int N = 50;

int n, ans;
int a[N];

int c(int a, int b) {
    int res = 1;
    for(int i = a; i >= a - b + 1; i--) res *= i;
    for(int i = b; i >= 1; i--) res /= i;
    return res;
}

int fact(int x) {
    int res = 1;
    for(int i = 1; i <= x; i++) res = res * i;
    return res;
}

signed main() {

    cin >> n;
    for(int i = 0; i <= n; i++) a[i] = c(n, i) * fact(n - i);

    for(int i = 0; i <= n; i += 2) ans += a[i];
    for(int i = 1; i <= n; i += 2) ans -= a[i];

    cout << ans << '\n';

    return 0;
}

P10596 BZOJ2839 集合计数

题意

设全集 \(U={1,2,\cdots n}\)，它有 \(2^n\) 个子集。现在要从这些子集中选取若干个（至少一个），使得它们交集的大小为 \(k\)。问选取的方案数，对 \(10^9+7\) 取模。

\(n\le 10^6,\ 0\le k\le n\)

注意到恰好 \(k\) 个不好做，但是钦定 \(k\) 个作为交集中的元素是显然容易的，方案数为 \(s_k=\binom{n}{k}(2^{2^{n-k}}-1)\)。直接向后二项式反演即可。

注意：指数中的模数为原模数减 \(1\)（费马小定理），即 \(10^9+6\)。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
#define int long long
using namespace std;
const int N = 1e6 + 10;
const int MOD = 1e9 + 7;

int n, k, ans;
int inv[N], fact[N], ifact[N];
int pw2[N];

#define add(a, b) a = (a + b) % MOD;
#define sub(a, b) a = (a + MOD - b) % MOD;

inline int c(int a, int b) {
    return fact[a] * ifact[a - b] % MOD * ifact[b] % MOD;
}

inline int qpow(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int a[N];

signed main() {

    cin >> n >> k;

    inv[1] = 1;
    fact[0] = ifact[0] = 1;
    pw2[0] = 1;
    for(int i = 2; i <= n; i++) inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    for(int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
    for(int i = 1; i <= n; i++) ifact[i] = ifact[i - 1] * inv[i] % MOD;
    for(int i = 1; i <= n; i++) pw2[i] = pw2[i - 1] * 2 % (MOD - 1);

    for(int i = k; i <= n; i++) a[i] = c(n, i) * (qpow(2, pw2[n - i]) + MOD - 1) % MOD;

    for(int i = k; i <= n; i += 2) add(ans, c(i, k) * a[i] % MOD);
    for(int i = k + 1; i <= n; i += 2) sub(ans, c(i, k) * a[i] % MOD);

    cout << ans << '\n';

    return 0;
}

P5505 [JSOI2011] 分特产

题意

有 \(m\) 种物品，第 \(i\) 种物品有 \(a_i\) 个，同种物品之间完全相同。你需要把 \(m\) 种物品分给 \(n\) 个人，每个人都必须至少分到一个物品，问分配方案数。、

\(n,m,a_i\le 1000\)

由于同种物品之间完全相同，因此我们必须分开单独考虑每种物品，用插板法计算方案数。总方案数应是 \(\prod_{i=1}^{m}{\binom{a_i+n}{n}}\)。然而在分配单种物品的过程中，可以分给一个人 \(0\) 件物品，因此最终有人为空的情况也会被统计到。

考虑二项式反演，钦定 \(k\) 个人为空的方案数 \(s_k=\prod_{i=1}^{m}{\binom{a_i+n-k}{n-k}}\) 是容易计算的。直接向后二项式反演计算恰好 \(0\) 人时的方案数即可。

时间复杂度 \(O(nm)\)。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#define int long long
using namespace std;
const int N = 2010;
const int MOD = 1e9 + 7;

int n, m, ans;
int a[N];
int inv[N], fact[N], ifact[N];
int s[N];

int c(int x, int y) {
    return fact[x] * ifact[x - y] % MOD * ifact[y] % MOD;
}

signed main() {

    inv[1] = fact[0] = ifact[0] = 1;
    for(int i = 2; i < N; i++) inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    for(int i = 1; i < N; i++) fact[i] = fact[i - 1] * i % MOD;
    for(int i = 1; i < N; i++) ifact[i] = ifact[i - 1] * inv[i] % MOD;

    cin >> n >> m;
    for(int i = 1; i <= m; i++) cin >> a[i];

    for(int k = 0; k < n; k++) {
        s[k] = c(n, k);
        for(int i = 1; i <= m; i++) s[k] = s[k] * c(a[i] + n - k - 1, n - k - 1) % MOD;
    }
    for(int i = 0; i <= n; i += 2) ans = (ans + s[i]) % MOD;
    for(int i = 1; i <= n; i += 2) ans = (ans + MOD - s[i]) % MOD;

    cout << ans << '\n';

    return 0;
}

P4859 已经没有什么好害怕的了

题意

给定两个长为 \(n\) 的序列 \(a,b\)（保证不出现重复的数字），你需要将 \(b\) 重新排列，使得 \(a_i> b_i\) 的位置 \(i\) 的数量比 \(a_i<b_i\) 的位置数量恰好多 \(k\) 个。问重排（匹配）方案数，答案对 \(10^9+9\) 取模。

\(n\le 2000, 0\le k\le n\)

先 \(k\gets \frac 12(n+k)\)，表示 \(a_i>b_i\) 的位置恰好有 \(k\) 个。

我们只需要求出钦定 \(x\) 个位置满足 \(a_i>b_i\) 的方案数 \(s_x\)，然后向后二项式反演即可。

注意到 \(s_x\) 不易用组合数直接计算。我们先将 \(a,b\) 分别排好序，考虑 dp，设 \(f_{i,j}\) 表示 \(a\) 的前 \(i\) 项种钦定了 \(j\) 项匹配了一个 \(b_i<a_i\)，对应的方案数。由于序列已经排好序，每个 \(a_i\) 能匹配的位置是一个前缀 \(p\)，使用 lower_bound 求出即可。容易写出转移：

\[ f_{i,j}=f_{i-1,j}+(p-j+1)f_{i-1,j-1} \]

最后 \((n-x)!f_{n,x}\) 就是 \(s_x\)。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N = 2010;
const int MOD = 1e9 + 9;

#define add(a, b) a = (a + b) % MOD

int fact[N], ifact[N], inv[N];

int c(int a, int b) {
    return fact[a] * ifact[a - b] % MOD * ifact[b] % MOD;
}

int n, k, ans;
int a[N], b[N];
int f[N];

signed main() {

    inv[1] = fact[0] = ifact[0] = 1;
    for(int i = 2; i < N; i++) inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    for(int i = 1; i < N; i++) fact[i] = fact[i - 1] * i % MOD;
    for(int i = 1; i < N; i++) ifact[i] = ifact[i - 1] * inv[i] % MOD;

    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> b[i];

    if((n & 1) != (k & 1)) { cout << "0\n"; return 0; }
    k = (n + k) >> 1;

    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + n);

    for(int i = 1; i <= n; i++) {
        int p = lower_bound(b + 1, b + 1 + n, a[i]) - b - 1;
        f[0] = 1;
        for(int j = min(i, p); j >= 1; j--) {
            add(f[j], f[j - 1] * (p - j + 1) % MOD);
        }
    }

    for(int i = 0; i <= n; i++) f[i] = f[i] * fact[n - i] % MOD;

    for(int i = k; i <= n; i += 2) add(ans, c(i, k) * f[i] % MOD);
    for(int i = k + 1; i <= n; i += 2) add(ans, MOD - c(i, k) * f[i] % MOD);

    cout << ans << '\n';

    return 0;
}