容斥

本文将简单介绍几种常见的容斥模型，以及容斥方法。容斥和反演是离不开的，因为实际上它们就是同一种东西的两种表现形式，一种出现于小学课本，另一种出现于大学的教材。但是，容斥原理所运用的手段与技巧完全是基于反演理论的，因此，想熟练运用容斥原理，第一步就是完全搞清楚反演是什么。文章：从卷积到反演

经典容斥模型 1

对于多个集合，已知属于其中至少 $i$个集合的元素有 $x_i$个，求全集的大小。

对于这样的问题，也包括接下来讨论的更复杂的问题，我们的处理方法往往是写出函数化的表达，然后尝试用反演的办法求解我们需要的答案。令 $F[i]$表示属于至少 $i$个集合的元素个数，$G[i]$表示属于恰好 $i$个集合的元素个数，那么：
$$
F[i]=\sum_{j=i}^{N}G[j]
$$
显然：
$$
G[i]=F[i]-F[i+1]
$$

经典容斥模型 2

由于我找不到一个合适的描述，故这个模型直接用例题来阐述。

求 1~N 这 N 个数的错排个数

对于这类限制较强的问题，我们一般转化为限制较弱的问题，最终用容斥原理求解。

每个数都不能待在自己的位置上，这是一个很强的限制。如果我们限制若干个数呆在自己位置上，其余的数随便排列，则这是一个很弱的限制。

设 $F[i]$表示，固定了 $i$个数在自己位置上，其余的数随便排列的方案数，$G[i]$表示恰好只有 $i$个数在自己的位置上的方案数。我们需要通过 $F$求出 $G[0]$。

$$
F[i] = \sum_{j=i}^{N}\binom{j}{i}G[j]
$$

为什么有个组合数？因为 $j$个元素大组成的集合的小为 $i$的子集有 $\binom{j}{i}$个。指定 $j$个元素中的任意 $i$个，其余的乱排，都会产生 $j$个元素在自己位置上的情况。如：$N=3$，固定 ${1,2},{1,3},{2,3}$时，排列 ${1,2,3}$各被计算了一次。

观察发现，由 $F$求 $G$的方法很简单，可以使用二项式反演，当然以下方法更简单，可以 $O(n^2)$求解：

$$
G[i]=F[i]-\sum_{j=i+1}^{N}G[j]\binom{j}{i}
$$

特殊的，对于 $G[0]$，有：

$$
G[0]=\sum_{i=0}^{N}(-1)^iF[i]
$$

为什么呢？组合数有这样一个性质：

$$
\sum_{i=0}^{N}(-1)^i\binom{N}{i}=[i=0]
$$

将上面式子的 $F$用 $G$表示后，展开的形式将是

$$
G[0]=\sum_{i=0}^{N}(-1)^{i}\binom{N}{i}G[i]=\sum_{i=0}^{N}G[i]\cdot[i=0]
$$

子集容斥模型 1

设一个集合的权值为其所有元素的权值之和，现在给出全集 $U$的所有子集的子集的权值和，如何求出全集的每个子集的权值？即：
$$
F[S] = \sum_{T\subset S}G[T]
$$
给出 $F[S]$，求 $G[S]$的值，或给出 $G[S]$，求 $F[S]$。

对于这个问题，无论是从 $F$到 $G$，还是从 $G$到 $F$，要实现高效的计算都是有点困难的。但是，借助 $FMT$，我们可以将复杂度优化为 $O(2^{|U|}|U|)$。

子集容斥模型 2

给出全集 $U$的所有子集的元素的最大值，求全集的每个子集内所有元素的最小值。

该问题的解法又被称作 min-max 容斥，基于如下公式：
$$
\begin{aligned}
MAX[S] & = \sum_{T\in S}(-1)^{|T|+1}MIN[T] \\
MIN[S] & = \sum_{T\in S}(-1)^{|T|+1}MAX[T]
\end{aligned}
$$

