题意简述

对 $1 \sim n$ 的所有子集 $b$，设 $k = |b|$，计算 $\operatorname{MEX}(b, k+1)$ 的和，结果对 $10^9+7$ 取模。

贡献转换

对每个可能的答案 $x$，统计有多少子集满足 $f(b) = x$。

要使 $\operatorname{MEX}(b, k+1) = x$，必须满足：

• $x \notin b$；
• 在 $1 \sim x-1$ 中，不在 $b$ 中的正整数个数恰好为 $k$。

即 $b$ 在 $[1, x-1]$ 中选取了 $t = x - 1 - k$ 个元素。显然 $0 \le t \le \min(x-1, k)$。
$b$ 的其余 $k - t$ 个元素只能从 $> x$ 的部分选取，若 $x \le n$ 则 $x$ 本身不可选。

组合公式

固定 $x$ 和 $k$，满足条件的子集个数为：

$$\binom{x-1}{t} \times \binom{n - \min(x, n)}{k - t} $$

其中 $t = x - 1 - k$，且要求 $k - t \le n - \min(x, n)$。

$x$ 的范围为 $1 \sim 2n+1$。
$k$ 的范围为 $0 \sim n$，但受 $t$ 限制可缩小枚举区间。

最终答案为：

$$\sum_{x=1}^{2n+1} \sum_{k} x \cdot \binom{x-1}{t} \cdot \binom{n - \min(x,n)}{k - t} \pmod{M} $$

实现细节

• 用阶乘和逆元数组 $O(2n)$ 预处理，组合数 $O(1)$ 查询。
• 对每组 $n$，双重循环枚举 $x$ 和 $k$，内部直接公式计算。
• 时间复杂度 $O(n^2)$，总 $\sum n^2 \le 25\times 10^6$，在 2.5 秒内可行。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;
const int MAXV = 10015; // 2 * 5000 + 5

ll fact[MAXV], invfact[MAXV];

ll modpow(ll a, ll e) {
    ll r = 1;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

void precompute(int max_n) {
    int limit = 2 * max_n + 5;
    fact[0] = 1;
    for (int i = 1; i < limit; ++i)
        fact[i] = fact[i-1] * i % MOD;
    invfact[limit-1] = modpow(fact[limit-1], MOD-2);
    for (int i = limit-2; i >= 0; --i)
        invfact[i] = invfact[i+1] * (i+1) % MOD;
}

ll nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] * invfact[r] % MOD * invfact[n-r] % MOD;
}

void solve(int n) {
    ll ans = 0;
    int max_x = 2 * n + 1;
    for (int x = 1; x <= max_x; ++x) {
        int mx = min(x, n);
        int L = max(0, (x + 1) / 2);       // 最小的 k 使得 t = x-1-k ≥ 0
        int R = min(n, x - 1);             // 最大的 k
        for (int k = L; k <= R; ++k) {
            int t = x - 1 - k;
            int rem = k - t;               // 需要从 >x 选取的个数
            if (rem < 0 || rem > n - mx) continue;
            ll ways = nCr(x-1, t) * nCr(n - mx, rem) % MOD;
            ans = (ans + 1LL * x * ways) % MOD;
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    vector<int> ns(t);
    int max_n = 0;
    for (int i = 0; i < t; ++i) {
        cin >> ns[i];
        max_n = max(max_n, ns[i]);
    }
    precompute(max_n);
    for (int n : ns) solve(n);
    return 0;
}