题解：P14636 [NOIP2025] 清仓甩卖 / sale（民间数据）

· · 题解

代码等公开再说。

多亏 T3 过于险恶，我在 12:30 的时候做出了回去优化 T2 \mathcal{O}(n^3) 而放弃 T3 的决定，于是过了 T2 所有大样例（应该没啥问题吧）。

先将物品价格从大到小排序。

我们可以想一下背包的时候什么情况下按性价比排序是错的。

比如说背包大小是 5，我有一个大小为 2，价值是 3 的物品，一个大小是 5，价值是 7 的物品，此时先放了第一个物品而导致第二个物品放不下了，必须是一个更贵的但是更值钱的物品放不下而此时背包没有填满导致的。

所以这个题显然也是因为放了一个 1 块的导致有个更贵的 2 块的放不下了。我们不妨枚举这两个物品为 a_i,a_j，则 w_i=2,w_j=1，且 2a_j>a_i>a_j，表示最后一个买的位置是 j，此时剩了 1 块钱，没买上 a_i。

那么很显然买东西花了 m-1 块。注意到前 i-1 个物品的性价比一定高于第 i 个所以都必须买。

注意我们要找到第一个 p 满足 a_p<a_i-a_j，那么 [p,n] 内的方案都可以随便选择，方案数是 2^{n-p+1}，而 w_{[j,p)} 必须为 2，否则剩的那 1 块钱可以再在 [j,p) 内再买一个形成更优的方案。

然后计算 [1,j] 的方案数。一共花了 m-1 块，前 i-1 个数花了 1 或 2 块，第 i+1 到 j-1 个数花了 0 或 1 块，第 j 个花了一块。

考虑直接先扔 i-1 块，这样前 i-1 个数也是花了 0 或 1 块。然后就是很简单的组合数问题了。

实现不难吧，等代码公开了我再更新。

upd on 2025.12.3

有个 sb 没预处理 2 的幂导致写成了 \mathcal{O}(n^2\log n) 然后获得了 92 分，我不说是谁。

这是预处理 2 的幂之后的 AC 代码：

#include<bits/stdc++.h>
using namespace std;
#define gc getchar
#define pc putchar
#define int long long
const int N = 5010, M = N * 2, mod = 998244353;
int sub, T, n, m, a[N], fr[M], ifr[M], bit[N];
int read() {
    int x = 0; char ch = gc();
    while(ch < '0' || ch > '9') ch = gc();
    while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48), ch = gc();
    return x;
}
void write(int x) {
    if(x == 0) {pc('0'); return ;}
    int tot = 0; char s[15];
    while(x) s[tot++] = x % 10 + '0', x /= 10;
    while(tot--) pc(s[tot]);
}
int Pow(int a, int b) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod; b >>= 1;
    }
    return ans;
}
void Add(int &x, int y) {
    x += y;
    if(x >= mod) x -= mod;
}
void Sub(int &x, int y) {
    x -= y;
    if(x < 0) x += mod;
}
void init(const int m = 10004) {
    fr[0] = ifr[0] = 1;
    for(int i = 1; i <= m; i++) fr[i] = fr[i - 1] * i % mod;
    ifr[m] = Pow(fr[m], mod - 2);
    for(int i = m - 1; i; i--) ifr[i] = ifr[i + 1] * (i + 1) % mod;
}
int C(int n, int m) {
    if(n < m || m < 0) return 0;
    if(m == 0) return 1;
    return fr[n] * ifr[m] % mod * ifr[n - m] % mod;
}
signed main() {
//  freopen("sale.in", "r", stdin);
//  freopen("sale.out", "w", stdout);
    init();
    sub = read(), T = read();
    bit[0] = 1; for(int i = 1; i <= 5000; i++) bit[i] = bit[i - 1] * 2 % mod;
    while(T--) {
        n = read(), m = read();
        for(int i = 1; i <= n; i++) a[i] = read();
        sort(a + 1, a + 1 + n); reverse(a + 1, a + 1 + n);
        int ans = 0;
        for(int i = 1; i <= n; i++) {
            int p = n + 1;
            for(int j = i + 1; j <= n; j++) if(a[i] != a[j]) {
                if(a[j] * 2 <= a[i]) break;
                while(p && a[p - 1] < a[i] - a[j]) p--;
                Add(ans, bit[n - p + 1] * C(j - 2, m - i - 1) % mod);
            }
        }
        ans = (Pow(2, n) - ans + mod) % mod;
        write(ans); pc('\n');
    }
    return 0;
}

// AFO on 2025.11.29