正确性？拿由 $MIN$求 $MAX$的公式来举例：
– 已知 $S,\forall T\subset S,MIN[T]$，求 $MAX[S]$
– 对于元素 $x$，设有 $c$个元素比它大，则 $S$只有 $2^c$个子集以 $x$为最小值。
– 这 $2^c$个子集在公式中的系数为交替的 $\pm1$，若 $c\neq 0$则 $\pm x$全部低消。若 $c=0$，则系数只有一个 $+1$。

min-max 容斥推广到期望的计算中依旧成立。即：

$$
\begin{aligned}
MAX[E(x)|x\in S] & = \sum_{T\in S}(-1)^{|T|+1}MIN[E(x)|x\in T] \\
MIN[E(x)|x\in S] & = \sum_{T\in S}(-1)^{|T|+1}MAX[E(x)|x\in T]
\end{aligned}
$$

正确性？这根本不需要证明。上下两个式子没有任何区别，除了应用范围不同之外。

题目

1. AGC005D ~K Permutation

题意：求前 $N$个正整数的排列中，有多少个满足 $\forall i, |a_i-i|\neq K$。数据范围：$K< N\leq 2000$

分析：我们可以直接套用经典模型 2 里的方法。设 $F[i]$为强制 $i$个位置 $|a_i-i|=K$的排列个数，$G[i]$为恰好有 $i$个位置 $|a_i-i|=K$的排列个数，有：
$$
F[i]=\sum_{j=i}^{N}\binom{j}{i}G[j]
$$
根据经典模型 2，我们可以 $O(n)$容斥出 $G[0]$。

现在最大的问题成了，如何求出 $F[i]$。

注意到，对于每个 $i$，恰有 1 或 2 个 $a_i$满足 $a_i-i$。如果选择一个位置，可能会有其它 1 或 2 个位置不能选。这样，我们将相互限制的位置之间连边，将会得到一张二分图，并且，这张二分图是由若干条不相交的链组成的。因此，如果用 $H[i][j]$表示前 $i$条链中选了 $j$个点的方案数，那么：
$$
\begin{aligned}
H[0][0] & = 1;\\
H[i][j] & = H[i-1][j-k]\binom{len_i-k+1}{k}
\end{aligned}
$$
其中 $len_i$为第 $i$条链的长度，组合数的意义是在链上选 $k$个不相邻的点的方案数。Dp 求 $H$数组的时间复杂度看上去是 $O(NK^2)$的，实际上是 $O(N^2)$的。具体原因大家自行分析，这里不再赘述。

因此，我们求出了 $H$数组后，可以快速求出 $F$：

$$
F[i] = H[N][i](N-i)!
$$

上面的方法的时间复杂度为 $O(N^2)$。另外，由于链的最大长度和最短长度相差不超过 $3$，如果我们用生成函数 $A_i$表示在一条长度为 $i$的链上选点的方案数的话，$H[N]$将以用不超过三个生成函数的若干次幂的积表示，这样，借助多项式求幂，时间复杂度可以优化成 $O(N\log N)$。

2. BZOJ4036 按位或

题意：有 $[0,2^N]$之间的数，每一轮数 $i$都有 $p_i$的概率出现，求期望多少轮后出现过的数的按位或为 $2^N-1$。数据范围 $N\leq 20$

分析：这是两种子集容斥模型的结合。根据题意，我们要求每一位第一次出现时间的最大值，根据子集容斥模型 2，我们可以枚举全集的所有子集，求该子集对应位第一次出现时间的最小值。而求第一次的最小值是非常容易的。

假设有 $q$的概率出现的数并不包含 $S$的任意一位，则期望 $\frac{1}{1-q}$次之后，$S$头一次与出现的数有交集。为什么呢？设 $e$为 $S$第一次与出现的数有交集的期望时间，则有 $1-q$的概率第一个数与 $S$有交集，有 $q$的概率你一无所有，从头来过，因此 $e=(1-q)+q(e+1)$。解得 $e=\frac{1}{1-q}$

