ARC139D Priority Queue 2 题解

Coffee_zzz · 2025-09-28 10:59:01 · 题解

首先把总和拆开，将 \sum\limits_{i=1}^n a_i 转化为 \sum\limits_{j=1}^m \sum\limits_{i=1}^n [a_i \ge j]。

于是考虑枚举 j，计算 \sum\limits_{i=1}^n [a_i \ge j] 的总和。

设初始时满足 a_i \ge j 的 i 的个数等于 c，操作过程中一共加了 p 个大于等于 j 的数：

• 若 c \ge n-x+1，则最终满足 a_i \ge j 的 i 的个数等于 f(c,p)=\max(n-x+1,c+p-k)；
• 若 c \lt n-x+1，则最终满足 a_i \ge j 的 i 的个数等于 f(c,p)=\min(n-x+1,c+p)。

于是可以得到：

预处理后直接计算即可。时间复杂度 \mathcal O(n+mk)。

#define int long long
const int N=2005,mod=998244353;
int n,m,k,x,a[N],pw[N][N],fac[N],infac[N],ans;
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=res*a%mod;
        b>>=1,a=a*a%mod;
    }
    return res;
}
int f(int c,int p){
    if(c>=n-x+1) return max(n-x+1,c+p-k);
    else return min(n-x+1,c+p);
}
int C(int n,int m){
    return fac[n]*infac[m]%mod*infac[n-m]%mod;
}
void solve(){
    cin>>n>>m>>k>>x;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=0;i<=m;i++){
        pw[i][0]=1;
        for(int j=1;j<=k;j++) pw[i][j]=pw[i][j-1]*i%mod;
    }
    fac[0]=infac[0]=1;
    for(int i=1;i<=k;i++) fac[i]=fac[i-1]*i%mod;
    infac[k]=ksm(fac[k],mod-2);
    for(int i=k-1;i>0;i--) infac[i]=infac[i+1]*(i+1)%mod;
    for(int j=1;j<=m;j++){
        int c=0;
        for(int i=1;i<=n;i++) if(a[i]>=j) c++;
        for(int p=0;p<=k;p++) ans+=f(c,p)*pw[m-j+1][p]%mod*pw[j-1][k-p]%mod*C(k,p),ans%=mod;
    }
    cout<<ans<<endl;
}