当前位置：首页 > news >正文

容斥原理

news 来源：原创 2024/4/29 15:59:12

容斥原理：其实就是不断的加减来得到最终结果的过程。

容斥原理例题1：Devu和鲜花
题意：有n(n<=20)个花瓶，每个花瓶里有Ai枝花，现要取M枝花组成一束，有多少种方案。

分析：这是容斥原理的经典例题。

假设我们在第i个花瓶里取 $a_{i}$ 枝花，我们可以得到式子：
$x_{1}+x_{2}+…+x_{n}=M$
我们这里用一个技巧，假设 $y_{i}$ = $x_{i} +1$
$y_{1}+y_{2}+…+y_{n}=M+N$
这时，我们原来的问题就变成了这个题的解的个数。
而且，此时 $y_{i}>=1$ ，然后我们就可以用隔板法。
（注：这里隔板隔得是每个块的数量，因为每次隔板不能从最两端放（操作起来比较方便），所以我们必须将这个数换成>=1的才行）
此时，我们接着分析：
现在我们假设每个瓶里面的花都是： $\infty$
这时我们发现种类数是： $C_{M+N-1}^{N-1}$
然后我们去思考如何除去不符合题意的部分：

这里就是用到了我们的容斥了，首先确定一下当前的答案： $C_{M+N-1}^{N-1}$ -( $S_{1}$ $\cup$ $S_{2}$ $\cup$ $\dots$ $\cup$ $S_{n}$ )
这里的 $S_{i}$ 表示的是第i个花瓶取>=Ai+1的情况。
这里的容斥就体现的很明显了：我们先算有1个不符合情况的，然后再算两个，这样的话就是加上奇数的，减去偶数的，就可以得到答案。
具体的计算和算整体的类似，我们以1个不满足的时候为例：
$\Sigma_{i=1}^{i=n}$ $C_{N+M-1-(Ai+1)}^ {N-1}$ ，这里可能会有疑问为什么这里是Ai+1而不是Ai+2，我们不是将xi转化为yi了？就是因为这个是隔板法，每次取的是>=1我们每次都放N-1个板，这样就能保证每次都从每个花瓶里取1个。一定保证之前取完的是不合法的。

下面是AC代码：

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

using namespace std;

typedef long long LL;

const int N = 20, mod = 1e9 + 7;

LL A[N];
int down = 1;
//快速幂求逆元
int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}
//求组合数
int C(LL a, LL b)
{
    if (a < b) return 0;
    int up = 1;
    for (LL i = a; i > a - b; i -- ) up = i % mod * up % mod;
    return (LL)up * down % mod;//除以某个数等于乘以他的逆元
}

int main()
{
    LL n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> A[i];

    for (int j = 1; j <= n - 1; j ++ ) down = (LL)j * down % mod;//求down
    down = qmi(down, mod - 2, mod);//求down的逆元

    int res = 0;
    for (int i = 0; i < 1 << n; i ++ )
    {
        LL a = m + n - 1, b = n - 1;
        int sign = 1;
        for (int j = 0; j < n; j ++ )
            if (i >> j & 1)
            {
                sign *= -1;//每次转换加减，偶数个就加上，因为这里是从0开始，所以我们不用对res赋初值，整体就是偶数加上，奇数减去（分析我们推导出的式子）。
                a -= A[j] + 1;
            }
        res = (res + C(a, b) * sign) % mod;
    }

    cout << (res + mod) % mod << endl;

    return 0;
}

例题2：Character Encoding
题意：有m个格子，要求填数，每个数的范围是[0,n-1]，要求最终的数是k。

