社论：P14636 [NOIP2025] 清仓甩卖 / sale

Jordan_Pan · 2025-11-29 14:56:11 · 题解

0

初二学弟说这个题是绿。

1

依题意，单独把 w_i=1 的序列和 w_i=2 的序列提出来，他们各自的 a_i 都是递减的，于是先对 a_i 从大到小排序。

正难则反，考虑计算 caizi 的策略不优秀的方案数。

手玩样例可以发现 caizi 按照性价比选取的策略是相当优秀的，唯一可能不优的点在于，如果当前需要购买一套 w_i=2 的女装，如果 caizi 手里只有 1 元，此时取消前面选的一个 w_j=1，用 2 元购买 a_i 可能会更优。

此时 caizi 为了最大化价值，肯定会取消前面最小的 a_j，也就是前面最靠近 i 的 w_j=1。

再找到 i 后面 a_p 最大的 w_p=1（也就是后面最靠近 i 的，可能没有），那么按照 caizi 的贪心策略会选择 a_j+a_p 这两套，如果 a_j+a_p<a_i，就说明 caizi 的策略不优。

于是问题转化为：经过若干次购买，m=1 时需要购买的 w_i=2，且前后最近的两个 w_j=w_p=1 满足 a_j+a_p<a_i，这样的赋值方案数。

2

枚举 i，枚举 j，我们理清填 w 会导致 caizi 的贪心序列发生什么变化。

记 c_i 为最大的 a_{c_i}>\frac12a_i，我们按照 i,c_i 把序列分成了三段：

• 在区间 [1,i-1]，填 w=1 或者 2 都会排在 i 前面。
• 在区间 [i+1,c_i]，填 1 会排在 i 前面，填 2 会排在 i 后面。
• 在区间 [c_i+1,n]，填 1 或者 2 都会排在 i 后面。

此时一个不优秀的贪心序列应该满足哪些条件？

对 m-2 的限制分两类讨论：

• 不妨记填了 $x$ 个 $1$ 和 $y$ 个 $2$，需要满足 $x+y=i-1$ 且 $x+2y=m-2-2(i-j-1)$，解方程组得到 $x,y$，方案数为 $\binom{i-1}x$。 Upd：不对啊，如果 $j<i$ 那么 $a_j\ge a_i$，这一部分贡献为 $0$，我在干啥。
• 与前一种情况同理，不过 $[i+1,j-1]$ 相当于填 $1$ 或者 $0$，给等式两边同时加上 $j-i-1$ 仍然变为填 $2$ 或者 $1$。

3

接下来考虑 p 的贡献。

回顾上面的式子：a_j+a_p<a_i，若 i,j 固定，容易发现 p 有一个分界线，在分界线右侧就满足不等式。

而 a 序列不增，j 从小到大枚举，即 p 的分界线会单调地从右往左，双指针维护。记新的 p 为最大的 a_j+a_p\ge a_i。

此时只需要 p 前面填上 2，[p+1,n] 里出现一个 1（或者不出现也行），就可以宣告不等式成立，方案数为 2^{n-p}。可能需要特判 a_j\ge a_i。

这里有一个小问题，会不会出现 p\le c_i 的情况。事实上根据 c_i 的定义，此时 a_j>\frac12a_i 且 a_p>\frac12a_i，不满足不等式，所以不需要考虑。

4

被洛谷卡常了，吓人。

:::info[代码]

#include<bits/stdc++.h>
constexpr int rSiz=1<<21;
char rBuf[rSiz],*p1=rBuf,*p2=rBuf;
#define gc() (p1==p2&&(p2=(p1=rBuf)+fread(rBuf,1,rSiz,stdin),p1==p2)?EOF:*p1++)
template<class T>void rd(T&x){
    char ch=gc();
    for(;ch<'0'||ch>'9';ch=gc());
    for(x=0;ch>='0'&&ch<='9';ch=gc())
        x=(x<<1)+(x<<3)+(ch^48);
}
constexpr int _=5005,mod=998244353;
void Add(int &x,int y){if((x+=y)>=mod)x-=mod;}
int pw(int x,int y=mod-2){
    for(int v=1;;y>>=1,x=1ll*x*x%mod){
        if(!y)return v;
        if(y&1)v=1ll*v*x%mod;
    }
}
int fac[_],inv[_],pw2[_];
void init(int M){
    fac[0]=pw2[0]=1;
    for(int i=1;i<=M;++i)fac[i]=1ll*fac[i-1]*i%mod,pw2[i]=(pw2[i-1]<<1)%mod;
    inv[M]=pw(fac[M]);
    for(int i=M;i;--i)inv[i-1]=1ll*inv[i]*i%mod;
}
int C(int x,int y){
    if(y<0||y>x)return 0;
    return 1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int calc(int k,int i){return C(i,k-i);}
int CC,T;
int n,m,a[_],c[_],ans;
void solve(){
    rd(n),rd(m);ans=0;
    for(int i=1;i<=n;++i)rd(a[i]);
    std::sort(a+1,a+n+1,[](int x,int y){return x>y;});
    for(int i=1,j=0;i<=n;++i){
        for(;j<n&&2*a[j+1]>a[i];++j);
        c[i]=j;
    }
    for(int i=1;i<=n;++i){
        int p=n;
        for(int j=i+1;j<=c[i];++j){
            for(;p>0&&a[p]+a[j]<a[i];--p);
            int v=m-2+j-i-1;
            Add(ans,1ll*calc(v,j-2)*(pw2[n-p]-(a[j]>=a[i]))%mod);
        }
    }
    ans=(pw2[n]-ans+mod)%mod;
    printf("%d\n",ans);
}
#define fio(x) freopen(x ".in","r",stdin);freopen(x ".out","w",stdout);
int main(){
    // fio("sale");
    init(5000);
    rd(CC),rd(T);
    for(;T;--T)solve();
}
:::