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

· · 题解

第一次正赛切紫，留念。

以下的 a_i 均已经降序排序方便考虑。

正难则反，考虑统计贪心策略不优的方案数。首先手动模拟一下样例，我们发现当且仅当一个较大的 a_i 因为 w_i=2 而被较后选择，而后面的某个 a_j>\dfrac{a_i}2(w_j=1) 在被选择后恰好 m=1 导致 a_i 没有被选择使得贪心策略不优（为什么有大于的限制？因为 a_j 要在 a_i 前被选择）。

我们讨论一下 m=1 时如果后面还有 a_k(w_k=1) 被抉择的情况，发现这样的 k 的范围是一个 [k_0,n] 的形式，可以在从小到大枚举 j 的时候双指针顺便做掉。显然 k 即后面的 a 其 w 均可随意抉择，所以考虑直接枚举 i 和 j，其就是 w_1 \cdots w_j 的方案数与 2^{n-k_0+1} 的乘积（此时我们已经钦定 w_i=2,w_j=1,w_{j+1} \cdots w_{k-1}=2）。

我们发现我们需要在决策完 a_j 时 m 恰为 1，那么我们需要在 1 到 j 剩余的 j-2 个位置上填 w，这个直接组合意义是不太好做的。我们再考虑枚举 i+1 \cdots j-1 中有多少个 w_k=1 即这些 a_k 会在 a_j 前被选择，假设有 x 个这样的 k(w_k=1)。我们发现在 i 之前的无论 w 为 1 或 2 都一定会被选择，也就是说我们要求 w_1 \cdots w_{i-1} 的和为 m-x-2，那么我们可以把这两部分组合意义分开计算：

\sum_{x=0}^{j-i-1} \binom{j-i-1}{x} \times \binom{i-1}{m-i-1-x}

显然直接枚举 i,j,x 是 \mathcal{O}(n^3) 的，考虑优化上面这个式子。这里引用一句不知道谁说的话：代数推导天地灭，组合意义保平安。我们考虑该式的实际组合意义：共 (j-i-1)+(i-1) 个球，在前 j-i-1 个球中取 x 个，在后 i-1 个球中取 m-i-1-x 个，枚举 x，也就是说上式等价于：

\binom{j-2}{m-i-1}

于是我们可以省去枚举 x 的时间复杂度，\mathcal{O}(n^2) 可通过本题。

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

inline int read() {
    int x=0,ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch&15);
    return x;
}

using ll=long long;
const ll mod=998244353;
const int N=5005;
int c,T,n,m;
struct Candy {
    int val,id;
    Candy(int val=0,int id=0) {this->val=val,this->id=id;}
    inline bool operator <(const Candy& tmp) const {
        if(val==tmp.val) return id<tmp.id;
        return val>tmp.val;
    }
} a[N];

inline ll quickpow(ll base,ll p) {
    ll tmp=1;
    for(;p;p>>=1) {
        if(p&1) tmp=tmp*base%mod;
        base=base*base%mod;
    }
    return tmp;
}
ll pw[N],fact[N],inv[N];
inline void init() {
    static const int s=5000;
    pw[0]=fact[0]=inv[0]=1;
    for(int i=1;i<=s;i++) {
        pw[i]=pw[i-1]<<1;
        if(pw[i]>=mod) pw[i]-=mod;
    }
    for(int i=1;i<=s;i++) {
        fact[i]=fact[i-1]*i%mod;
        inv[i]=quickpow(fact[i],mod-2);
    }
    return ;
}
inline ll C(int n,int m) {
    if(n<0||m<0||n<m) return 0;
    return fact[n]*inv[m]%mod*inv[n-m]%mod;
}

int main() {
    c=read(),T=read(),init();
    while(T--) {
        n=read(),m=read();
        for(int i=1;i<=n;i++) a[i].val=read(),a[i].id=i;
        sort(a+1,a+1+n); ll ans=0;
        for(int i=1;i<n;i++) {
            int q=lower_bound(a+1,a+1+n,Candy(a[i].val>>1,0))-a;
            for(int j=i+1,k=n;j<q;j++) {
                if(a[j].val==a[i].val) continue ;
                while(k>=q&&a[j].val+a[k].val<a[i].val) k--;
                (ans+=C(j-2,m-i-1)*pw[n-k])%=mod;
            }
        }
        if((ans=pw[n]-ans)<0) ans+=mod;
        printf("%lld\n",ans);
    }
    return 0;
}