min-max容斥笔记及例题
这个东西是一个非常好玩的数学工具。
$$max(S)=\sum_{T\subset S}(-1)^{|T|-1}min(T)$$
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。$$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}$$
上面的等差数列*等比数列用错位相减法就可以算出来了。
这是一个结论，是要记住的。
1 #include<cstdio> 2 #define Rint register int 3 using namespace std; 4 int n; 5 double p[20], ans; 6 inline void dfs(int dep, int tot, double sum){ 7 if(dep == n){ 8 if(sum > 1e-10) ans += (tot & 1) ? 1 / sum : -1 / sum; 9 return; 10 } 11 dfs(dep + 1, tot + 1, sum + p[dep]); 12 dfs(dep + 1, tot, sum); 13 } 14 int main(){ 15 while(~scanf("%d", &n)){ 16 for(Rint i = 0;i < n;i ++) scanf("%lf", p + i); 17 ans = 0; 18 dfs(0, 0, 0); 19 printf("%.6lf\n", ans); 20 } 21 }
题目描述：
在$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}$$
1 #include<cstdio> 2 #define Rint register int 3 using namespace std; 4 typedef long long LL; 5 const int N = 1003, M = 10003, K = 13, mod = 998244353; 6 int n, k, m, p[N], dp[M][K], inv[M], ans; 7 int main(){ 8 scanf("%d%d%d", &n, &k, &m); k = n + 1 - k; 9 inv[1] = 1; 10 for(Rint i = 2;i <= m;i ++) inv[i] = (LL) (mod - mod / i) * inv[mod % i] % mod; 11 for(Rint i = 1;i <= n;i ++) scanf("%d", p + i); 12 dp[0][0] = 1; 13 for(Rint i = 1;i <= n;i ++) 14 for(Rint j = m;j >= p[i];j --) 15 for(Rint s = k;s;s --) dp[j][s] = ((LL) dp[j][s] + dp[j - p[i]][s - 1] - dp[j - p[i]][s] + mod) % mod; 16 for(Rint i = 1;i <= m;i ++) ans = (ans + (LL) dp[i][k] * inv[i]) % mod; 17 printf("%d\n", (LL) ans * m % mod); 18 }
