容斥总结

很优美的计算方法。

引入

首先看个小学数学题

班主任在班会上问：“谁做完了语文作业？请举手”有37人举手，又问：“谁做完了数学作业？请举手”有42人举手，最后问：“谁语文、数学作业都做完了？请举手”有25人举手。求这个班语文、数学作业至少有一个做完的人数是多少个？

小学写啥作业。。这就是一道容斥原理的题。我们可以通过画图或者直接看出答案是$37+42-25$

定义

我们可以试着转换一下。这个问题可以转化为知道一个有限集合$U$，还知道两种条件$P_1,P_2$，定义两个集合$S_1,S_2$为$U$的子集，分别是满足$P_1,P_2$的元素，现在知道分别满足两种性质的元素个数$|S_1|,|S_2|$和同时满足两种条件的元素个数$|S_1 \cap S_2|$，求出至少满足一种的元素个数$|S_1 \cup S_2|$

那么公式就是

$$|S_1 \cup S_2|=|S_1|+|S_2|-|S_1 \cap S_2|$$

通过画图啥的可以推广出三种条件的公式

$$|S_1 \cup S_2 \cup S_3|=|S_1|+|S_2|+|S_3|-|S_1 \cap S_2|-|S_1 \cap S_3|-|S_2 \cap S_3|+|S_1 \cap S_2 \cap S_3|$$

这样我们可以得出容斥原理的一个通式

设$U$中有$n$种不同的条件$P_i$，满足每种条件的子集为$S_i$，则满足最少一个条件的元素个数为

\begin{aligned}
|S_1 \cup S_2 \cup \cdots \cup S_n| & = \sum_{i}|S_i| -\sum_{i< j}|S_i \cap S_j|+\sum_{i< j< k}|S_i \cap S_j \cap S_k|-\cdots \\
& \cdots +(-1)^{n-1}|S_1 \cap S_2 \cap \cdots \cap S_n|
\end{aligned}

下面就证明一下这个结论。

考虑某个元素$i$，它属于的$m$个集合为$T_1,T_2 \cdots T_m$。我们考虑式子右边它算了多少次。。

$$times=C_m^1-C_m^2+\cdots (-1)^{m-1}C_m^m$$

上图吧

就是计算了它在每个条件里的贡献。

$$times=-((\sum_{i=0}^m(-1)^iC_m^i)-C_m^0)$$

二项式定理化一下

$$times=-((1-1)^m-1)$$

这样也就是说，只要$m>0$就是计算了1次，所以只要它满足一个条件，它就只会计算一次，也就是至少满足一个条件。

这里我们是拿交集求出并集，那如何反向求呢？

那就用补集转换。。

公式

$$|S_1 \cap S_2 \cap \cdots \cap S_n|=|U|-|S_1 \cup S_2 \cup \cdots \cup S_n|$$

例题

下面就看点例题吧

uva11806

题意:给一个nxm的棋盘，往里面放k个棋子，且第一行，第一列，最后一行，最后一列至少有一个棋子。问方案数。

题解

总的集合是所有子都随便放的方案数，四个条件是满足分别第一行，第一列，最后一行，最后一列满足。

我们先补集转化一下，再套公式就好了。

#include <cstdio>
#define mod 1000007
using namespace std;
int c[10001][510],T,n,m,k;
void init()
{
    c[0][0]=1;
    for (int i=1;i<=500;i++)
    {
        c[i][0]=1;
        for (int j=1;j<=i;j++)
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
    }
}
int C(int n,int m)
{
    if (n<m)
        return 0;
    return c[n][m];
}
main()
{
    init();
    scanf("%d",&T);
    for (int cs=1;cs<=T;cs++)
    {
        scanf("%d%d%d",&n,&m,&k);
        if (k==1)
        {
            printf("Case %d: 0\n",cs);
            continue;
        }
        int ans=0;
        for (int s=0;s<=(1<<4)-1;s++)
        {
            int x=n,y=m,cnt=0;
            for (int i=0;i<2;i++)
                if (s&(1<<i))
                    x--,cnt++;
            for (int i=2;i<4;i++)
                if (s&(1<<i))
                    y--,cnt++;
            if (cnt&1)
                ans=(ans-C(x*y,k))%mod;//,printf("-%d %d\n",x,y);
            else
                ans=(ans+C(x*y,k))%mod;//,printf("+%d %d\n",x,y);
        }
//      int ans=(((((((((C(n*m,k)-C((n-1)*m,k)*2)%mod-C((m-1)*n,k)*2)%mod+C((n-2)*m,k))%mod+C((m-2)*n,k))%mod+C((n-1)*(m-1),k)*4)%mod-C((n-2)*(m-1),k)*2)%mod-C((m-2)*(n-1),k)*2)%mod+C((n-2)*(m-2),k))%mod)%mod;
        printf("Case %d: %d\n",cs,(ans%mod+mod)%mod);
    }

}

