【洛谷】[HNOI2011] 卡农

题目链接：https://www.luogu.com.cn/problem/P3214

题目大义：

给定集合S={1,2,...,n}，选出m个子集，满足：
（1）所有选出的m个子集都不能为空。
（2）所有选出的m个子集中，不能存在两个完全一样的集合。
（3）所有选出的m个子集中，1到n每个元素出现的次数必须是偶数。

先不管重复，我们只需要在最后除以m!
记f[i]表示分成i段合法的方案数
对于限制3，其实在分好前i-1段时，最后一段就自动分好了，但是最后一段可能是空集或者跟前面重复，所以要用容斥。
对于前i-1段的方案数，应该为\(\Large A_{2^n-1}^{i-1}\)

除空集以外，共有\(2^n-1\)个子集，在其中选\(i-1\)个

如果最后一段是空集，则方案数就是f[i-1]
如果最后一段重复了，则在f[i-2]的基础上，在选出一个与前i-2个不重复的子集，有\(2^n-1-(i-2)=2^n-i+1\)，
还要注意，这个与最后一段重复的子集有\(i-1\)个位置可以放
故转移方程为\(f[i]=\Large A_{2^n-1}^{i-1} \normalsize - f[i-1] - f[i-2] \times (i-1) \times (2^n-i+1)\)
最后乘上m!的逆元即可

#include
using namespace std;
const int N = 1e6 + 5, P = 1e8 + 7;
int n, m, p, fac[N], f[N];
inline int qpow(int a, int b){
	int ret = 1;
	for (; b; a = 1ll * a * a % P, b >>= 1)
		if (b & 1) ret = 1ll * ret * a % P;
	return ret;
}
int main(){
	scanf("%d%d", &n, &m);
	p = qpow(2, n);
	fac[0] = 1;
	for (int i = 1; i < m; ++i)
		fac[i] = 1ll * fac[i - 1] * (p - i + P) % P;
	
	f[0] = 1, f[1] = 0;
	for (int i = 2; i <= m; ++i)
		f[i] = ((fac[i - 1] - f[i - 1] - 1ll * f[i - 2] * (i - 1) % P * (p - i + 1) % P) % P + P) % P;
	
	int inv = 1;
	for (int i = 1; i <= m; ++i) inv = 1ll * inv * i % P;
	inv = qpow(inv, P - 2);
	printf("%d\n", 1ll * f[m] * inv % P);
	return 0;
}