题目描述
为了打开返回现世的大门，Yopilla 需要制作开启大门的钥匙。Yopilla 所在的迷失大陆有 \(n\) 种原料，只需要集齐任意 \(k\) 种，就可以开始制作。
Yopilla 来到了迷失大陆的核心地域。每个单位时间，这片地域就会随机生成一种原料。每种原料被生成的概率是不同的，第 ii种原料被生成的概率是$ \frac{p_i}{m} $。如果 Yopilla 没有这种原料，那么就可以进行收集。
Yopilla 急于知道，他收集到任意 kk 种原料的期望时间，答案对 \(998244353\) 取模。
输入输出格式
输入格式：
第一行三个数 \(n, k, m\)。
第二行 nn 个数 \(p_1, p_2, ..., p_np1,p2,...,pn\) 。
输出格式：
输出一行。
输入输出样例
输入样例#1：
复制
3 3 31 1 1
输出样例#1：
复制
499122182
说明
对于 \(10 \%\) 的数据，\(p_1 = p_2 = ... = p_m\) 。
对于另外 \(10 \%\) 的数据，\(k = n\)。
对于 \(70 \%\) 的数据，\(n \le 100\)。
对于 \(100 \%\)的数据，\(1 \le n \le 1000\),\(1 \le k \le n, \lvert n - k \rvert \le 10，0 \le p_i \le m, \sum p = m, 1 \le m \le 100000\)
min-max反演的推广：kth min-max反演。
下面的证明转载自这位dalao的博客：。
我们考虑构造一个容斥系数\(f(x)\)，使得
\[ kthmax(S)=\sum_{T⊆S}f(|T|)min(T) \] $考虑第x+1大的元素会被统计到的贡献。 $ $这个贡献为\sum_{i=0}^{x}C_{x}^{i}f(i+1) $ 上面这个式子就是说前\(x\)大的元素选或不选都无所谓，然后必选第\(x+1\)大的元素的方案数。则
\[ [x==k-1]=\displaystyle\sum_{i=0}^{x}C_{x}^{i}f(i+1) \]二项式反演一下
\[ f(x+1)=\displaystyle\sum_{i=0}^{x}(-1)^{x-i}C_{x}^{i}[i==k-1] \]得到
\[ f(x+1)=(-1)^{x-(k-1)}C_{x}^{i-1} \] 因此\[ f(x)=(-1)^{x-k}C_{x-1}^{k-1} \]综上，
\[ kthmax(s)=\displaystyle\sum_{T \subseteq S}f(|T|)min(T)\\ =\sum_{T\subseteq S}(-1)^{|T|-k}C_{|T|-1}^{k-1}min(T) \]本题就是求第\((n-k+1)\)大的物品的出现的期望值。
我们直接套公式：
\[ kthmax(s)\displaystyle=\sum_{T\subseteq S}(-1)^{|T|-k}C_{|T|-1}^{k-1}min(T) \]显然：\(min(T)=\frac{m}{\displaystyle\sum_{i \in S}p_i}\)。
然而天真的我以为可以直接将这个值DP出来，然后做自闭了。所以遇到这种非线性的求和还是不要乱来...
然后直接贴dalao的题解（逃）：