标签：int ll ge need include ABC295 mod

ABC295 E

给你一个长度为 \(N\) 的序列 \(A\) 满足 \(\forall i\in [1,N],A_i\in[0,M]\)，其中 \(M\) 是一个给定的常数

执行以下两种操作

1. 不断把序列中的一个 \(0\) 换成在 \([1, M]\) 中均匀随机的一个数，直到序列中没有 \(0\)
2. 对整个序列升序排序

求序列第 \(K\) 个数的期望值，对 \(998244353\) 取模

考虑从权值的角度去做

假设 \(X\) 可以在 \([1, M]\) 内取值，为 \(i\) 的概率是 \(p_i\)， 则 \(X\) 的期望值是：

\[E(X)=\sum_{i=1}^M i \times p_i \]

发现 \(p_M\) 被加了 \(M\) 次， \(p_{M-1}\) 被加了 \(M-1\) 次，\(p_{M-2}\) 被加了 \(M-2\) 次……

一个类似后缀和之和的东西，可以写成

\[E(X)=\sum_{i=1}^{M}\sum_{j=i}^{M} p_j \]

的形式

所以也就是

\[E(X)=\sum_{i=1}^{M}P(X\ge i) \]

考虑枚举权值 \(X\)，那就只用算出对于每个 \(X\) 有 \(A_k\ge X\) 的概率即可
这相当于在操作 \(1\) 之后至少有 \(N+1-K\) 个 \(j\) 令 \(A_j\ge X\)
那二项式分布即可，减去原序列非 \(0\) 已经 \(\ge X\) 的个数，剩下的记为 \(p\)，再算出随机的数中至少有 \(p\) 个 \(\ge X\) 的概率

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>

using namespace std;
typedef long long ll;
const int N = 5555;
const ll mod = 998244353;
int a[N];
int n, m, k;
ll binom[N][N];

ll f_pow(ll a, ll k = mod - 2){
    ll base = 1;
    for(; k; k >>= 1, a = (a * a) % mod){
        if(k & 1)
            base = (base * a) % mod;
    }
    return base;
}

void add(ll &x, ll k){
	x += k;
	if(x > mod)
		x -= mod;
}

int main(){
	for(int i = 0; i < N; i++){
		binom[i][0] = 1;
		for(int j = 1; j <= i; j++)
			binom[i][j] = (binom[i-1][j-1] + binom[i-1][j]) % mod;
	}

	cin >> n >> m >> k;

    for(int i = 1; i <= n; i++){
		cin >> a[i];
	}

	ll ans = 0;

	ll invm = f_pow(m);
	for(int X = 1; X <= m; X++){
		int need = n - k + 1;
		int zeronum = 0;

		for(int j = 1; j <= n; j++){
			if(a[j] >= X)
				need--;
			if(a[j] == 0)
				zeronum++;
		}

		if(need < 0 || need > zeronum){
			add(ans, need < 0 ? 1 : 0);
			continue;
		}

		ll p = (m - X + 1) * invm % mod;
		ll q = ((1 - p) % mod + mod) % mod;
		for(int j = need; j <= zeronum; j++){
			ll k = binom[zeronum][j] * f_pow(p, j) % mod * f_pow(q, zeronum - j) % mod;
			k %= mod;
			add(ans, k);
		}
	}
	printf("%lld\n", ans % mod);
    return 0;
}

标签：int,ll,ge,need,include,ABC295,mod
From： https://www.cnblogs.com/lostintianyi/p/17280774.html