P3214 [HNOI2011] 卡农

题目描述

众所周知卡农是一种复调音乐的写作技法，小余在听卡农音乐时灵感大发，发明了一种新的音乐谱写规则。

他将声音分成 $n$ 个音阶，并将音乐分成若干个片段。音乐的每个片段都是由 $1$ 到 $n$ 个音阶构成的和声，即从 $n$ 个音阶中挑选若干个音阶同时演奏出来。

为了强调与卡农的不同，他规定任意两个片段所包含的音阶集合都不同。同时为了保持音乐的规律性，他还规定在一段音乐中每个音阶被奏响的次数为偶数。

现在的问题是：小余想知道包含 $m$ 个片段的音乐一共有多少种。

两段音乐 $a$ 和 $b$ 同种当且仅当将 $a$ 的片段重新排列后可以得到 $b$ 。例如：假设 $a$ 为 ${{1, 2}, {2, 3}}$ ， $b$ 为 ${{2, 3}, {1, 2}}$ ，那么 $a$ 与 $b$ 就是同种音乐。

答案对 $10^{8} + 7$ 取模。

仅一行两个正整数 $n, m$

输出一行一个整数表示答案。

2 3

【数据范围】

【样例解释】

本题可转化为：在集合 $S = {1, 2, \dots, n}$ 中选出 $m$ 个子集，满足性质：

定义 $f (i)$ 为逐个选出 $i$ 个子集满足条件的方案数。

由性质 3 可知，确定了前 $i - 1$ 个非空子集后，第 $i$ 个子集也确定下来。因此方案数为 $A_{2^{n} - 1}^{i - 1}$ 。

去掉不满足性质 1 的方案数。若最后一个子集为空，则前 $i - 1$ 个子集已经满足了所有条件，方案数为 $f (i - 1)$ 。

去电不满足性质 2 的方案数。若第 $j$ 个子集和第 $i$ 个子集相同，则除这两个子集外剩下的 $n - 2$ 个子集是一个合法的方案。因此方案数为 $f (i - 2) \times (i - 1) \times (2^{n} - 1 - (i - 2))$ 。

因此有

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

由于我们的定义“逐个选出”与题目要求的“同种音乐”相冲突，将方案数除以 $m!$ 即可。