过了所有大样例和洛谷数据。虽然 4h 才切，但也算是一雪前耻了。

:::info[Hint]{open} 正难则反，取不到最大原价总和只有两种情况：

• 最优解选性价比较低的 $2$，小 R 选性价比较高的 $1$，且 $1$ 的原价低于 $2$ 的原价。

• 最优解选性价比中的 $2$，小 R 选性价比较高的 $1$ 和性价比较低的 $1$，且两个 $1$ 的原价之和低于 $2$ 的原价。

上述的 $2$ 是最优解中选取的性价比最低的 $2$，上述的 $1$ 是小 R 选取的性价比最低的 $1$。

性价比高于所选性价比最低的 $2$ 的 $2$ 都必选，性价比高于所选性价比最低的 $1$ 的 $1$ 都必选。 :::

:::info[Tip] 一个组合意义显然成立的恒等式：

$$\sum_{i=0}^{k}\dbinom{n}{i}\dbinom{m}{k-i}=\dbinom{n+m}{k}$$

:::

按原价从大到小排序，枚举：（记 $c$ 为 $1\sim i-1$ 中 $2$ 的数量）

• 对于第一种情况，枚举最优解的 $2$（记为 $i$）以及小 R 的 $1$（记为 $j$），则 $a_i>a_j>\frac{1}{2}a_i$，则方案数为：

$$\sum_{c=0}^{i-1}\dbinom{i-1}{c}\dbinom{j-i-1}{m-(i-1+c)-2}=\dbinom{j-2}{m-i-1}$$

:::info[分析] 最优解选了 $1\sim i-1$ 中的所有、$i$、$i+1\sim j-1$ 中的 $1$。

小 R 选了 $1\sim i-1$ 中的所有、$i+1\sim j-1$ 中的 $1$、$j$。 :::

• 对于第二种情况，枚举最优解的 $2$（记为 $i$）以及小 R 的性价比较高的 $1$（记为 $j$），则 $a_i>a_j>\frac{1}{2}a_i$，设 $p$ 为使得 $a_k+a_{j}< a_{i}$（即可以成为性价比较低的 $1$）的最小的 $k$，则方案数为：

$$\sum_{k=p}^{n}2^{n-k}\cdot\sum_{c=0}^{i-1}\dbinom{i-1}{c}\dbinom{j-i-1}{m-(i-1+c)-2}=(2^{n-p+1}-1)\cdot\dbinom{j-2}{m-i-1}$$

:::info[分析] 最优解选了 $1\sim i-1$ 中的所有、$i$、$i+1\sim j-1$ 中的 $1$。

小 R 选了 $1\sim i-1$ 中的所有、$i+1\sim j-1$ 中的 $1$、$j$、$k$。 :::

于是在 $i,j$ 一定时，二种情况的方案数之和就是：

$$2^{n-p+1}\cdot\dbinom{j-2}{m-i-1}$$

$p$ 使用双指针维护即可。

时间复杂度 $\mathcal{O}(\sum n^2)$，空间复杂度 $\mathcal{O}(n^2)$ 或 $\mathcal{O}(n)$。

:::success[[NOIP2025] 清仓甩卖 - sale.cpp]

#include<bits/stdc++.h>
using namespace std;
const int maxn=5010;
const int mod=998244353;
int dp[maxn][maxn],pre[maxn],a[maxn];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    dp[0][0]=pre[0]=1;
    for(int i=1;i<=maxn-10;i++){
        dp[i][0]=1;
        pre[i]=pre[i-1]<<1;
        if(pre[i]>=mod) pre[i]-=mod;
        for(int j=1;j<=i;j++){
            dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
            if(dp[i][j]>=mod) dp[i][j]-=mod;
        }
    }
    int c,t;cin>>c>>t;
    while(t--){
        int n,m;cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        sort(a+1,a+1+n,greater<int>());
        long long ans=0;
        for(int i=1;i<=n;i++){
            if(m-i-1<0) break;
            int p=n+1;
            for(int j=max(i+1,m-i+1);j<=n;j++){
                if(a[i]==a[j]) continue;
                if(a[i]>=(a[j]<<1)) break;
                while(p>1 and a[p-1]+a[j]<a[i]) p--;
                ans+=1ll*dp[j-2][m-i-1]*pre[n-p+1]%mod;
            }
        }
        cout<<(pre[n]-ans%mod+mod)%mod<<"\n";
    }
    return 0;
}

:::