题解：P14636 [NOIP2025] 清仓甩卖 / sale（民间数据）
Night_sea_64
·
·
题解
我觉得这题最多蓝。为啥都要范德蒙德卷积？我一度以为自己过了所有大样例的做法假了。
首先，注意到这是一个背包弱化版的贪心做法。
我们可以注意到，这个贪心是假的，当且仅当你选的一个 w=1，创飞了一个可能更优的 w=2。
于是可以枚举那个没选的 w=2，再枚举那个创飞它的 w=1。
先将原价排序。枚举到 i 位置 w=2 被创飞了，并且创飞它的是 j。j 需要满足 a_j<a_i 且 2\times a_j>a_i。
可以发现：
-
-
-
-
- 如果 j 后面的第一个 w=1 是 k，需要满足 a_j+a_k<a_i，不然选了 j,k 就更优了。找到第一个满足这条件的 k。j+1\sim k 都是 w=2，不选。k 及其后面的可以随便（k 不一定 w=1）。
然后 i-1 及之前的 w 之和加上 i+1\sim j-1 的 w=1 的个数恰好是 m-2 才行。因为选了个 j 之后是 m-1，但是你把 j 删掉加入 i 更优可以凑到恰好 m。
枚举 $j$ 找 $k$ 的过程双指针即可。复杂度 $O(n^2)$。
```cpp
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
int cid,t,n,m;
const int nr=5010,mod=998244353;
int c[nr][nr],power[nr];
int a[nr];
bool cmp(int x,int y){
return x>y;
}
int C(int x,int y)
{
if(x<0||y<0||x<y)return 0;
return c[x][y];
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>cid>>t;
for(int i=0;i<=5000;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;
}
power[0]=1;
for(int i=1;i<=5000;i++)power[i]=power[i-1]*2%mod;
while(t--)
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1,cmp);
int ans=0;
for(int i=1;i<=n;i++)
{
int pos=i;
while(pos<=n&&a[pos]==a[i])pos++;
pos--;
int k=n+1;
for(int j=pos+1;j<=n&&a[j]*2>a[i];j++)
{
while(a[j]+a[k-1]<a[i])k--;
ans+=C(j-2,m-i-1)*power[n-k+1];
ans%=mod;
}
}
cout<<(power[n]+mod-ans)%mod<<'\n';
}
return 0;
}
```