组合数学与 DP 结合

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\) 取模。

对于 \(100\%\) 的数据，\(1\le n,m \le 10^6\)。

实现 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
const int mod = 1e8 + 7;
int n, m, f[N], a[N];
int qpow(int n, int k)
{
    int ans = 1;
    while (k)
    {
        if (k & 1)
            ans = ans * n % mod;
        n = n * n % mod;
        k >>= 1;
    }
    return ans;
}
int fac[N];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    int p = qpow(2, n) - 1;
    a[0] = 1, fac[0] = 1;
    for (int i = 1; i <= m; i++)
    {
        a[i] = a[i - 1] * (p - i + 1 + mod) % mod;
        fac[i] = fac[i - 1] * i % mod;
    }
    f[0] = 1;
    for (int i = 2; i <= m; i++)
    {
        f[i] = a[i - 1];
        f[i] = (f[i] - f[i - 1] + mod) % mod;
        f[i] = ((f[i] - f[i - 2] * (i - 1) % mod * (p - i + 2)) % mod + mod) % mod;
    }
    // cout << f[2] << endl << f[3] << endl;
    cout << f[m] * qpow(fac[m], mod - 2) % mod;
    return 0;
}