题解 卡农

题目传送门

题目大意

给出(n,m)，表示有(n)个元素，求出有多少种方法使得选出(m)个子集，满足:

1. 子集两两不完全相同。

2. 不能有子集为空集。

3. 每个元素被选中的次数只能为偶数次。

思路

我果然是个sb。。。

不难看出如果选中了(i-1)个子集，那么就一定确定了第(i)个子集，因为前面(i-1)个子集里面出现了奇数次的元素必须出现，否则必须不能出现。那么，我们设(f[i])表示选出(i)个子集并满足上面三个条件的方案数。那么总方案数就是(A_{2^n-1}^{i-1})，考虑减去不合法方案数。不满足第二种的方案数就是(f[i-1])，因为如果前(i-1)个子集都满足了，那第(i)个子集就不能选了。再考虑不满足第(1)中情况的方案数，假设子集(i,j)重复，那么去掉(i,j)也是合法的，就有(f[i-2])种，而(j)有(i-1)种方案，(i)有(2^n-1-(i-2)=2^n+1-i)种方案。

于是，我们得出转移式:

[f[i]=A_{2^n-1}^{i-1}-f[i-1]-(i-1)(2^n+1-i)f[i-2] ]

但是这并不是最后的答案，可以看出这样(dp)最后的子集是有顺序的，所以还需要除以(m!)。

( exttt{Code})

#include <bits/stdc++.h>
using namespace std;

#define Int register int
#define mod 100000007
#define MAXN 1000005

int mul (int a,int b){return 1ll * a * b % mod;}
int dec (int a,int b){return a >= b ? a - b : a + mod - b;}
int add (int a,int b){return a + b >= mod ? a + b - mod : a + b;}
int qkpow (int a,int b){
	int res = 1;for (;b;b >>= 1,a = 1ll * a * a % mod) if (b & 1) res = 1ll * res * a % mod;
	return res;
} 

int n,m,up,A[MAXN],dp[MAXN],fac[MAXN],ifac[MAXN];

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

signed main(){
	read (n,m),A[0] = dp[0] = fac[0] = 1,up = qkpow (2,n);
	for (Int i = 1;i <= m;++ i) fac[i] = mul (fac[i - 1],i);
	ifac[m] = qkpow (fac[m],mod - 2);for (Int i = m;i;-- i) ifac[i - 1] = mul (ifac[i],i);
	for (Int i = 1;i <= m;++ i) A[i] = mul (A[i - 1],up - i);
	for (Int i = 1;i <= m;++ i) dp[i] = dec (A[i - 1],add (dp[i - 1],mul (dp[i - 2],mul (i - 1,up + 1 - i))));
	write (mul (dp[m],ifac[m])),putchar ('
');
	return 0;
}