[P14636] [NOIP2025] 清仓甩卖 / sale 题解

· · 题解

赛时花费 3\text{h}+ 通过大样例，自造数据 1.07\text{s}，希望别死。

设确定 w 后，从大到小排序后的 \frac{a_i}{w_i} 数组为 b，不妨设 b_i 对应的就是 a_i,w_i。

观察一个不合法的情况，形如取了一个前缀到 b_x 之后，还剩 1 块钱，然后遇到几个 w_z=2 取不到，然后再遇到一个 w_y=1 刚好把 1 块钱用完（可能不存在 y）。这里，如果 a_x+a_y<a_z，那么把 x,y 换为 z 就是更优的，这时候就不合法了。

然后一个自然的想法是，枚举 x,y,z，算出方案数 \text{calc}(x,y,z)，然后省掉其中一维就可以做到 \mathcal{O}(n^2)。

这个 \text{calc}(x,y,z) 实在是非常难算！

首先可以钦定，z 为从左到右第一个满足 \text{calc}(x,y,z)\neq 0 的 z，以方便去重。

需要计算的方案数可以分成三部分：[1,z-1],[z+1,y-1],[y+1,n]，显然 w_z=2,w_x=w_y=1。

先考虑 [1,z-1] 部分，我们需要求出为 [1,z-1] 所有数确定 w 的方案数，使得按照原策略取时，恰好在 z 所在的位置剩下 1 块钱。由于 x 是除了 y 之外最后一个被取到的 w=1，x 到 z 部分的 w 必须为 2。

