这个东西是一个非常好玩的数学工具。
$$max(S)=\sum_{T\subset S}(-1)^{|T|-1}min(T)$$
$$max_k(S)=\sum_{T\subset S}(-1)^{|T|-k}C_{|T|-1}^{k-1}min(T)$$
其中$max(S),min(S),max_k(S)$分别表示集合$S$中的最大值，最小值，第$k$大值
现在我们考虑如何证明，显然我们只用证明第二个式子。
设$$max_k(S)=\sum_{T\subset S}f(|T|)\min(T)$$
其中$f(|T|)$是待定的关于$|T|$的函数。
现在我们考虑第$x+1$大的数会被统计到的次数。
$$[x==k-1]=\sum_{i=0}^xC_x^i*f(i+1)$$
用二项式反演就可以得到
$$f(x+1)=\sum_{i=0}^x(-1)^{x-i}*C_x^i*[i==k-1]$$
$$=(-1)^{x-k+1}*C_x^{k-1}$$
所以$f(x)=(-1)^{x-k}*C_{x-1}^{k-1}$
代入原来的式子就可以证明。
而且比这个原理更有用的是它对于期望也成立。
$$E[max(S)]=\sum_{T\subset S}(-1)^{|T|-1}E[min(T)]$$
$$E[max_k(S)]=\sum_{T\subset S}(-1)^{|T|-k}C_{|T|-1}^{k-1}E[min(T)]$$
其中$E[max(S)]$表示出现(?)$S$中所有元素的贡献期望
$E[min(S)]$表示出现$S$中任意一个元素的贡献期望
根据上面两个定义，不难想到$E[max_k(S)]$表示出现至少$|S|-k+1$个元素的贡献期望。
这个式子一看就很高大上。。。
现在是例题时间
先来一道最最基础的模板
题目描述：
有$n$种卡片，每一秒都有$p_i$的概率获得一张第$i$种卡片，求每张卡片都至少有一张的期望时间。
$1\leq n\leq 20,p_i\geq 0,\sum_{i=1}^np_i\leq 1$
只用把式子带进去就可以了。
不过还有一个问题，如何计算$E[min(T)]$?
开始推式子，设$P=P(x\in T)=\sum_{x\in T}p_x$
$$E[min(T)]=\sum_{k=1}^{+\infty}P(min(T)==k)*k$$
$$=P*\sum_{k=0}^{+\infty}(1-P)^k*(k+1)$$
$$=P*\frac{1}{P^2}=\frac{1}{P}$$
上面的等差数列*等比数列用错位相减法就可以算出来了。
这是一个结论，是要记住的。
#include<cstdio>
#define Rint register int
using namespace std;
int n;
double p[], ans;
inline void dfs(int dep, int tot, double sum){
if(dep == n){
if(sum > 1e-) ans += (tot & ) ? / sum : - / sum;
return;
}
dfs(dep + , tot + , sum + p[dep]);
dfs(dep + , tot, sum);
}
int main(){
while(~scanf("%d", &n)){
for(Rint i = ;i < n;i ++) scanf("%lf", p + i);
ans = ;
dfs(, , );
printf("%.6lf\n", ans);
}
}
题目描述：
在$n$个元素中，要集齐$k$种，每过一个单位时间，就会随机生成一个元素，生成第$i$个元素的概率为$\frac{p_i}{m}$，求集齐的期望时间，对$998244353$取模
$1\leq k\leq n\leq 10^3,n-k\leq 10,0\leq p_i\leq m,1\leq \sum_{i=1}^np_i=m\leq 10^4$
首先，题目里面说的是$E[min_k(S)]$，令$k=n+1-k$就可以变为$E[max_k(S)]$
但是直接求是肯定不行的，注意到这个式子与子集有关，就可以联想到dp
设$f_{i,j,k}$表示将前$i$个数作为$S$,$\sum_{x\in T}p_x=j$，$\sum_{T\subset S}(-1)^{|T|-k}C_{|T|-1}^{k-1}$的值。
按照套路，现在应该讨论$i\in T$和$i\notin T$
对于第二种，$f_{i,j,k}+=f_{i-1,j,k}$
对于第一种，$$f_{i,j,k}+=\sum_{i\in T\subset S}(-1)^{|T|-k}C_{|T|-1}^{k-1}$$
$$=\sum_{i\notin T}(-1)^{|T|-k+1}C_{|T|}^{k-1}$$
$$=\sum_{i\notin T}(-1)^{|T|-k+1}C_{|T|-1}^{k-1}+\sum_{i\notin T}(-1)^{|T|-k+1}C_{|T|-1}^{k-2}$$
$$=\sum_{i\notin T}(-1)^{|T|-k}*(-1)*C_{|T|-1}^{k-1}+\sum_{i\notin T}(-1)^{|T|-(k-1)}C_{|T|-1}^{(k-1)-1}$$
$$=f_{i-1,j-p_i,k-1}-f_{i-1,j-p_i,k}$$
所以$f_{i,j,k}=f_{i-1,j,k}+f_{i-1,j-p_i,k-1}-f_{i-1,j-p_i,k}$
还要用滚动数组将第一维滚掉。。。
至于边界，肯定不能设0，因为只有自己加减。。。
算一算就知道$f_{i,0,0}=1$
答案$$ans=m*\sum_{j=1}^m\frac{f_{n,j,k}}{j}$$
#include<cstdio>
#define Rint register int
using namespace std;
typedef long long LL;
const int N = , M = , K = , mod = ;
int n, k, m, p[N], dp[M][K], inv[M], ans;
int main(){
scanf("%d%d%d", &n, &k, &m); k = n + - k;
inv[] = ;
for(Rint i = ;i <= m;i ++) inv[i] = (LL) (mod - mod / i) * inv[mod % i] % mod;
for(Rint i = ;i <= n;i ++) scanf("%d", p + i);
dp[][] = ;
for(Rint i = ;i <= n;i ++)
for(Rint j = m;j >= p[i];j --)
for(Rint s = k;s;s --) dp[j][s] = ((LL) dp[j][s] + dp[j - p[i]][s - ] - dp[j - p[i]][s] + mod) % mod;
for(Rint i = ;i <= m;i ++) ans = (ans + (LL) dp[i][k] * inv[i]) % mod;
printf("%d\n", (LL) ans * m % mod);
}