分析：这是容斥原理的经典例题。不过这个题的话和上面的题还是有所不同的，我们对比发现这个数据量是很大的不可能用上面那个枚举的方法，但是这个题的优秀之处在于他的每个空格的能放的最大数是相同的，我们直接用 $C_{m}^{i}$ 来表示我们选几个合格即可，整体思路和上面的相同，这里不再赘述，下面是AC代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
#define int long long
const int mod=998244353;
const int N=1e6+10;
int n,m,k;
int qpow(int a,int b)
{
    int t=1;
    while(b)
    {
        if(b&1) t=t*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return t;
}
int fc[N],gc[N];
int mul(int a,int b)
{
    return a*b%mod;
}
inline void init(){
    fc[0]=1;
    for(int i=1;i<=500001;i++) fc[i]=mul(fc[i-1],i);
    gc[500001]=qpow(fc[500001],mod-2);
    for(int i=500001;i>=1;i--) gc[i-1]=mul(gc[i],i);
}
inline int C(int i,int j){
	if(j>i)return 0;
	return mul(mul(fc[i],gc[j]),gc[i-j]);
}
int cal()
{
    int ans=0;
    for(int i=1;i*n<=k;i++)
    {
        if(i&1) ans=(ans+C(m,i)*C(k+m-1-i*n,m-1))%mod;
        else ans=(ans-C(m,i)*C(k+m-1-i*n,m-1))%mod;
    }
    return (C(k+m-1,m-1)-ans+mod)%mod;
}
signed main()
{
    init();
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m>>k;
        cout<<cal()<<endl;
    }
    return 0;
}

例题3：810975
题意：一共n场比赛，赢了m场，连续赢得场数为k，问有多少中可能。
题解：可以转化为和第2道题一样的思路。

但是我们先朴素的分析一下题目，一共n场比赛赢了m场，连续赢得场数为k，如果直接处理的话（可以自己想一想）这个连续的k场真的很难处理，所以这个对于1很难处理我们就去处理0。发现这里有n-m个0，这时我们就在这n-m个0中插入1，由与0的两边可以插，所以一共相当于有n-m+1个空档。

所以问题就转化成了n-m+1个格字，填数，每个格子填的最大的数是k，之和是m。问有几种方案，这时这个题目就和上面是一样的了。

当然，想到这里之后还是不够的，这样算了之后是最大时<=k的时候，而不是恰好等于k的时候，而且k是必须含有的。

这里我们用cal(k)-cal(k-1)即可。

简单证明一下：cal(k-1)是每个都<=k-1的情况，cal(k)是每个都<=k-1的时候。这样的话，其实每个都<=k-1的时候cal(k-1)是全部都包含的。只有==k时候是不包含的，所以这里可以表示。

下面是AC代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
#define int long long
const int mod=998244353;
const int N=1e6+10;
int n,m,k;
int qpow(int a,int b)
{
    int t=1;
    while(b)
    {
        if(b&1) t=t*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return t;
}
int fc[N],gc[N];
int mul(int a,int b)
{
    return a*b%mod;
}
inline void init(){
    fc[0]=1;
    for(int i=1;i<=500001;i++) fc[i]=mul(fc[i-1],i);
    gc[500001]=qpow(fc[500001],mod-2);
    for(int i=500001;i>=1;i--) gc[i-1]=mul(gc[i],i);
}
inline int C(int i,int j){
	if(j>i)return 0;
	return mul(mul(fc[i],gc[j]),gc[i-j]);
}
int cal(int k)
{
    int ans=0;
    for(int i=1;i*(k+1)<=m;i++)
    {
        if(i&1) ans=(ans+C(n-m+1,i)*C(n-i*(k+1),n-m))%mod;
        else ans=(ans-C(n-m+1,i)*C(n-i*(k+1),n-m))%mod;
    }//这个可以从开始然后加减号反转，这样就可以不用减去了。
    return (C(n,n-m)-ans+mod)%mod;
}
signed main()
{
    init();
    cin>>n>>m>>k;
    if(k==0)
    {
        cout<<(m==0)<<endl;
        return 0;
    }
    int ans=((cal(k)-cal(k-1))%mod+mod)%mod;
    cout<<ans<<endl;
    return 0;
}