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

· · 题解

场上做法

先将a_i从大到小排序，下面用1表示w_i=1的物品，2表示w_i=2的物品

容易想到买不到最大当且仅当最后的两个1换成最大的没选的2更优。设i为最大的没选的2，j,k依次为倒数第二，倒数第一个1，则需满足a_i<a_j*2,a_j+a_k<a_i。

考虑钦定j,双指针出满足第一个柿子的最小的i,再枚举i,双指针出满足第二个柿子的最小的k,则可将序列分为i前面，i到j,j到k,k后面四段，记他们的长度分别为。c_1,c_2,c_3,c_4（每一段都不含i,j,k）。

注意到第3段一定为2，第4段可任取，第一段w的总和加上第二段1的个数必为m-2,故1,2段和第4段可分开讨论。

考虑1,2段，设第一段有x个2，则第一段总和为c_1+x,第二段1的个数为m-2-c_1-x,种类数即为\sum{\begin{pmatrix}c_1\\x\\\end{pmatrix} \times \begin{pmatrix}c_2\\ m-2-c_1-x\\\end{pmatrix}},范德蒙德卷积即为\begin{pmatrix}c_1+c_2\\m-2-c_1\end{pmatrix}

接下来考虑第4段，设k最大可取到now,如果没有合适的k则now=n+1,则总方案数为\sum_{i=0}^{n-now+1} 2^i+1,加1是因为后面可能没有1，但注意如果a_i=a_j则无法加1，为0。注意到其他情况下这个柿子即为2^{n-now+1}。

接下来把刚才得到的两个柿子相乘后累加即可，时间复杂度O(\sum{n^2})，少爷机上应该能过。

cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3fll

const int N=5e4+10;
const ll mod=998244353;

ll a[N],fac[N],inv[N],pw[N],n,m,T,Type;

ll qp(ll x,ll y)
{
    ll sum=1;
    while(y)
    {
        if(y&1) sum=sum*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return sum;
}

void init()
{
    fac[0]=pw[0]=1;
    for(int i=1;i<=5e4;i++)
    {
        fac[i]=fac[i-1]*i%mod;
        pw[i]=pw[i-1]*2%mod;
    }
    inv[50000]=qp(fac[50000],mod-2);
    for(int i=49999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> Type >> T;
    init();
    while(T--)
    {
        cin >> n >> m;
        for(int i=1;i<=n;i++) cin >> a[i];
        sort(a+1,a+n+1);
        for(int i=1,j=n;i<j;i++,j--) swap(a[i],a[j]);
        ll ans=0,pos=1;
        for(int i=1;i<=n;i++)
        {
            while(a[pos]>=a[i]*2) pos++;
            int now=n+1;
            for(int j=i-1;j>=pos;j--)
            {
                while(now>1&&a[i]+a[now-1]<a[j]) now--;
                ll c1=j-1,c2=i-j-1;
                if(a[j]>a[i]&&m-2-c1>=0&&c1+c2>=m-2-c1)
                {
                    ans=(ans+inv[m-2-c1]*inv[c1*2+c2-m+2]%mod*fac[c1+c2]%mod*pw[n-now+1]%mod)%mod;
                }
            }
        }
        cout << (pw[n]+mod-ans)%mod << '\n';
    }
    return 0;
}