E

首先，一个错误的思路。

考虑 \(A_k\) 是原先 \(A_i\neq 0\) 中的一个，还是 \(A_i\) 转化成 \(0\) 后的一个。前者没有任何问题，但是后者会重复 \(\rightarrow\) 错误！

正确的思路：

注意到 \(\text{Answer}=\displaystyle \sum^{m}_{i=1} \ ([\text{possibility of }A_k=i]\times i)=\sum^{m}_{i=1}\ [\text{possibility of}A_k\ge i]\)。

这个证明是很显然的。

再次注意到 \(N,M\le 2000\rightarrow\) 可以用 \(O(NM)\)！

Spoiler

考虑枚举 \(i\)，然后 \(O(N)\) 计算 \(\sum\) 后面的答案。其实，\([\text{possibility of}A_k\ge i]\) 就等于 \([\text{possibility of at least } N-k+1 \text{ integers that are } \ge i]\)。这样，就很简单了。

Code

#include <bits/stdc++.h>

using namespace std;

#define de(x) cout<<#x<<"="<<x<<endl

#define int long long

const int N = 2e3+3;
const int mod = 998244353;

int inv(int a){
	return a==1?1:(mod-1ll*inv(mod%a)*(mod/a)%mod);
}

int n,m,k;
int a[N];
int binom[N][N];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>m>>k;
    for (int i=0; i<n; i++){
        cin>>a[i];
    }
    binom[0][0]=1;
    for (int i=1; i<N; i++){
        binom[i][0]=1;
        for (int j=1; j<=i; j++){
            binom[i][j]=binom[i-1][j]+binom[i-1][j-1];
            binom[i][j]%=mod;
        }
    }
    int zero=0;
    for (int i=0; i<n; i++){
        zero+=(a[i]==0);
    }
    int ans=0;
    for (int i=1; i<=m; i++){
        // count the number of ways such that a_k>=i
        int nd=n-k+1;
        for (int j=0; j<n; j++){
            if (a[j]>=i){
                nd--;
            }
        }
        if (nd<0){
            ans++;
            ans%=mod;
            continue;
        }
        if (nd>zero){
            continue;
        }
        int pos=(m-i+1)*inv(m)%mod;
        int pos2=(1-pos+mod)%mod;
        vector<int> v1(zero+1),v2(zero+1);
        v1[0]=1;
        v2[0]=1;
        for (int j=0; j<zero; j++){
            v1[j+1]=v1[j]*pos;
            v1[j+1]%=mod;
            v2[j+1]=v2[j]*pos2;
            v2[j+1]%=mod;
        }
        for (int j=nd; j<=zero; j++){
            ans+=v1[j]*v2[zero-j]%mod*binom[zero][j]%mod;
            ans%=mod;
        }
    }
    cout<<ans<<endl;
    return 0;
}

526互联

ABC 295

E