P3214 [HNOI2011]卡农

题目

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

*/