#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

ll countLists(int n, int m) {
    if (n == 1) return m; // 单独处理n=1的情况

    vector<ll> prev(m + 1, 0);
    for (int j = 1; j <= m; ++j)
        prev[j] = 1; // 初始化n=1的情况

    for (int i = 2; i <= n; ++i) {
        ll min_j = 1LL << (i - 1); // 当前层最小允许的数值
        if (min_j > m) return 0;

        // 构建前缀和数组
        vector<ll> sum_prev(m + 1, 0);
        sum_prev[0] = 0;
        for (int j = 1; j <= m; ++j)
            sum_prev[j] = sum_prev[j - 1] + prev[j];

        vector<ll> current(m + 1, 0);
        for (int j = min_j; j <= m; ++j) {
            int max_k = j / 2; // 前一个数的最大值
            current[j] = sum_prev[max_k];
        }
        prev = current;
    }

    ll total = 0;
    for (int j = 1; j <= m; ++j)
        total += prev[j];
    return total;
}

int main() {
    int C, n, m;
    cin >> C;
    for (int c = 1; c <= C; ++c) {
        cin >> n >> m;
        ll ans = countLists(n, m);
        cout << "Case " << c << ": n = " << n << ", m = " << m 
             << ", # lists = " << ans << endl;
    }
    return 0;
}

代码解释初始化：

当N=1时，每个数字都构成合法列表，直接返回M。 动态规划数组构建：使用prev数组记录前一层状态，逐步计算每一层的可能值。 前缀和优化：通过前缀和数组sum_prev快速累加前驱状态，避免重复遍历。 结果统计：将最后一层的所有可能值累加，得到最终结果。 该算法时间复杂度为$O(N×M)$，能够高效处理题目给定的输入范围，正确计算所有合法序列数目