容斥

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

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

发表评论

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

你是机器人吗? =。= *