跳转至

容斥和反演

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

子集反演

设全集 \(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\))二项式反演即可。

代码
#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\)

代码
#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)\)

代码
#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\)

代码
#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;
}