P14636 [NOIP2025] 清仓甩卖题解

Coffee_zzz · 2025-11-30 18:13:31 · 题解

合法的方案数并不好求，因此考虑正难则反，计算不合法的方案数。

首先尝试刻画一下不合法的条件。显然，如果小 R 购买的糖果是按照性价比排序后的一段前缀，则他买到的糖果一定是最优的；因此，我们只需要考虑中间有一些糖果因为买不起而没有买的情况。设：

小 R 在只剩下恰好一元钱前，购买的最后一颗满足 w_i=1 的糖果为 y（其性价比为 a_y）；
小 R 在只剩下恰好一元钱后，遇到的第一颗满足 w_i=2 的糖果的编号为 x（其性价比为 \dfrac {a_x} 2）；
小 R 在只剩下恰好一元钱后，遇到的第一颗满足 w_i=1 的糖果的编号为 z（其性价比为 a_z）；特殊地，若不存在糖果 z，则认为 z=n+1，其原价 a_z 等于 0；

则小 R 会先购买糖果 y，再购买若干满足 w_i=2 的糖果，并在只剩下恰好一元钱时遇到糖果 x；由于小 R 买不起糖果 x，他只能被迫购买糖果 z。
显然，当 a_x \gt a_y+a_z 时，购买糖果 x 是比购买糖果 y 和糖果 z 更优的，这种定价方案并不能使小 R 买到的糖果的原价总和最大。于是，我们只需要计算满足 a_x \gt a_y+a_z 的方案数即可。

我们将所有糖果按照原价从大到小排序，并将此时的下标作为糖果的编号。考虑枚举 x 和 y（a_x \gt a_y \gt \dfrac{a_x}2），设 u 为最大的满足 a_u \gt \dfrac {a_x} 2 的正整数，v 为最大的满足 a_v \ge a_x-a_y 的正整数，则有下面的要求：

对于 i\in [1,x-1]，w_i 可以等于 1 或 2；
对于 i=x，w_i 需要等于 2；
对于 i\in [x+1,y-1]，w_i 可以等于 1 或 2（若 w_i=1 则它会被放在 x 前面，若 w_i=2 则它会被放在 x 后面）；
对于 i=y，w_i 需要等于 1；
对于 i\in [y+1,u]，w_i 需要等于 2，因为如果 w_i=1 的话糖果 y 就不是剩下恰好一元钱前购买的最后一颗糖果了；
对于 i\in [u+1,v]，w_i 需要等于 2，因为如果 w_i=1 的话糖果 z 就不满足 a_x \gt a_y+a_z 了；
对于 i\in [v+1,n]，w_i 可以等于 1 或 2，因为它们都可以作为糖果 z。

同时，设 [1,x-1] 中满足 w_i=2 的 i 有 f 个，[x+1,y-1] 中满足 w_i=1 的 i 有 g 个，为了使遇到糖果 x 时剩下恰好一元钱，需要满足 x-1+f+g+1=m-1（加 1 是因为还要买糖果 y）。

对于 x 前面的糖果，相当于要从 y-2 颗糖果里选 m-x-1 颗，让它们的贡献加 1，一共有 {y-2} \choose {m-x-1} 种方案；对于 x 后面的糖果，[v+1,n] 中的每颗糖果都有两种方案，方案数为 2^{n-v}；将两部分相乘，可以得到此时的方案数为 {{y-2} \choose {m-x-1}} \cdot 2^{n-v}。注意跳过 y-2 \lt m-x-1 的情况。

于是我们只需要枚举 x 和 y，利用双指针求出 v 的值，计算出方案数并相加即可。

时间复杂度 \mathcal O(\sum n^2)。

const int N=5005,mod=998244353;
int n,m,fac[N],infac[N],pw[N],ans;
ll a[N];
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=1ll*res*a%mod;
        a=1ll*a*a%mod,b>>=1;
    }
    return res;
}
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
int C(int n,int m){
    return 1ll*fac[n]*infac[m]%mod*infac[n-m]%mod;
}
void init(){
    fac[0]=infac[0]=pw[0]=1;
    for(int i=1;i<N;i++) fac[i]=1ll*fac[i-1]*i%mod;
    infac[N-1]=ksm(fac[N-1],mod-2);
    for(int i=N-2;i>=1;i--) infac[i]=1ll*infac[i+1]*(i+1)%mod;
    for(int i=1;i<N;i++) pw[i]=2*pw[i-1]%mod;
}
void solve(){
    cin>>n>>m,ans=0,a[n+1]=0;
    for(int i=1;i<=n;i++) cin>>a[i],a[i]=a[i]*2;
    sort(a+1,a+n+1);
    reverse(a+1,a+n+1);
    for(int x=1;x<min(m,n);x++){
        int y=x;
        while(y<n&&a[x]/2<a[y+1]) y++;
        int v=y;
        while(v<n&&a[x]-a[y]<=a[v+1]) v++;
        for(;a[y]<a[x];y--){
            while(v<n&&a[x]-a[y]<=a[v+1]) v++;
            int f=y-2,g=m-x-1;
            if(f<g) continue;
            add(ans,1ll*C(f,g)*pw[n-v]%mod);
        }
    }
    cout<<(pw[n]+mod-ans)%mod<<endl;
}

P14636 [NOIP2025] 清仓甩卖 题解

P14636 [NOIP2025] 清仓甩卖题解