hdu4135

题意：求出a-b中间和n互质的数字个数。$a< b< 10^{15} n< 10^9$

题解

补集转化成a-b之间和它不互质的数字个数。就把n分解质因数，作为条件。计算小于b和小于a-1的，减一下。

#include<cstdio>
#include<algorithm>
#include <cstdlib>
#include<vector>
#include <map>
using namespace std;

const int MAXN = 100005;
long long x[MAXN];
map <long long,int> ma;

long long multi(long long a, long long b, long long p) {
    long long ans = 0;
    while(b) {
        if(b&1LL) ans = (ans+a)%p;
        a = (a+a)%p;
        b >>= 1;
    }
    return ans;
}

long long qpow(long long a, long long b, long long p) {
    long long ans = 1;
    while(b) {
        if(b&1LL) ans = multi(ans, a, p);
        a = multi(a, a, p);
        b >>= 1;
    }
    return ans;
}

bool Miller_Rabin(long long n) {
    if(n == 2) return true;
    int s = 30, i, t = 0;
    long long u = n-1;
    while(!(u & 1)) {
        t++;
        u >>= 1;
    }
    while(s--) {
        long long a = rand()%(n-2)+2;
        x[0] = qpow(a, u, n);
        for(i = 1; i <= t; i++) {
            x[i] = multi(x[i-1], x[i-1], n);
            if(x[i] == 1 && x[i-1] != 1 && x[i-1] != n-1) return false;
        }
        if(x[t] != 1) return false;
    }
    return true;
}

long long gcd(long long a, long long b) {
    return b ? gcd(b, a%b) : a;
}

long long Pollard_Rho(long long n, int c) {
    long long i = 1, k = 2, x = rand()%(n-1)+1, y = x;
    while(true) {
        i++;
        x = (multi(x, x, n) + c)%n;
        long long p = gcd((y-x+n)%n, n);
        if(p != 1 && p != n) return p;
        if(y == x) return n;
        if(i == k) {
            y = x;
            k <<= 1;
        }
    }
}

void find(long long n, int c) {
    if(n == 1) return;
    if(Miller_Rabin(n)) {
        ma[n]++;
        return;
    }
    long long p = n, k = c;
    while(p >= n) p = Pollard_Rho(p, c--);
    find(p, k);
    find(n/p, k);
}
long long n,k,a,b,rt[1010],tot;
long long ge(long long n)
{
    long long ans=0;
    for (int i=0;i<=(1<<tot)-1;i++)
    {
        int temp=1,cnt=0;
        for (int j=0;j<tot;j++)
            if (i&(1<<j))
                temp*=rt[j+1],cnt++;
//      if (temp==1) continue;
        if (cnt&1)
            ans=ans-n/temp;
        else
            ans=ans+n/temp;
    }
    return ans;
}
main()
{
    int T;
    scanf("%d",&T);
    for (int cs=1;cs<=T;cs++)
    {
        scanf("%lld%lld%lld",&a,&b,&n);
        ma.clear();tot=0;
        long long ans=0;
        find(n,1242);
        for(map<long long, int>::iterator c = ma.begin(); c != ma.end();)
        {
            long long x1=c->first,x2=c->second,temp=n,tans=0,te=0;
            c++;
            rt[++tot]=x1;
        }
        printf("Case #%d: %lld\n",cs,ge(b)-ge(a-1));
    }
}

