思路与算法

应判断每种定价下，性价比贪心是否等于这一种定价对应的最优0/1背包，而不是把不同定价所得收益相互比较。先统计失败定价数bad，答案为2^n−bad。按原价递减、相同原价按原编号排列。失败方案唯一确定第一个买不起的2元糖果c，以及它之前买到的1元糖果中最小原价v，必须c/2<v<c。设c在该顺序中的0起始下标为h；N为原价≥v的个数，Cv为原价=v的个数，L为原价<c−v的个数，k=m−1−h。这类失败定价数是2^L·[C(N−1,k)−C(N−Cv−1,k)]。枚举c和不同的v值求和，严格小于的边界用有序指针处理。所有组合数用一次杨辉三角预处理，负下标或越界组合数为0。若2·min(a)>max(a)，所有v后的自由低价区域均为空，关于v的相邻组合数差可望远镜相消，进一步用O(n)计算该组。

正确性说明

先解释失败结构。把所有1元糖果、2元糖果分别按原价递减排序；购买固定数量的2元糖果后，最优方案一定取相应的最高原价前缀，再用剩余预算取最高原价1元前缀。以2元购买数量为自变量，其最优总原价是离散凹函数，因此检查相邻的一次交换已足够。性价比排序保证减少一个已买2元糖果、增加最多两个1元糖果不会改善答案。唯一可能的改进是多买一个未买2元糖果。若第一次买不起2元糖果时余钱0，此前1元糖果的原价都至少为c/2，换掉两个也不会改善；所以失败时余钱恰为1，即此前花m−1。此时最先未买的2元原价为c，设此前最小1元原价v，之后能买的首个1元原价为b（没有则b=0），交换改善当且仅当c>v+b，从而必有c/2<v<c。

再计数。c之前的h个原价顺序项目，无论定1元还是2元都排在c之前，费用生成函数为z^h(1+z)^h。其余原价≥v且不含c的项目，1元时在c之前、2元时在之后，贡献(1+z)^(N−1−h)；同时至少有一个原价恰为v的项目被定为1元，故减去该整组全为2元的情况。取花费m−1的系数即得到两个组合数之差。原价在[c−v,v)内的项目必须全部为2元，否则会改变v或使b≥c−v；原价<c−v的L个项目可任意定价，乘2^L。c及v在失败方案中唯一，所以各分类不重不漏。最终从全部2^n种方案中减去bad即为所求。

复杂度

设所有组最大n为nmax≤5000，单点总N≤50000。一次杨辉三角与2的幂初始化耗时O(nmax²)、空间O(nmax²)，三角存储约50MB。每组排序O(n log n)，枚举c及v组并用单调L指针，O(n²)，总时间O(nmax²+Σn²)，输入输出O(N+t)亦计入。全部组原数组合计O(N)空间。特殊高价分支的望远镜优化仅降低常数和部分组时间，不是依赖数据性质才能正确。

易错点

比较性价比要交叉乘，或者在计数推导中坚持严格边界；c/2=v时2元且原价更高的c先被考虑，不能计入失败区间。重复原价要整组扣除，不能把同值v的不同个体多次分类。题目有t=50000、总N=50000的情况，也有10组n=5000；预处理只能全文件做一次。不要把题意误读为寻找跨所有定价的统一最高收益。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
struct FastInput {
    static const int SZ = 1 << 16;
    char a[SZ];
    int at = 0, len = 0;
    int get() {
        if (at == len) {
            len = fread(a, 1, SZ, stdin);
            at = 0;
            if (!len)
                return -1;
        }
        return a[at++];
    }
    int next() {
        int c;
        do {
            c = get();
        } while (c <= 32 && c >= 0);
        int x = 0;
        while (c >= 48 && c <= 57) {
            x = x * 10 + c - 48;
            c = get();
        }
        return x;
    }
};
struct Case {
    int n, m;
    vector<int> a;
};
vector<int> binomial, power2;
vector<size_t> offset;
int choose(int n, int k) {
    if (k < 0 || k > n || n < 0)
        return 0;
    return binomial[offset[n] + k];
}
int solve(Case &test) {
    int n = test.n, m = test.m;
    vector<int> &a = test.a;
    stable_sort(a.begin(), a.end(), greater<int>());
    vector<int> end(n);
    for (int i = 0; i < n;) {
        int j = i;
        while (j + 1 < n && a[j + 1] == a[i])
            ++j;
        for (int k = i; k <= j; ++k)
            end[k] = j;
        i = j + 1;
    }
    int bad = 0;
    if (2LL * a.back() > a.front()) {
        for (int h = 0; h < n; ++h) {
            int k = m - 1 - h;
            if (k <= 0 || k > n - 1)
                continue;
            int d = choose(n - 1, k) - choose(end[h], k);
            if (d < 0)
                d += MOD;
            bad += d;
            if (bad >= MOD)
                bad -= MOD;
        }
    } else {
        for (int h = 0; h < n; ++h) {
            int k = m - 1 - h;
            if (k <= 0 || k > n - 1)
                continue;
            int c = a[h], L = 0;
            for (int j = end[h] + 1; j < n && 2LL * a[j] > c; j = end[j] + 1) {
                int last = end[j];
                if (last < k)
                    continue;
                int v = a[j];
                while (L < n && a[n - 1 - L] < c - v)
                    ++L;
                int d;
                if (last == j)
                    d = choose(j - 1, k - 1);
                else {
                    d = choose(last, k) - choose(j - 1, k);
                    if (d < 0)
                        d += MOD;
                }
                if (!d)
                    continue;
                int term = L ? int(1LL * d * power2[L] % MOD) : d;
                bad += term;
                if (bad >= MOD)
                    bad -= MOD;
            }
        }
    }
    int result = power2[n] - bad;
    if (result < 0)
        result += MOD;
    return result;
}
int main() {
    FastInput in;
    int type = in.next(), T = in.next(), maxn = 0;
    vector<Case> tests(T);
    for (auto &x : tests) {
        x.n = in.next();
        x.m = in.next();
        x.a.resize(x.n);
        for (int &a : x.a)
            a = in.next();
        maxn = max(maxn, x.n);
    }
    offset.resize(maxn + 1);
    for (int i = 0; i <= maxn; ++i)
        offset[i] = size_t(i) * (i + 1) / 2;
    binomial.resize(size_t(maxn + 1) * (maxn + 2) / 2);
    for (int i = 0; i <= maxn; ++i) {
        binomial[offset[i]] = binomial[offset[i] + i] = 1;
        for (int j = 1; j < i; ++j) {
            int x = binomial[offset[i - 1] + j - 1] + binomial[offset[i - 1] + j];
            if (x >= MOD)
                x -= MOD;
            binomial[offset[i] + j] = x;
        }
    }
    power2.resize(maxn + 1);
    power2[0] = 1;
    for (int i = 1; i <= maxn; ++i)
        power2[i] = power2[i - 1] * 2LL % MOD;
    for (auto &x : tests)
        printf("%d\n", solve(x));
}