题目

P3214 [HNOI2011]卡农

在被一题容斥\(dp\)完虐之后,打算做一做集合容斥这类的题了

第一次深感HNOI的毒瘤(题做得太少了!!)

做法

求\([1,n]\)组成的集合中选\(m\)个不同集合且每个元素出现偶数的组合方案

无序(打乱顺序仍记为一种)通常我们对于有序的做法更简单,怎么转换呢

C组合数的公式是怎么得来的?别说你是背来的\(emmm\)(那也没有做这题的必要了)

有序\(m!\)就得到了无序的

我们考虑\(dp\),数组\(dp_i\)表示选i个不同集合的排列方案

异或和为\(0\),则,确定前\(i-1\)个集合则第\(i\)个集合自然也出来了,方案数为\(A_{2^n-1}^{i-1}\)

如果前面\(i-1\)个集合异或和已为\(0\),那第\(i\)个集合为空集,不符题意,这部分的方案数就是\(dp_{i-1}\)

保证所选集合不重复,若\(i\)与前\(i-1\)任意重复,去掉这个重复的集合,为\(dp_{i-2}\),可能的位置有\((i-1)\)个,重复集合个数有\((2^n-1-(i-2))\)

\(dp_i=A_{2^n-1}^{i-1}-dp_{i-1}-dp_{i-2}*(i-1)*(2^n-i+1)\)

最后再乘下逆元就好了

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL p=100000007;
const int maxn=1e6+9;
inline LL Pow(LL base,LL b){
LL ret(1);
while(b){
if(b&1)
ret=ret*base%p;
base=base*base%p,
b>>=1;
}
return ret;
}
LL n,m,a,Up,A,ans;
LL dp[maxn];
int main(){
scanf("%lld%lld",&n,&m);
dp[1]=dp[2]=0,
Up=(Pow(2ll,n)-1ll+p)%p,
A=Up;
for(LL i=3;i<=m;++i)
A=A*(Up-i+2)%p,
dp[i]=((A-dp[i-1]+p)%p-dp[i-2]*(i-1)%p*((Up-(i-2)+p)%p)%p +p)%p;
a=1;
for(LL i=2;i<=m;++i)
a=a*i%p;
ans=dp[m]*Pow(a,p-2)%p;
printf("%lld\n",ans);
return 0;
}/*
100 1000
*/
05-04 04:51