ソートはしないで個数を数える．
\(1\) から \(m\) を動く確率変数 \(x\) に対して，\(x\) の期待値は \begin{align} e_{x} & = & \sum_{i = 1}^{m} \ i \cdot p_{x = i} \\ & = & \sum_{i = 1}^{m} \ p_{x \geq i}. \end{align} \(p_{x \geq i}\) は，ソートをしないで \(j \in a_{j} \geq i\) となる \(j\) の個数を数えれば求まる．
\(a\) における \(0\) の個数を \(z\) とおく．
\(for \ i \in [1,m]\) \(for \ s \in [0,z]\) を全探索する．
\(s \in [0,z] \) に対して，\(0\) を丁度 \(s\) 個 \(i\) 以上にして， 残りの \(z-s\) 個を \(i\) にする場合の数を数える．
実装:
注意は，\(z = 0\) の場合．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m ,k ;
cin >> n >> m >> k;
vll a(n); rep(i,n) { cin >> a[i]; }
Comb<mint, 2050> co;
ll z = 0;
rep(i,n){
if(a[i] == 0) z++;
}
// remark : case z = 0
mint inv = mint(1) / mint(m).pow(z);
mint c = 0;
rep1(i,m){
ll t = 0; rep(j,n) if(a[j] >= i) t++;
rep(s, z+1){
if(s + t >= n+1-k){
c += co.nCr(z,s) * mint(m+1-i).pow(s) * mint(i-1).pow(z-s);
}
}
}
cout << (c * inv).val() << endl;
return 0;
}
