题解：P14636 [NOIP2025] 清仓甩卖 / sale
yangzichen1203
·
·
题解
勘误：11.30 15:34 发现一处笔误，请求重新审核
计数好题，主要难点在于推式子（但我赛时没写完……）
显然答案与顺序无关，则我们先对 a 数组从小到大排序。
我们再考虑 $m\ne2$ 的情况。对于 $m=1$，显然 $ans=2^n$。而对于 $m>2$，我们考虑如何将其转换到 $m=2$ 上。我们枚举 $i$ 为被卡掉的那个数的位置，$j$ 为第一个去卡 $i$ 的数的位置，$k$ 为 $i$ 前面最大的数的位置，$t$ 为 $[i+1,n]$ 区间内 $2$ 的个数，则答案为
$$\sum_{i=1}^n\sum_{j=1}^{i-1}\sum_{t=0}^{n-i}\binom{n-i}{t}\binom{i-j-1}{m-n+i-2-t}(1+\sum_{k=1}^{j-1}2^{k-1})[a_j<a_i \land 2a_j>a_i \land a_j+a_k<a_i]$$
直接做是 $O(n^4)$ 的，不可接受，我们考虑优化。
发现 $k$ 的贡献可以用等比数列求和来计算，即 $1+\sum_{k=1}^{j-1}2^{k-1}[a_k<a_i-a_j]=2^K$，其中 $K$ 表示最大的满足 $a_k<a_i-a_j$ 的 $k$，这可以通过二分求出。时间复杂度就能被优化到 $O(n^3\log n)$。
:::info[等比数列求和]
$$\sum_{i=0}^nx^i=\frac{x^{n+1}-1}{x-1}$$
证明：
设
$$t=\sum_{i=0}^nx^i$$
$$xt=\sum_{i=1}^{n+1}x^i$$
两式相减得
$$(x-1)t=x^{n+1}-1$$
$$t=\frac{x^{n+1}-1}{x-1}$$
$$Q.E.D$$
:::
此时答案为
$$\sum_{i=1}^n\sum_{j=1}^{i-1}\sum_{t=0}^{n-i}\binom{n-i}{t}\binom{i-j-1}{m-n+i-2-t}2^K[a_j<a_i \land 2a_j>a_i]$$
观察到 $\sum_{t=0}^{n-i}\binom{n-i}{t}\binom{i-j-1}{m-n+i-2-t}$ 是一个范德蒙德卷积的形式，答案为 $\binom{n-j-1}{m-n+i-2}$，我们就可以再省下一只 $O(n)$，优化到 $O(n^2\log n)$。
:::info[范德蒙德卷积]
名字听起来很吓人，但原理很简单。
$$\sum_{t=0}^{n}\binom{n}{t}\binom{m}{k-t}=\binom{n+m}{k}$$
证明：考虑一共有 $n+m$ 个物品，从中选 $k$ 个。这件事情等价于在 $n$ 个物品中先选 $t$ 个，再在剩下 $m$ 个物品中选 $k-t$ 个。改变的仅仅是枚举顺序。
:::
此时答案为
$$\sum_{i=1}^n\sum_{j=1}^{i-1}\binom{n-j-1}{m-n+i-2}2^K[a_j<a_i \land 2a_j>a_i]$$
我们发现由于 $2^K$ 这一项的阻碍，此时 $i$ 和 $j$ 的贡献已经不能再往下拆了，所以我们考虑每次 $O(1)$ 求 $K$ 来把时间复杂度降到 $O(n^2)$。因为 $i$ 不变时，从小到大枚举 $j$，则此时 $a_i-a_j$ 单调不升，我们就可以用一个指针维护 $K$ 的位置，做到均摊 $O(1)$。
:::success[Code]
```cpp
#include<bits/stdc++.h>
#define For(i,j,k) for(int i=j;i<=k;i++)
#define dFor(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
#define MAXN 5005
#define Mod 998244353
int n,m,a[MAXN],b[MAXN],p[MAXN],fra[MAXN],inv[MAXN];
int Pow(int x,int y){
int ans=1;
while(y){
if(y&1){
ans=1ll*ans*x%Mod;
}
x=1ll*x*x%Mod;
y>>=1;
}
return ans;
}
void init(){
p[0]=1;fra[0]=1;
For(i,1,5000){
p[i]=1ll*p[i-1]*2%Mod;
fra[i]=1ll*fra[i-1]*i%Mod;
}
inv[5000]=Pow(fra[5000],Mod-2);
dFor(i,4999,0){
inv[i]=1ll*inv[i+1]*(i+1)%Mod;
}
}
int C(int n,int m){
if(n<0||m<0||m>n) return 0;
return 1ll*fra[n]*inv[n-m]%Mod*inv[m]%Mod;
}
int f[MAXN];
int main(){
freopen("sale11.in","r",stdin);
freopen("sale11.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
init();
int c,T;
cin>>c>>T;
while(T--){
cin>>n>>m;
For(i,1,n){
cin>>a[i];
}
sort(a+1,a+n+1);
int ans=0;
For(i,1,n){
int k=i-1;
For(j,1,i-1){
if(a[j]<a[i]&&a[j]*2>a[i]){
while(a[k]>=a[i]-a[j]){
k--;
}
ans=(ans+1ll*p[k]*C(n-j-1,m-2-n+i)%Mod)%Mod;
}
}
}
cout<<(p[n]-ans+Mod)%Mod<<endl;
}
return 0;
}
```
:::
后记：做完这道题后，我感觉组合计数题最难的就是写出一个多项式算法，这一步有时候要花很长时间，而优化则是无脑搞就行了，基本一下子就搞定了。