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

· · 题解

十二点多过了大样例。喜提后俩题加起来 13 分。要是这题挂分了真就要跳了。

感觉直接数不太好做，用 2^n 减去不合法方案数。考虑什么时候不合法，可以发现是一直买直到只剩下 1 元钱而下一个是 w=2，设这是第 i 个，此时只能跳过这个，去买后面第一个 w=1 的（也可能后面没有了），发现不合法当且仅当用第 i 个替换第 i 个前面的原价最低的 w=1 和后面的 w=1 （如果没有后面的就只考虑前面的）更优。先按照 a_i 从大到小排序，枚举 i 表示第一个买不到的 w=2 在排序后序列的位置，此时它前面的无论 w 取多少最终的性价比都会在这个前面，它后面可以有若干个 w 取 1，也在它前面。再枚举 i 后面最后一个 w=1 且 2a_j>a_i 的 j，此时相当于要求 w_j=1,w_i=2，且 ,\sum_{k=1}^{i-1}w_k 加上 w_{[i+1,j]} 中 1 的个数等于 m-1。此时我们知道 j 是 i 前面最后一个比 a_i 小的，那要求不合法就要 j 后面下一个 w=1 的位置 p 满足 a_p+a_j<a_i，合法的 a 是一段后缀，这段后缀任意选，方案数是 2 的幂次，j+1 到这段后缀前面只能令 w=2。特判 a_j=a_i 的情况，后缀长度是 0，但是要求严格小于，方案数不是 2^0 而是 0。然后发现只差等于 m-1 的限制，先把前 i-1 个 w_i 都减一，这样和是 m-1 的这些 w 取值都是 0 或 1 了，组合数选出一些是 1 即可。这样枚举 i,j，二分找到合法后缀，复杂度是 n^2\log n，发现后缀有单调性，双指针即可 O(n^2)。

::::info[考场代码]

#include<bits/stdc++.h>
using namespace std;

namespace z {
const int N = 5e5 + 5, mod = 998244353;
#define int long long
int a[N],fac[N],inv[N],pw[N];
int qpow(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
int C(int n, int m){
    if(n<0||m<0||n<m)return 0;
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
void main() {
    fac[0]=pw[0]=inv[0]=1;
    for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%mod,pw[i]=pw[i-1]*2%mod,inv[i]=qpow(fac[i],mod-2);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    freopen("sale.in","r",stdin);
    freopen("sale.out","w",stdout);
    int Cid, T;cin>>Cid>>T;
    while(T--){
        int n, m; cin >> n >> m;
        for(int i = 1; i <= n; i++) cin >> a[i],a[i]*=2;
        sort(a + 1, a + n + 1, greater<int>());
        int ans = qpow(2, n);
        for(int i = 1; i <= n; i++) {
            int l=n+1;
            for(int j = i+1;j<=n;j++) {
                if(a[j]>a[i]/2) {
                    l=max(l,j+1);
                    while(l-1>j&&a[l-1]+a[j]<a[i])l--;
                    int rem=max(0ll,j-1-(i+1)+1);
                    int tmp=C(rem+i-1,m-2-i+1);
                    ans-=tmp*(pw[n-l+1]-(a[i]==a[j]))%mod;
                }
            }

        }
        cout << (ans%mod+mod)%mod << '\n';
    }
}

#undef int

}

int main() {
    z::main();
    return 0;
}

::::