题意#

有 $n$ 个音，$m$ 个音乐片段构成一首歌。音乐的每个片段都是从 $n$ 个音阶中挑选若干个音阶同时演奏出来。

要求：任意两个片段所包含的音阶集合都不同。

要求：每个音在这首歌中被奏响的次数为偶数。

求满足上述条件的歌一共有多少种，答案对 $10^8+7$ 取模。

两段音乐 $a$ 和 $b$ 同种当且仅当将 $a$ 的片段重新排列后可以得到 $b$。

$1\le n,m \le 10^6$。

题解#

思路#

$n$ 个音，$m$ 个片段。

题目忽略顺序，我们忽略要求，最后用答案 $\times \frac{1}{m!}$ 即可。

设 $f_i$ 表示前 $i$ 个片段的可选方案数。

利用二进制转化一下：

每种选择方式编号为 $1,2,\cdots, 2^n-1$。选 $m$ 个数，异或和为 $0$，且不存在两个相同。

先不考虑任意两个数不相同：

前 $i$ 个数的可选方案数，不是 $C_{2^n-1}^i$，因为需要保证异或和为 $0$。

注意到，若前 $i-1$ 个数已经确定，那么第 $i$ 个数则唯一固定，所以方案数为 $C_{2^n-1}^{i-1}$.

但这并不完全正确，有两种不合法的情况需要考虑：

情况一#

若前 $i-1$ 个数异或和为 $0$，第 $i$ 个数只能为 $0$，但可选数中不存在 $0$ 这个数。

这种情况的方案数为 $f_{i-1}$.

情况二#

根据组合数，我们选取的前 $i-1$ 个数一定两两不等，但第 $i$ 个数有可能和前面中的某个数相等，需要减去这种情况。

不妨设第 $j$ 个数与第 $i$ 个数相等。

1. 其他 $i-2$ 个数异或和为 $0$、且选取方式完全合法，有 $f_{i-2}$ 种选择方法。

2. $j$ 这个位置有 $(i-1)$ 种可能，每个位置下，都可以从 $1\sim 2^n-1$ 中选取，唯一的限制是不能与其他 $(i-2)$ 个数相等，有 $(i-1)[2^n-1-(i-2)]$ 种选择方法。

综上，第二组不合法情况的方案数为 $f_{i-2}(i-1)[2^n-1-(i-2)]$.

将这两种情况减去即可。

$$f_i=C_{2^n-1}^{i-1}-f_{i-1}-f_{i-2}(i-1)(2^n-1-(i-2))$$

递推求解，

$$\operatorname{Ans}=\frac{f_m}{m!}\bmod 100000007$$