题目链接
题目解法
考虑一个常用的转化（更多用于期望）：枚举答案，将 \(=\) 变成 \(\le\) 或 \(\ge\)
\(\sum\limits_{i=1}^mi\times c(x=i)=\sum\limits_{i=1}^mc(x\ge i)\)
枚举 \(i\)，令当前序列中 \(\ge i\) 的数的个数为 \(c\)
考虑操作会给 \(c\) 带来什么变化
- 添加一个数 \(v\)
若 \(v\ge i\)，\(c+1\)，否则 \(c\) 不变 - 删除第 \(x\) 小元素
若 \(c>n-x+1\)，则 \(c-1\)，否则 \(c\) 不变
另一种理解方式是：在 \(c\le n-x+1\) 时，\(n-x+1\) 就是 \(c\) 的上界
显然需要枚举 \(1\) 操作 \(v\ge i\) 的次数 \(j\)
然后计算出 \(c\) 的值，即为 \(\max(c-(k-j),\min(n-x+1,c+j))\)
后面的 \(\min\) 时好理解的，前面的取 \(\max\) 是为了考虑最终 \(c>n-x+1\) 的情况
时间复杂度 \(O(mk\log k)\)
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
const int N=2100,P=998244353;
int n,m,k,x,a[N],C[N][N];
int qmi(int a,int b){
int res=1;
for(;b;b>>=1){
if(b&1) res=1ll*res*a%P;
a=1ll*a*a%P;
}
return res;
}
int main(){
n=read(),m=read(),k=read(),x=read();
C[0][0]=1;
F(i,1,k) F(j,0,i) C[i][j]=(!j||i==j)?1:(C[i-1][j-1]+C[i-1][j])%P;
F(i,1,n) a[i]=read();
int ans=0;
F(i,1,m){
int cnt=0;
F(j,1,n) if(a[j]>=i) cnt++;
F(j,0,k){
int c=max(cnt-(k-j),min(n+1-x,cnt+j));
// cout<<"!!!"<<i<<' '<<j<<' '<<c<<' '<<C[k][j]<<'\n';
ans=(ans+1ll*c*C[k][j]%P*qmi(m-i+1,j)%P*qmi(i-1,k-j))%P;
}
}
printf("%d\n",ans);
fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
return 0;
}