【题解】重返现世

题目链接：重返现世

题意：

有 $n$ 个元素，每次抽取到第 $i$ 个的概率是 $\dfrac{p_i}{m}$，求抽到任意不同 $k$ 个的期望次数。

$1\le n\le 1000,1\le m\le 10^4,0\le n-k\le 10,\sum p_i=m$。

这题也太神秘了/bx/bx/bx

首先考虑 $\text{min-max}$ 容斥，则这个东西是：

$$ E(\text{kth-min}(S))=\sum_{T\subseteq S} \binom{|T|-1}{k-1}(-1)^{|T|-k} E(\max(T)) $$

回忆一下 $E(\max(T))$ 的求法，这是一个经典的 $\text{min-max}$ 容斥问题，其做法需要把 $\max$ 反演成 $\min$。所以这样仍然是不好做的。

但是我们知道，第 $k$ 小 $\iff$ 第 $n-k+1$ 大，所以我们令 $k\leftarrow n-k+1$。这样还有一个好处：当 $k\leftarrow n-k+1$，则 $k\le 11$，用上了题目的条件。

于是有：

$$ E(\text{kth-max}(S))=\sum_{T\subseteq S} \binom{|T|-1}{k-1}(-1)^{|T|-k} E(\min(T)) $$

这时候 $E(\min(T))$ 就是一个经典问题了，这个问题问的是：

第一次抽出集合 $T$ 中的元素所需要的期望次数。

抽出集合中任意一个元素的概率是 $\dfrac{\sum_{x\in T} p_x}{m}$，所以期望次数就是其倒数 $\dfrac{m}{\sum_{x\in T}p_x}$。

因此答案是：

$$ E(\text{kth-max}(S))=\sum_{T\subseteq S} \binom{|T|-1}{k-1}(-1)^{|T|-k} \dfrac{m}{\sum_{x\in T}p_x} $$

这个 $\sum_{x\in T}p_x$ 在分母上太神秘了，但是我们有 $m\le 10^4$，所以可以枚举这个和！答案变成：

$$ =\sum_{s=1}^m \dfrac{m}{s}\sum_{T\subseteq S}\binom{|T|-1}{k-1}(-1)^{|T|-k}\Big[\sum_{x\in T} p_x=s\Big] $$

考虑对每一种 $s$，算后面那个系数之和。考虑 $\text{dp}$，设 $\text{dp}_{i,j,x}$ 表示考虑前 $i$ 个元素，$\sum_{x\in T} p_x=j$，

$$ \binom{|T|-1}{x-1}(-1)^{|T|-x} $$

的和。

考虑如何转移，首先如果第 $i$ 个元素不选，则有：

$$ \text{dp}_{i,j,x}=\text{dp}_{i-1,j,x} $$

如果选择第 $i$ 个元素，则 $j\leftarrow j+p_i$。考虑上面这个系数会怎样变化：

$$ \binom{|T|-1}{x-1}(-1)^{|T|-x}=-\binom{|T|-2}{x-1}(-1)^{(|T|-1)-x}+\binom{|T|-2}{x-2}(-1)^{(|T|-1)-(x-1)} $$

也就是把杨辉三角拆开，然后把 $-1$ 的系数修正一下。于是有转移：

$$ \text{dp}_{i,j,x}=\text{dp}_{i-1,j,x}+\text{dp}_{i-1,j-p_i,x-1}-\text{dp}_{i-1,j-p_i,x} $$

直接 $\text{dp}$ 即可做到 $\mathcal{O}(nm\times (n-k))$。空间开不下，记得滚动一下。

彩蛋：推式子的时候，大力推了 kth-min 转化为 min 的系数，觉得自己巨大厉害，后来发现这和 kth-max 转变为 min 没有任何区别/tuu

//Code By CXY07
#include<bits/stdc++.h>
using namespace std;

//#define FILE
#define int long long
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define LINE() cout << "LINE = " << __LINE__ << endl
#define debug(x) cout << #x << " = " << x << endl
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define popc(x) __builtin_popcount(x)
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'

const int MAXN = 1010;
const int MAXM = 10010;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
const int mod = 998244353;
//const int G = 3;
//const int base = 131;

int n, k, m, p[MAXN], Ans;
int dp[MAXM][12], Inv[MAXM];

template<typename T> inline bool read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { a = a * 10 + (c ^ 48); c = getchar(); }
    return a *= f, true;
}

template<typename A, typename ...B>
inline bool read(A &x, B &...y) { return read(x) && read(y...); }

void modadd(int &x, int y) {
    x += y;
    if(x >= mod) x -= mod;
}

signed main () {
#ifdef FILE
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif
    read(n), read(k), read(m); Inv[1] = 1, k = n - k + 1;
    for(int i = 1; i <= n; ++i) read(p[i]);
    for(int i = 2; i <= m; ++i) 
        Inv[i] = Inv[mod % i] * (mod - mod / i) % mod;
    dp[0][0] = 1;
    for(int i = 1; i <= n; ++i)
        for(int j = m; j >= p[i]; --j)
            for(int c = k; c; --c)
                (dp[j][c] += dp[j - p[i]][c - 1] - dp[j - p[i]][c] + mod) %= mod;
    for(int p = 1; p <= m; ++p)
        Ans = (Ans + dp[p][k] * m % mod * Inv[p]) % mod;
    printf("%lld\n", Ans);
    return 0;
}