那么有多大的概率出现的数与 $S$没有交集呢？即
$$
q_S=\sum_{T\cap S = \emptyset}p_{T}
$$
根据子集容斥模型 1，借助 FMT，$q_S$的求解可以在 $O(N2^N)$时间内完成。

---

还有一些有意思的有关容斥的题目，这里不再放题解，但是给出题目列表：

• AGC005D

• BZOJ3294 放旗子

• 51nod1518

• HDU4336

• BZOJ4036 按位或

• BZOJ4455 小星星

• BZOJ4767 两双手

• BZOJ4361 isn

• BZOJ2560 串珠子

• BZOJ4005 骗我呢

• CF342D

• TC SRM498Div1 foxjump 11223

以及上面两道题的代码：

• 1. AGC005D ~K Permutation

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define MOD 924844033
#define MX 2003

using namespace std;

typedef long long ll;

int N, K;
int LEN[MX], NUM;
ll FAC[MX], FACI[MX];
ll F[MX][MX], G[MX];

ll qpow(ll x, ll t)
{
    ll ans = 1;
    while(t)
    {
        if(t & 1) ans = ans*x%MOD;
        x = x*x%MOD;
        t >>= 1;
    }
    return ans;
}

ll inv(ll x)
{
    return qpow(x, MOD-2);
}

ll C(int n, int m)
{
    if(n<0 || m<0 || n<m) return 0;
    else return FAC[n] * FACI[m]%MOD * FACI[n-m]%MOD;
}

void init()
{
    FAC[0] = 1;
    for(int i=1; i<=N; i++) FAC[i] = FAC[i-1] * i % MOD;
    FACI[N] = inv(FAC[N]);
    for(int i=N-1; i>=0; i--) FACI[i] = FACI[i+1] * (i+1) % MOD;
}

int main()
{
    scanf("%d%d", &N, &K);
    init();
    for(int i=1; i<=K&&i<=N-K; i++)
        LEN[++NUM] = (N-K-i)/K+1,
        LEN[++NUM] = (N-K-i)/K+1;
    F[0][0] = 1;
    for(int i=1; i<=NUM; i++)
        for(int j=0; j<=N; j++)
            for(int k=0; k<=j&&k<=((LEN[i]+1)>>1); k++)
                F[i][j] = (F[i][j] + F[i-1][j-k] * C(LEN[i]-k+1, k))%MOD;
    for(int i=N; i>=0; i--)
    {
        G[i] = F[NUM][i] * FAC[N-i] % MOD;
        G[i] = (G[i] - G[i+1] + MOD) % MOD;
    }
    printf("%lld\n", G[0]);
    return 0;
}

• BZOJ4036 按位或

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

double pro[1048576];
int n, len;

void fwt(double* x, int l)
{
    for(int i=1; i<l; i<<=1)
        for(int j=0; j<l; j+=(i<<1))
            for(int k=0; k<i; k++)
                x[j+k+i] += x[j+k];
}

void fuck()
{
    static double bit[32];
    for(int i=0; i<len; i++)
        for(int j=0; j<n; j++)
            if((i>>j) & 1)
                bit[j] += pro[i];
    for(int i=0; i<n; i++)
        if(bit[i] < 1e-10)
        {
            printf("INF\n");
            exit(0);
        }
}

int main()
{
    scanf("%d", &n);
    len = 1<<n;
    for(int i=0; i<len; i++) scanf("%lf", &pro[i]);
    fuck();
    fwt(pro, len);
    double ans = 0;
    for(int i=1; i<len; i++)
        if(__builtin_popcount(i) & 1) ans += 1/(1-pro[(~i)&(len-1)]);
        else ans -= 1/(1-pro[(~i)&(len-1)]);
    printf("%.10lf\n", ans);
    return 0;
}