题解：P14636 [NOIP2025] 清仓甩卖 / sale

· · 题解

以此篇题解记录我失败的 NOIP。这凭啥有紫啊，还有和范德蒙德等式有啥关系。

考虑不优的情况，一种是可以把最小的两个 1 换成一个更大的 2，设可以把 a_i,a_j 换成 a_k，那么要求 a_i+a_j<a_k<2\max(a_i,a_j)；另一种是可以把最小的 1 换成一个 2，这种情况的要求是简单的。

先将 a 数组排序一下，对于第一种情况，枚举 i<j<k，发现对于 x>k 无论怎样都会被选，j<x<k 的 x 为 1 则会被选，为 2 则不会，i<x<j 由于钦定了 i,j 是最小的 1 因此只能为 2，一定不会选，1\le x<i 的无所谓随便选。只有 x>j 的部分才会被选，把一定被选的后 n-k 个数贡献扣掉，然后把剩下的 m-2-(n-k)（扣掉 a_i=a_j=1）分给 n-j-1 个数，就是组合数 \dbinom{m-2-n+k}{n-j-1}，完整的式子：

\sum_{i=1}^n\sum_{j=i+1}^n\sum_{k=j+1}^n[a_i+a_j<a_k<2a_j]2^{i-1}\times\dbinom{m-2-n+k}{n-j-1}

发现 i 在这个式子的贡献只有 2 的次幂，并且合法的 i 一定是一段前缀，可以用等比数列求和，所以只用枚举 j,k 并 O(1) 计算贡献，复杂度 O(n^2)。

而对于第二种情况相当于选了一个 a_j=0 的 j，可以和上面差不多计算。实现发现合法的 i 随 j 的增大而增大，因此双指针即可。时间复杂度 O(n^2)，跑得飞快。

笑点（这并不好笑）解析：考场上想冲正解所以没有枚举 k，死活做不出来。

代码过民间数据了，就先放上来了。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e4 + 5;
const int P = 998244353;
int a[N], fac[N], inv[N], pw[N];
inline int qpow(int a, int b = P - 2) {
    int res = 1;
    while (b) {
        if (b  & 1) res = res * a % P;
        a = a * a % P, b >>= 1;
    } return res;
}
inline void init() {
    pw[0] =fac[0] = inv[0] = 1;
    for (int i = 1; i < N; i++)
        pw[i] = pw[i - 1] * 2 % P, fac[i] = fac[i - 1] * i % P;
    inv[N - 1] = qpow(fac[N - 1]);
    for (int i = N - 2; i; i--)
        inv[i] = inv[i + 1] * (i + 1) % P;
}
inline int C(int n, int m) {
    if (n < 0 || m < 0 || n < m) return 0;
    return fac[n] * inv[m] % P * inv[n - m] % P;
}
inline void solve() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n); int ans = pw[n];
    for (int i = 1; i <= n; i++)
        for (int j = i + 1, x = 0; j <= n && a[i] +a[i] > a[j]; j++) {
            while (x <= i && a[x + 1] + a[i] < a[j]) x++;
            if (x >= i) break; if (a[j] ==  a[i]) continue;
            ans = (ans - pw[x] * C(n - i - 1, m - 2 - n + j) % P + P) % P;
        }
    cout << ans << '\n';
}
signed main() {
    freopen("sale.in","r",stdin);
    freopen("sale.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    init(); int c, T; cin >> c >> T;
    while (T--) solve();
    return 0; 
}