Luogu

分析

首先题目中的集合是无序的，我们将其转为有序的来计算，只需要最后除以 $m!$ 即可。

设 $f_i$ 表示划分为 $i$ 个片段的方案数，考虑转移。

首先，如果我们已经确定了前 $i - 1$ 个片段，那么第 $i$ 个片段唯一确定，这样子的方案数为 $A_{2^n - 1}^{i - 1}$。

但是这样子会有一些不合法的情况：

• 第 $i$ 个片段为空：这样子去掉第 $i$ 个后也合法，方案数为 $f_{i - 1}$。
• 第 $i$ 个片段和之前的某个片段重复：这样子去掉这两个片段后也合法，且之前的片段有 $i - 1$ 种、$i$ 有 $2^n - 1 - (i - 2)$ 种，因此方案数为 $f_{i - 1} \times (i - 1) \times [2^n - 1 - (i - 2)]$。

预处理排列数 $\mathcal{O}(m)$ 计算即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X = 0, w = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}

const int N = 1000000 + 10;
const int mod = 1e8 + 7;
int qpow(int a, int b) {
    int c = 1;
    for (; b; b >>= 1, a = 1ll * a * a % mod)
        if (b & 1) c = 1ll * c * a % mod;
    return c;
}

int n, m, f[N], A[N];

int main() {
    n = read(), m = read(); int c = qpow(2, n) - 1, fac = 1;
    A[0] = 1;
    for (int i = 1; i <= m; ++i)
        A[i] = 1ll * A[i - 1] * (c - i + 1 + mod) % mod, fac = 1ll * fac * i % mod;
    f[0] = 1, f[1] = 0;
    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] - 1ll * f[i - 2] * (i - 1) % mod * (c - (i - 2) + mod) % mod + mod) % mod;
    }
    printf("%d\n", 1ll * f[m] * qpow(fac, mod - 2) % mod);
    return 0;
}