解题思路:
容斥定理,考虑选出若干集合使得交集至少为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;
}
0.0分
7 人评分