题解：AT_arc139_d [ARC139D] Priority Queue 2

CuteC12 · 2025-12-14 08:58:22 · 题解

在北京联训期间做的这题，感谢 yhw 老师的帮助。挺困难的题（对我来说），我一个晚上才搞定它，所以尽量写得细致一点，让后人更快看懂。

题意

给定一个大小为 n 的可重集合 S，值域为 m，必须进行 k 次操作，每次随便选一个数 1 \leq v \leq m，把 v 加入 S，再删除 S 中第 x 大的数。求最后所有方案中 S 的总和的总和。范围在 2000 之内。

题目分析

这一波操作下来，集合 S 变成的样子已经很难看了，几乎很不可做。但你的目的是求和，所以可以进行如下变换，看好了：

其实很好理解，相当于你把 S 画成柱状图，你从下往上扫描，cnt([j \leq a_i]) 是每层的格子数，下面简记为 cnt(j)。

答案是这一切的总和，你可以枚举上式的 j，求这个 j 的和，再加起来。

现在考虑 cnt(j) 的变化。显然，如果这次选择的 v \geq j，cnt(j) 加一，否则不变。然后删除第 x 小的数。这个等价于如果 cnt(j)>n-x+1，cnt(j) 减一，否则不变。

体会一下这个过程。你发现，如果起始的 cnt(j) \geq n-x+1，它在每次被加之后会一直减，直到它等于 n-x+1 后，就被定住了；否则也差不多，你加加加加加，直到等于 n-x+1，也会被定住。你得到了最关键的性质：最终的 cnt(j) 只与初始值和被加的次数相关。

最终做法

先计算出最开始的 cnt(j)，然后，枚举你加一的次数 p。按照刚才讲的算出最终状态，记为 c，柿子便很简单，(m-j+1)^p(j-1)^{k-p}\binom{k}{p}c。

复杂度 O(m(n+k))。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2001,M=998244353;
int n,m,k,x,ans,a[N],fac[N],inv[N];
int fpow(int x,int y)
{
    int ans=1;
    while(y)
    {
        if(y&1) ans=ans*x%M;
        x=x*x%M;
        y>>=1;
    }
    return ans;
}
int C(int n,int m)
{
    return fac[n]*inv[m]%M*inv[n-m]%M;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>k>>x;
    for(int i=1;i<=n;i++)   cin>>a[i];
    fac[0]=fac[1]=inv[0]=inv[1]=1;
    for(int i=2;i<=k;i++)
    {
        fac[i]=fac[i-1]*i%M;
        inv[i]=(M-M/i)*inv[M%i]%M;
    }
    for(int i=2;i<=k;i++)   inv[i]=inv[i]*inv[i-1]%M;
    for(int i=1;i<=m;i++)
    {
        int c=0;
        for(int j=1;j<=n;j++)   if(a[j]>=i) c++;
        for(int j=0;j<=k;j++)
        {
            int nc;
            if(c>n-x+1) nc=max(c+j-k,n-x+1);
            else    nc=min(c+j,n-x+1);
            ans=(ans+fpow(m-i+1,j)*fpow(i-1,k-j)%M*C(k,j)%M*nc)%M;
        }
    }
    cout<<ans;
    return 0;
}

最后安利一下博客，求各位大神一个赞，qwq～～