ARC139D Priority Queue 2 题解

首先把总和拆开，将

\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)$ 。

于是可以得到：

\sum_{i=1}^n[a_i\ge j]=\sum_{p=0}^k f(c,p)(m-j+1)^p(j-1)^{k-p}{k \choose 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;
}

ARC139D Priority Queue 2 题解

文章操作

相关推荐

评论

ARC139D Priority Queue 2 题解