蓝桥杯算法提高VIP-子集选取 （C++代码）

解题思路:

容斥定理，考虑选出若干集合使得交集至少为k的方案数，有f(i)=Cin×(22n−i−1)，可以理解为已经选定了i个，剩下2n−i

个集合，每个可以选或不选，但是不能一个也不选。但是这样做肯定会有重复的，我们思考容斥系数是什么。

当我们计算交集至少为k的时候，每个交集为j的方案都会被计算Ckj

次，所以
f(k)的系数是1
f(k+1)的系数是−Ckk+1
f(k+2)的系数−Ckk+2+Ckk+1Ck+1k+2=Ckk+2（小tips:CMNCSM=CSNCN−MN−S

）

以此类推，f(i)的系数就是(−1)i−kCki

。

所以答案为∑i=kn(−1)i−kCkiCin(22n−i−1)

求组合数需要线性筛逆元，方法：i−1≡−⌊pi⌋×(p%i)−1(modp)

求(22i−1)

可以采用从n到k枚举i的方法，初值tmp=1，然后tmp=tmp*(tmp+2)。

注意事项:

参考代码:

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

typedef long long ll;

const ll mod=1000000007;

ll n,k,ans;

ll ine[1000010],jcc[1000010],jc[1000010];

ll c(ll x,ll y)

{

    return jc[x]*jcc[y]%mod*jcc[x-y]%mod;

}

int main()

{

    scanf("%lld%lld",&n,&k);

    ll i,j,flag,tmp;

    ine[1]=jc[1]=jcc[1]=jc[0]=jcc[0]=1;

    for(i=2;i<=n;i++)

    {

        ine[i]=(mod-(mod/i)*ine[mod%i])%mod;

        jcc[i]=jcc[i-1]*ine[i]%mod;

        jc[i]=jc[i-1]*i%mod;

    }

    for(i=n,flag=((n-k)&1)?-1:1,tmp=1;i>=k;i--)

    {

        ans=(ans+mod+flag*c(i,k)*c(n,i)%mod*tmp%mod)%mod;

        flag=-flag,tmp=tmp*(tmp+2)%mod;

    }

    printf("%lld",ans);

    return 0;

}