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

· · 题解

题外话：这个题其实并没有像大家想的那么难写/有一车 corner case，实际上写起来很简单而且总共有 0 个分讨。

为了方便描述，以下记题面中的 w_i 为物品的体积。

第一步显然是考虑把条件刻画成一个简洁可做的形式。发现合法条件并不好刻画，正难则反，我们考虑什么时候不合法。

显然在大多数时候，直接贪心选性价比最高的肯定没有问题。唯一的例外可能是：我们先用一个体积小但价值也小的填了进去，可是实际上更优的体积更大的数却填不进去了。

也就是说，当且仅当最后剩余体积为 2 时，有可能出现我们按照贪心策略选了一个体积为 1 的物品，这时候最多只能再选一个体积为 1 的物品，但是实际上把这两个物品扔掉换成一个体积为 2 的物品更优。

整理一下条件，如下图（x,y 分别为最后考虑的两个体积为 1 的物品，z 为更优的体积为 2 的物品）：

当然其实有个小 bug：有可能 x 是价值最小的一个体积为 1 的物品，这时候 y 不存在。不过别急，我们将会在稍后描述其正确性。

我们发现，由于在分别确定完价值为 1 和 2 的物品的集合后，实际上每个集合内最后被选出来的都是一段后缀，而我们的判定条件又只跟最小的几个位置相关，因此我们不难想到枚举这些位置。具体而言，我们考虑把 a 从小到大排序，然后枚举 x 和 z 所在的位置 p 和 q，其中必须满足 a_p > \frac{a_q}{2} 且 a_p < a_q。这里的 p 和 q 实际上分别是所有在贪心策略中被选上的 1 的最小值和没有被选上的 2 的最大值。

我们考虑“选出的数和为 m”的限制。对于 [p+1,q-1] 中间的所有物品，如果体积是 2 那么不产生贡献（因为 a_q 都没被选上那么它价值更小，更不可能），否则一定被选上产生 1 的贡献（由于 a_p 被选上了所以它一定也得选上）。而对于 [q+1,n] 的物品，一定会被选上，产生 1 或 2 的贡献。

也就是说，我们有 q-p-1 个数可以为 0/1，n-q 个数可以为 1/2，现在要给它们分配权值，使得其和为 m-2，问方案数（这里 -2 是因为 a_q 自己占掉两格体积）。

这一步显然可以直接范德蒙德卷积，如果你不会也很简单，考虑把后 n-q 个数全部减去 1，那么相当于有 q-p-1+n-q = n-p-1 个值为 0/1 的变量，要求和为 m-2-(n-q)，方案数显然是 \binom{n-p-1}{m-2-(n-q)}。

别忘了我们还没考虑 z > x+y 的限制。也就是说，对于 a_q - a_p \le a_k 且 k < p 的所有的 k，它们的体积必须是 2，否则选择 a_p 和 a_k 肯定更优，这样就不满足我们的要求。我们发现，没有限制体积的部分一定是一段前缀 [1,r]，其中 p 固定时 r 随着 q 增加而增加，因此可以双指针算出 r。而 [1,r] 里的物品体积是多少没有任何限制，因此方案数是 2^r。这时候大家可能还记得我们前面提到的“无 y 可选”的情况，此时当且仅当 p 之前没有任何一个体积为 1 的物品，恰好是 2^r 种情况中的一种，因此我们这里非常自然地处理到了这一种情况。

如果你觉得听不太明白，可以看下面的图：

时间复杂度 O(n^2)，代码很好写。

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define fir first
#define sec second
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define pb push_back
const int inf=0x3f3f3f3f;
const int mod=998244353;
int C[5010][5010],pw[5010];
void init(int n)
{
    pw[0]=1;
    for(int i=1;i<=n;i++)pw[i]=(pw[i-1]<<1)%mod;
    for(int i=0;i<=n;i++)
    {
        C[i][0]=1;
        for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    }
}
int n,m,a[5010],ans;
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    ans=0;
    for(int i=1;i<=n;i++)for(int j=i+1,k=0;j<=n;j++)if(a[i]*2>a[j]&&a[i]!=a[j])
    {
        while(k<j-1&&a[i]+a[k+1]<a[j])k++;
        int sum=m-2-(n-j);
        int cnt=n-i-1;
        if(cnt<sum||sum<0)continue; 
        (ans+=1ll*pw[k]*C[cnt][sum]%mod)%=mod;
    }
    ans=(pw[n]-ans+mod)%mod;
    cout<<ans<<'\n';
}
signed main()
{
    init(5000); 
    int c,t;
    cin>>c>>t;
    while(t--)solve();
    return 0;
}