luogu1450 [HAOI2008]硬币购物

题目描述

硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。

输入输出格式

输入格式：
第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s

输出格式：
每次的方法数

输入输出样例

输入样例#1：
1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900
输出样例#1：
4
27

说明

di,s<=100000

tot<=1000

题解

设$f[i]$为不考虑每种硬币的数量限制的情况下，得到面值i的方案数。

dp一下搞出来。$f[i]=\sum_{j=1..4}f[i-c[j]]$

然后就是容斥：得到面值S的超过限制的方案数 – 第1、2、3、4种硬币分别超过限制的方案数 + 第1,2种硬币同时超过限制的方案数 + …… + 第1,2,3,4种硬币全部同时超过限制的方案数。

当第1种硬币超过限制时，只要要用到$d[1]+1$枚硬币，剩余的硬币可以任意分配，所以方案数为 $f[all–(d[1]+1) \times c[1]]$

然后就是容斥了。

#include <cstdio>
#define int long long
using namespace std;
int c[5],d[5],T,x,f[100010];
void init()
{
    f[0]=1;
    for (int i=1;i<=4;i++)
        for (int j=c[i];j<=100000;j++)
            f[j]+=f[j-c[i]];
}
main()
{
    scanf("%d%d%d%d%d",&c[1],&c[2],&c[3],&c[4],&T);
    init();
    while(T--)
    {
        int ans=0;
        scanf("%d%d%d%d%d",&d[1],&d[2],&d[3],&d[4],&x);
        for (int i=0;i<=(1<<4)-1;i++)
        {
            int now=x,cnt=0;
            for (int j=0;j<4;j++)
                if (i&(1<<j))
                    now-=c[j+1]*(d[j+1]+1),cnt++;
            if (now<0)  continue;
            if (cnt&1)
                ans-=f[now];
            else
                ans+=f[now];
        }
        printf("%lld\n",ans);
    }
}

luogu2567 [SCOI2010]幸运数字

题目描述

在中国，很多人都把6和8视为是幸运数字！lxhgww也这样认为，于是他定义自己的“幸运号码”是十进制表示中只包含数字6和8的那些号码，比如68，666，888都是“幸运号码”！但是这种“幸运号码”总是太少了，比如在[1,100]的区间内就只有6个（6，8，66，68，86，88），于是他又定义了一种“近似幸运号码”。lxhgww规定，凡是“幸运号码”的倍数都是“近似幸运号码”，当然，任何的“幸运号码”也都是“近似幸运号码”，比如12，16，666都是“近似幸运号码”。

现在lxhgww想知道在一段闭区间[a, b]内，“近似幸运号码”的个数。

输入输出格式

输入格式：
输入数据是一行，包括2个数字a和b

输出格式：
输出数据是一行，包括1个数字，表示在闭区间[a, b]内“近似幸运号码”的个数

输入输出样例

输入样例#1：
1 10
输出样例#1：
2

说明

对于30%的数据，保证1<=a<=b<=1000000

对于100%的数据，保证1<=a<=b<=10000000000

题解

我们先打表找下范围内的数字，发现有2000+个。

把这些数之间存在倍数关系的都干掉，发现还有900+个。

裸的枚举效率$O(2^{900})$，非常不优越。

发现会有很多组合大于边界，一旦大于就不用继续枚举。写了个剪枝的爆搜过了。

