考虑有序选择各子集，最后除以m!即可。设f[i]为选i个子集的合法方案数。
对f[i]考虑容斥，先只满足所有元素出现次数为偶数。确定前i-1个子集后第i个子集是确定的，那么方案数为A(2n-1,i-1)。
显然不能为空集，于是去掉前i-1个已经满足限制的方案，也即f[i-1]。
然后去掉第i个子集和之前重复的情况。显然如果有重复，将这两个去掉后仍然是合法的。那么方案数为f[i-2]*(i-1)*(2n-1-(i-2))。
#include#include #include #include #include #include using namespace std;int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}#define P 100000007#define N 1000010int n,m,f[N],inv[N],p,A[N];int main(){#ifndef ONLINE_JUDGE freopen("bzoj2339.in","r",stdin); freopen("bzoj2339.out","w",stdout); const char LL[]="%I64d\n";#else const char LL[]="%lld\n";#endif n=read(),m=read(); p=1;for (int i=1;i<=n;i++) p=(p<<1)%P;p--; inv[1]=1; for (int i=2;i<=m;i++) inv[i]=P-1ll*(P/i)*inv[P%i]%P; for (int i=2;i<=m;i++) inv[i]=1ll*inv[i]*inv[i-1]%P; A[0]=1;for (int i=1;i<=m;i++) A[i]=1ll*A[i-1]*(p-i+1+P)%P; f[0]=1;f[1]=0; for (int i=2;i<=m;i++) f[i]=((A[i-1]-f[i-1]+P)%P-1ll*f[i-2]*(i-1)%P*(p-i+2+P)%P+P)%P; cout<<1ll*f[m]*inv[m]%P; return 0;}