题解：P14636 [NOIP2025] 清仓甩卖 / sale（民间数据）
FallingFYC_
·
·
题解
P14636 [NOIP2025] 清仓甩卖
出题人：听说你想参加 NOI？
先将 \{a_i\} 降序排序，以下的 \{a_i\} 皆为排序后的结果。
正着难做，考虑统计小 R 策略不优的方案数。
此时我们就枚举 $x$，$z$ 的范围就是一段区间 $[z_l,n]$，我们随便选一个子集令他们为 $1$ 元的糖果甚至令 $z$ 不存在都行，故贡献为 $2^{n-z_l+1}$，注意判重。
---
考虑推广。以上结构一定会出现在已经花费 $m-2$ 元的时候。而 $y$ 一定是第一个未被购买的 $2$ 元糖果，$x$ 一定是购买的 $1$ 元糖果中最后两个中的一个。我们枚举 $x,y$，方案数相当于：前 $x-1$ 个糖果中，第 $y$ 个为 $2$ 元的，且第 $y$ 个之前的 $2$ 元糖果与第 $x$ 个之前的 $1$ 元糖果都购买了，总花费为 $m-2$ 的方案数。用式子表示出来即为：
$$\sum_{i=0}^{y-1} \binom{y-1}{i} \binom{x-y-1}{m-2-((2*i)+(y-1-i))}$$
用范德蒙德卷积得到：
$$\sum_{i=0}^{y-1} \binom{y-1}{i} \binom{x-y-1}{m-1-y-i} = \binom{x-2}{m-1-y}
$$
再乘上 $z$ 的贡献即可。
时间复杂度 $O(n^2)$。
---
::::success[代码]
```cpp line-numbers
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=(a),E##i=(b);i<=E##i;i++)
#define REV(i,a,b) for(int i=(a),E##i=(b);i>=E##i;i--)
#define CLOSE_TIE ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define psbk push_back
#define endl '\n'
template <typename T>
void _outval(string s,int p,const T &t) {cout<<s.substr(p,s.length()-p)<<'='<<t<<endl; }
template <typename T, typename... Args>
void _outval(string s,int p,const T &t,const Args &...rest){
string n="";
while(s[p]!=',') n+=s[p++];
cout<<n<<'='<<t<<", ";
_outval(s,p+1,rest...);
}
#define outval(...) _outval(#__VA_ARGS__,0,__VA_ARGS__)
#define outarr(a,be,ed)\
{cout<<(#a)<<": ";\
FOR(iiii,be,ed)cout<<'['<<iiii<<"]="<<a[iiii]<<(iiii<ed?", ":"\n");}
const int N=5005;
const ll mod=998244353;
int c,T,n,m,a[N];
ll pow2[N<<1],fac[N<<1],finv[N<<1];
ll qpow(ll a,int b){
ll res=1;
for(;b;b>>=1,a=a*a%mod)
if(b&1) res=res*a%mod;
return res;
}
ll C(int n,int m){return (n<m||m<0?0:fac[n]*finv[n-m]%mod*finv[m]%mod);}
void solve(){
cin>>n>>m;
FOR(i,1,n) cin>>a[i]; a[n+1]=0;
if(m==1) return cout<<pow2[n]<<endl,void();
sort(a+1,a+n+1,greater<int>());
ll ans=0;
FOR(y,1,n){
int zl=n;
FOR(x,y+1,n){
if(a[x]*2<=a[y]) break;
for(;a[y]>a[zl]*2&&a[zl]<a[y]-a[x];zl--); zl=min(zl+1,n+1);
ans=(ans+C(x-2,m-1-y)*(pow2[n-zl+1]-(bool)(a[x]==a[y]))%mod)%mod;
}
}
ans=(pow2[n]-ans+mod)%mod;
cout<<ans<<endl;
}
signed main(){
CLOSE_TIE
pow2[0]=fac[0]=finv[0]=1;
FOR(i,1,(N<<1)-5){
pow2[i]=pow2[i-1]*2ll%mod;
fac[i]=fac[i-1]*(ll)(i)%mod;
finv[i]=qpow(fac[i],mod-2);
}
cin>>c>>T;
while(T--) solve();
return 0;
}
::::