#include <cstdio>
#include <algorithm>
using namespace std;
long long cnt,ans[5010],a,b,data[5010],tot,anss;
void dfs(long long now,long long n)
{
    if (now)
        ans[++cnt]=now;
    if (now*10+6<=n)
        dfs((long long)now*10+6,n);
    if (now*10+8<=n)
        dfs((long long)now*10+8,n);
}
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
bool comp(long long a,long long b)
{
    return a>b;
}
void work(long long now,long long cnt,long long lcm)
{
    if(now>tot)
        if(cnt)
            if(cnt&1)
                anss+=(long long)(b/lcm-(a-1)/lcm);
            else
                anss-=(long long)(b/lcm-(a-1)/lcm);
        else;
    else
    {
        work(now+1,cnt,lcm);
        long long gcdd=gcd(data[now],lcm);
        if(data[now]/gcdd<=b/lcm)
            work(now+1,cnt+1,lcm/gcdd*data[now]);
    }
}
main()
{
    scanf("%lld%lld",&a,&b);
    dfs(0,b);
    sort(ans+1,ans+1+cnt);
    for (int i=1;i<=cnt;i++)
    {
        data[++tot]=ans[i];
        for (int j=1;j<tot;j++)
            if (ans[i]%data[j]==0)
            {
                tot--;
                break;
            }
    }
    sort(data+1,data+1+tot,comp);
    work(1,0,1);
    printf("%lld\n",anss);
//  printf("%d",find(b)-find(a-1));
}

bzoj2393

Description

~Cirno发现了一种baka数，这种数呢~只含有2和⑨两种数字
现在Cirno想知道~一个区间中~ ~有多少个数能被baka数整除~
但是Cirno这么天才的妖精才不屑去数啦
只能依靠聪明的你咯。

Input

一行正整数L R
( 1 < L < R < 10^10)

Output

一个正整数，代表所求的答案

Sample Input

1 100

Sample Output

58

一模一样

#include <cstdio>
#include <algorithm>
using namespace std;
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long long a[5010],data[5010],cnt,tot,l,r,ans;
void finds(long long now)
{
    if (now) a[++cnt]=now;
    if (now*10+2<=r) finds(now*10+2);
    if (now*10+9<=r) finds(now*10+9);
}
void dfs(long long now,long long cnt,long long lcm)
{
    if (now>tot)
        if (cnt)
            if (cnt&1) ans+=(long long)(r/lcm)-((l-1)/lcm);
            else ans-=(long long)(r/lcm)-((l-1)/lcm);
        else;
    else
    {
        dfs(now+1,cnt,lcm);
        long long g=gcd(lcm,data[now]);
        if (data[now]/g<=r/lcm)
            dfs(now+1,cnt+1,lcm/g*data[now]);
    }
}
main()
{
    scanf("%d%d",&l,&r);
    finds(0);
    sort(a+1,a+1+cnt);
    for (long long i=1;i<=cnt;i++)
    {
        data[++tot]=a[i];
        for (long long j=1;j<tot;j++)
            if (a[i]%data[j]==0)
            {
                tot--;break;
            }
    }
    for (long long i=1;i<=tot/2;i++)swap(data[i],data[tot-i+1]);
    dfs(1,0,1);
    printf("%lld\n",ans);
}

这是几个月前写的，现在又加了几道题：

bzoj2669
bzoj4455
bzoj4710
bzoj4569

恰好k个的容斥

有时候做题会有恰好k个的限制，限制很强，通常弱化为先拿出k个，剩下的任意。这时候容斥的形式通常是

$$=\ \ge k个\ -\ \ge k+1个\ +\ \ge k+2个\ …$$

这时候我们在统计$\geq j$也就是$k \leq j \leq n$时，如果依靠了枚举哪j个或者类似的DP，可能会过多的统计，比如一个$k+i$个的方案在这时候会被考虑$k + i \choose k$次，所以需要乘上一个组合数系数$k + i \choose k$

有的问题是恰好没有之类的，这时候$i \choose 0$所以不用考虑这个东西；同理，恰好n个也不用考虑。

证明

我们考虑一个恰好$x:x \geq k$个的方案被统计的次数：

$$
\begin{align}
&= \sum_{i=k}^x (-1)^{i-k}\binom{i}{k} \binom{x}{i} \\
&= \binom{x}{k} \sum_{i=k}^x (-1)^{i-k} \binom{x-k}{x-i}\\
&= \binom{x}{k} \sum_{j=0}^{x-k} \binom{x-k}{j} \\
&= [x==k]
\end{align}
$$

例题

bzoj3622
bzoj2024
bzoj3198
bzoj2839

用莫比乌斯函数做反演系数

bzoj2440
cf547c
bzoj2986