![](https://cdn.luogu.com.cn/upload/image_hosting/h566t0ge.png) 大概长这样（有点丑见谅），对于第一种点，其对 $m$ 的减量为 $1$ 或 $2$，对于第二种点，其对 $m$ 的减量为 $0$ 或 $1$。设对于 $[1,z]$ 而言，这两种点的数量分别为 $c_{1,z},c_{2,z}$。 把 $a_i,\frac{a_i}2$ 放一起排个序，统计前缀有多少个 $a_i$ 多少个 $\frac{a_i}2$ 即可得到 $c_{1,i},c_{2,i}$。 下面一步非常重要：**不妨设 $m$ 已经减掉了 $c_{1,z}$。** 这样两种点就本质上相同了，只需要再选任意 $m-c_{1,z}-2$ 个点即可（忽略了 $x$ 的贡献，所以是 $-2$），注意 $[x+1,z-1]$ 范围内的点只能选择贡献为 $0$，所以实际上是从 $c_{1,x-1}+c_{2,x-1}-1$（忽略 $z$）个点中选，于是方案数 $\binom{c_{1,x-1}+c_{2,x-1}-1}{m-c_{1,z}-2}$。 接下来考虑 $[z+1,y-1]$ 部分，这个部分只有 $w=2$，要求所有在其中的点都 $w=2$ 即可，没有贡献。 最后是 $[y+1,n]$ 部分，这个部分包含了跳过来的 $w=2$，这些点没有贡献，以及 $w=1,2$ 时都会在这个部分的点，这样的点可以任选 $w=1$ 或 $w=2$，每个点有 $2$ 的贡献，这样的点的数量可以通过与前文类似的方式求出，设为 $d_y$，则方案数 $2^{d_y}$。 于是得到 $\text{calc}$ 的表达式。 $\boxed{\text{calc}(x,y,z)=\binom{c_{1,x-1}+c_{2,x-1}-1}{m-c_{1,z}-2}2^{d_y}}

直接枚举满足 a_x+a_y<a_z,a_x<\frac {a_z}2<a_y 的 x,y,z 可以做到 \mathcal{O}(n^3)。注意处理相等的情况。

注意到对于一对 x,z，合法的 y 形如一个后缀，同时随着 a_x 的增加，y 的变化也是单调的，于是可以在枚举 x,z 时用一个指针维护 y 的边界，再预处理出 2^{d_y} 的后缀和，可以做到 \mathcal{O}(n^2)。

upd：赛时代码最终在 CCF 机子上通过，但是并不能在洛谷上通过。以下是经过略微卡常后在洛谷上通过的代码，最后两个点均小于 800\text{ms}，不算很极限。

:::info[code]

#include<bits/stdc++.h>
#define pb emplace_back
#define mp make_pair
#define pob pop_back
using namespace std;
typedef long long ll;
const ll maxn=100007,p=998244353;
ll n,m,cid,a[maxn],b[maxn],id[maxn],c[2][maxn],pw[maxn],ans;
ll frac[maxn],inv[maxn],s3[maxn],rev[maxn],to[maxn],nxt[maxn];
vector<pair<ll,ll> > vec;
void ups(ll &a,ll b){a=(a+b>=p)?(a+b-p):(a+b);}
void mul(ll &a,ll b){a=(a<b)?(a+p-b):(a-b);}
ll qpow(ll a,ll b){ll E=1; for(;b;b>>=1,a=a*a%p)if(b&1) E=E*a%p; return E;}
void init(void){
    pw[0]=frac[0]=1;
    for(ll i=1;i<maxn;i++) pw[i]=pw[i-1]*2%p,frac[i]=frac[i-1]*i%p;
    inv[maxn-1]=qpow(frac[maxn-1],p-2);
    for(ll i=maxn-1;i>=1;i--) inv[i-1]=inv[i]*i%p;
}
ll C(ll a,ll b){return (a<b||b<0)?0:frac[a]*inv[b]%p*inv[a-b]%p;}
ll solve(void){
    ans=0;
    for(ll i=1;i<=n;i++) b[2*i-1]=a[i],b[2*i]=2*a[i];
    for(ll i=1;i<=2*n;i++) id[i]=i;
    sort(id+1,id+1+2*n,[&](ll x,ll y){
        if(b[x]==b[y]){
            if((x&1)==(y&1)) return x<y;
            else return (bool)(x&1);
        }
        return b[x]>b[y];
    });
    for(ll i=1;i<=2*n;i++){
        c[0][i]=c[0][i-1],c[1][i]=c[1][i-1];
        c[id[i]&1][i]++;
        rev[id[i]]=i;
    }
    for(ll y=1;y<=2*n;y++){
        s3[y]=s3[y-1];
        if(id[y]%2==0) ups(s3[y],pw[c[0][2*n]-c[0][y]]);
    }
    vec.clear();
    for(ll i=1,lst=-1;i<=2*n;i++){
        if(id[i]%2==0) lst=vec.size(),vec.pb(i,id[i]);
        to[i]=lst;
    }
    for(ll i=2*n,lst=n;i>=1;i--){
        nxt[i]=lst;
        if(id[i]%2==0) lst--;
    }
    vec.pb(2*n+1,2*n);
    for(ll z=1,iz,cur,s2;z<=2*n;z++){
        if(id[z]%2==0) continue;
        iz=id[z];
        for(ll tx=to[z],x,ix,bx,cy=nxt[z];tx;tx--){
            x=vec[tx].first,ix=vec[tx].second,bx=b[ix];
            if((ix+1)/2==(iz+1)/2) continue;
            if(bx>=2*b[iz]) break;
            for(;cy<n&&b[vec[cy].second]+bx>=2*b[iz];cy++);
            cur=C(c[0][x-1]-1,m-2-c[1][z-1]);
            s2=s3[2*n],mul(s2,s3[vec[cy].first-1]);
            ups(ans,cur*(s2+1)%p);
        }
    }
    return (pw[n]-ans+p)%p;
}
int main(void){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    ll T=1; cin>>cid>>T;
    init();
    for(;T--;){
        cin>>n>>m;
        for(ll i=1;i<=n;i++) cin>>a[i];
        cout<<solve()<<"\n";
    }
    return 0;
}

:::