容斥

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

经典容斥模型 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;
}
分类: 文章

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注