题解 P3214 【[HNOI2011]卡农】

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$ 。

这种方法真的很难想到。

#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;
}