P14636 [NOIP2025] 清仓甩卖
zhlzt
·
·
题解
过了所有大样例和洛谷数据。虽然 4h 才切，但也算是一雪前耻了。
:::info[Hint]{open}
正难则反，取不到最大原价总和只有两种情况：
上述的 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，且所有 k>j 必有 w_k=2，则方案数为：
\sum_{c=0}^{i-1}\dbinom{i-1}{c}\dbinom{j-i-1}{m-(i-1+c)-2}=\dbinom{j-2}{m-i-1}
-
对于第二种情况，枚举最优解的 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}
于是在 i,j 一定时，二种情况的方案数之和就是：
2^{n-p+1}\cdot\dbinom{j-2}{m-i-1}
时间复杂度 $\mathcal{O}(\sum n^2)$，空间复杂度 $\mathcal{O}(n^2)$ 或 $\mathcal{O}(n)$。
:::success[[NOIP2025] 清仓甩卖 - sale.cpp]
```cpp line-numbers
#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;
}
```
:::