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

Skmqwq · 2025-11-29 18:24:58 · 题解

upd：修改了一处笔误。 upd：增加了代码。

注：本题解中的大小关系，前后顺序都是以性价比降序排序为基准。

考场上没调出来。倒闭。

正难则反。首先肯定要按照原价排序，我这里是升序排序。我们会发现不合法的情况一定是前面的一个 1 卡住了后面的一个 2。设 2 的位置是 i，那个 1 的取值范围就是 a_i 到 \frac{a_i}{2}，于是可以在这个范围里枚举 j（那个 1 的位置）。

注意到不合法的情况一定是后面不存在一个 1（设它的位置是 k）满足 a_j + a_k \ge a_i，于是 a_j 到 a_i - a_j 范围里的数的 w 必须是 2，而 a_i - a_j 到 1 范围里 1 和 2 都行。

然后因为卡住的原因一定是因为遇到这个 i 时的金币数只有 1 了。所以可以推得 \sum_{p>j}w = m-2，于是问题变为使性价比最大的 j - 1 个数的 w 的和为 m-2。

设 x 为 1 到 a_i - 1 中有多少个 2，nxt 为后面第一个可以填 1 的位置（可以用双指针维护），利用范德蒙德卷积可推得：

只需枚举 i, j，并用双指针维护 nxt，所以复杂度是 n^2 的。

最后，注意我们求得是反面，需要的是正面。

::::info[code]

const int N = 5e3 + 7, P = 998244353, M = 2 * N;
int n, m, c, t, fac[M], ifac[M], inv[M], pw[M], a[N];

inline int qp(int a, int b) {
    int ret = 1;
    while (b) {
        if (b & 1) ret = ret * a % P;
        a = a * a % P, b >>= 1;
    }
    return ret;
}
inline void init() {
    fac[0] = 1;
    rep(i, 1, 10000) fac[i] = fac[i - 1] * i % P;
    ifac[10000] = qp(fac[10000], P - 2);
    per(i, 10000, 1) ifac[i - 1] = ifac[i] * i % P;
    rep(i, 1, 10000) inv[i] = ifac[i] * fac[i - 1] % P;
    pw[0] = 1;
    rep(i, 1, 10000) pw[i] = pw[i - 1] * 2 % P;
}
inline int C(int n, int m) {
    if (n < m) return 0;
    if (n < 0) return 0;
    if (m < 0) return 0;
    return fac[n] * ifac[n - m] % P * ifac[m] % P;
}
inline void add(int &a, int b) {
    a += b;
    if (a > P) a -= P;
}

inline void Solve() {
    int ans = 0;
    cin >> n >> m;
    init();
    rep(i, 1, n) cin >> a[i]; a[n + 1] = 0;
    sort(a + 1, a + 1 + n);
    rep(i, 1, n) {
        int nxt = i - 1;
        rep(j, 1, i - 1) if(a[j] < a[i] && (a[j]<<1) > a[i]) {
            while (a[j] + a[nxt] >= a[i]) --nxt;
            add(ans, pw[nxt] * C(n - j - 1, m - n + i - 2) % P);
        }
    }
    cout << (qp(2, n) - ans + P) % P << '\n';
}

signed main() {
    std::ios::sync_with_stdio(false);   
    std::cin.tie(0);
    std::cout.tie(0);

    cin >> c >> t;
    while (t--) Solve();

    return 0;
}

::::