NOIP2025 T2 题解

20_200 · 2025-11-30 10:44:54 · 题解

场上心态崩溃，无法 debug，被这题送退役了。

这种题，要计数，显然需要先会判定一个方案是否合法。而且一般合法条件非常强，不然没办法计数。以下讨论一个方案不合法的条件。

首先可以将 a 数组降序排序。以下所有价格序列默认递减。

考虑把原序列 a 拆成两个序列 A,B，分别表示新定价为 2 和 1 的。为了减少特判，假定 A 和 B 后面都有无限多个 0，这样不会出现 m 元钱用不完的情况。

容易证明，不管是性价比策略，还是实际最优策略，A,B 中购买的都是一段前缀。

设 p,q 分别是 A,B 序列中购买的最后一个，则有 2p+q=m。

如果按照性价比排序的策略买，则应该满足 A_{p+1}\lt 2B_{q-1},A_p\ge 2B_{q+1}，即 p,q 都不会因为下一个性价比更高而导致策略改变。

如果是原价最大的策略，那么应该是 f(p)=\sum_{i=1}^pA_i+\sum_{i=1}^qB_i,ans=f(p)_{\min}。

当 p'\gets p+1 时，q'\gets q-2，f(p')\gets f(p)+A_{p+1}-B_q-B_{q-1} 。由于 A,B 都是递减的，g(p)=A_{p+1}-B_q-B_{q-1} 也递减，故 f(p) 取最大值等价于满足 g(p-1)\ge 0 且 g(p)\le 0。

所以，一种方案不合法，即按照性价比策略取不到最优解，等价于以下不等式：

由于 $A,B$ 递减，所以 $A_p>A_{p+1},B_{q-1}>B_q>B_{q+1}>B_{q+2}$。如果该条件满足，则第二个不等式成立，那么第四个一定不成立，所以第三个不等式必须要成立。而如果第三个不等式成立，则第二个不等式也一定成立。所以实际上只有第一个和第三个不等式是有用的，条件等价于 $B_{q-1}+B_q\lt A_{p+1}\lt 2B_{q-1}

现在可以开始计数了，暴力枚举 B_q,B_{q-1},A_{p+1} 在原序列 a 中对应的下标 i,j,k 以及 p 的值，则 q 可以直接确定，且 i>j>k， a_i+a_j<a_k<2a_j。方案数可以直接组合数，即为 \binom{k-1}{p}\binom{j-k-1}{q-2-(k-p-1)}2^{n-i}。

代入 2p+q=m 化简一下，\sum\binom{k-1}{p}\binom{j-k-1}{q-2-(k-p-1)}=\sum\binom{k-1}{p}\binom{j-k-1}{m-k-1-p}=\binom{j-2}{m-k-1}。所以不需要枚举 p。

而注意到 i 的贡献只有 2^{n-i} 一项，且对于固定的 j ，k 对应的 i 是一个单调递增的后缀，所以可以用双指针解决。

有一个重要的细节，i 需要枚举到 n+1，因为需要考虑 q 取到 B 后面补的 0 的情况。贡献系数应该为 2^{\max(n-i,0)}。

最后答案即为 2^n 减去不合法的方案数。

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

~去掉头文件和组合数预处理总共就十行，不知道场上在调什么鬼。~

::::success[代码]

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<ll,ll>
#define ve vector<ll>
#define fi first
#define se second
#define pb push_back
#define mid (l+r>>1)
#define lx (x<<1)
#define rx (x<<1|1)
using namespace std;
const ll N=5008,P=998244353;
ll T,n,m,ans,a[N],pw[N],c[N][N];
void init(){
    pw[0]=1;
    for(ll i=1;i<N;i++)pw[i]=pw[i-1]*2%P;
    for(ll i=0;i<N;i++)
        for(ll j=0;j<=i;j++)
            c[i][j]=(j?c[i-1][j]+c[i-1][j-1]:1)%P;
}
void slv(){
    cin>>n>>m,a[n+1]=ans=0;
    for(ll i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1,greater<ll>());
    for(ll j=2;j<=n;j++){
        ll p=j+1,s=0;
        for(ll i=j+1;i<=n+1;i++)
            (s+=pw[max(n-i,0ll)])%=P;
        for(ll k=max(m-j,0ll)+1;k<min(j,m);k++)
            if(a[k]<2*a[j]){
                while(p<=n+1&&a[p]>=a[k]-a[j])
                    (s-=pw[max(n-p,0ll)])%=P,p++;
                (ans+=c[j-2][m-k-1]*s)%=P;
            }
    }
    cout<<(pw[n]-ans+P)%P<<'\n';
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>T>>T,init();
    while(T--)slv();
    return 0;
}

::::