自动搬运

查看原文

来自洛谷，原作者为

	xyz32768 “各方面相差太远”

搬运于2025-08-24 21:46:33，当前版本为作者最后更新于2018-02-12 17:07:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题真的变态。HN太厉害了！

发现题目中定义的同种音乐其实是假的，只要除以$m!$就可以了（利用逆元）。

这样就是在集合$S=\{1,2,...,n\}$中选出$m$个子集，满足三点性质：

（1）所有选出的$m$个子集都不能为空。

（2）所有选出的$m$个子集中，不能存在两个完全一样的集合。

（3）所有选出的$m$个子集中，$1$到$n$每个元素出现的次数必须是偶数。

DP。定义状态$f[i]$表示到第$i$个子集，满足所有三点性质的方案数。

考虑从容斥的角度分析，得出转移。由性质（3）得到，确定了前$i-1$个子集后，第$i$个子集也随之确定。这时方案数为$A_{2^n-1}^{i-1}$。

然后去掉不满足性质（1）的方案数。可以得出，如果第$i$个子集为空，那么前$i-1$个子集可以凑成一个合法的方案。因此不满足性质（1）的方案数为$f[i-1]$。

最后去掉不满足性质（2）的方案数。假设第$j$个子集与第$i$个子集重复，那么如果把第$j$个子集和第$i$个子集去掉，剩下的$i-2$个子集可以凑成一个合法的方案，即$f[i-2]$。而$j$有$i-1$种取值，子集$i$的取法为$2^n-1-(i-2)$。

因此不满足性质（2）的方案数为$f[i-2]\times(i-1)\times(2^n-i+1)$。 得出转移：

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

代码：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6 + 5, MX = 1e8 + 7; int n, m, f[N], orz = 1, mx = 1, A[N];
int qpow(int a, int b) {
	int res = 1; while (b) b & 1 ? res = 1ll * res * a % MX : 0,
		a = 1ll * a * a % MX, b >>= 1; return res;
}
int main() {
	int i; cin >> n >> m; for (i = 1; i <= n; i++) orz = orz * 2 % MX;
	orz = (orz - 1 + MX) % MX; A[0] = 1; for (i = 1; i <= m; i++)
		A[i] = 1ll * A[i - 1] * ((orz - i + 1 + MX) % MX) % MX,
	mx = 1ll * mx * i % MX; f[f[1] = 0] = 1; for (i = 2; i <= m; i++)
		f[i] = (A[i - 1] - f[i - 1] + MX - 1ll * f[i - 2] *
		(i - 1) % MX * (orz - i + 2 + MX) % MX + MX) % MX;
	cout << 1ll * f[m] * qpow(mx, MX - 2) % MX << endl; return 0;
}