题解 P3214 【[HNOI2011]卡农】
Salamander
2018-02-02 10:09:17
题目大意：
从集合$\{1,2,...,n\}$中无序地选出$m$个互不相同的非空子集，要求在这些选出的子集中，每个数出现次数为偶数。求方案数。
首先将无序化为有序，最后答案除以$m!$。$dp[i]$表示选出了$i$个子集，并且满足所有限制的方案数。
直接考虑$dp[i-1]$转移到$dp[i]$非常困难，所以考虑补集转换一下，用容斥的方式求$dp[i]$。
首先由于限制了每个数的出现次数为偶数，所以如果前$i-1$个子集确定了，第$i$个的选择是唯一的，第$i$个里面的数必须是前面出现奇数次的那些数。所以在没有限制$i$不和之前相同和非空的情况下，选出$i$个子集的方案数为$A_{2^n-1}^{i-1}$，即从所有非空子集中选出前$i-1$个的排列数。
然后我们减去第$i$个子集为空的情况，方案数为$dp[i-1]$，即前$i-1$个集合自己已经满足了每个数出现次数为偶数的情况。
我们还要减去第$i$个子集和之前某个子集相同的情况。如果我们把相同的两个集合删去，那么剩下的集合肯定合法，所以方案数为$dp[i-2]$。然后第$i$个子集有$2^n-1-(i-2)$种方案，同时和第$i$个子集相同的那个子集的不同位置有$i-1$种，所以第$i$个子集和之前某个子集相同的方案数为$dp[i-2]*(i-1)*(2^n-1-(i-2))$。
所以我们得到了dp的转移：
$dp[i]=A_{2^n-1}^{i-1}-dp[i-1]-(dp[i-2]*(i-1)*(2^n-1-(i-2)))$
初始化$dp[0]=1,dp[1]=0$。
这种方法真的很难想到。
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define For(i,_beg,_end) for(int i=(_beg),i##end=(_end);i<=i##end;++i)
#define Rep(i,_beg,_end) for(int i=(_beg),i##end=(_end);i>=i##end;--i)
template<typename T>T Max(const T &x,const T &y){return x<y?y:x;}
template<typename T>T Min(const T &x,const T &y){return x<y?x:y;}
template<typename T>int chkmax(T &x,const T &y){return x<y?(x=y,1):0;}
template<typename T>int chkmin(T &x,const T &y){return x>y?(x=y,1):0;}
template<typename T>void read(T &x){
T f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(x=0;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
x*=f;
}
typedef long long LL;
const int maxn=1000010,mod=100000007;
int n,m;
LL dp[maxn],inv,A[maxn],mx;
LL power(LL x,LL y){
LL res=1;
for(;y;y>>=1,x=x*x%mod) if(y&1) res=res*x%mod;
return res;
}
int main(){
read(n);read(m);
inv=A[0]=1;
For(i,2,m) inv=inv*i%mod;
inv=power(inv,mod-2);
mx=power(2,n)-1;
For(i,1,m) A[i]=A[i-1]*(mx-i+1)%mod;
dp[0]=1;
For(i,2,m){
dp[i]=A[i-1]-dp[i-1]+mod;
dp[i]-=dp[i-2]*(i-1)%mod*(mx-(i-2))%mod;
dp[i]=(dp[i]%mod+mod)%mod;
}
printf("%lld\n",dp[m]*inv%mod);
return 0;
}
```