有没有帮人做CAD的网站,做阀门的网站,成都最好的网站建设,青岛当地的做公司网站的前言
见到一道神题#xff0c;学会两个知识点… 都是数学。
min-max容斥
给出式子#xff1a; max(S)∑T⊂S(−1)∣T∣1min(T)\max(S)\sum_{T\sub S}(-1)^{|T|1}\min(T)max(S)T⊂S∑(−1)∣T∣1min(T) min(S)∑T⊂S(−1)∣T∣1max(T)\min(S)\sum_{T\sub S}(-1)^…前言
见到一道神题学会两个知识点… 都是数学。
min-max容斥
给出式子 max(S)∑T⊂S(−1)∣T∣1min(T)\max(S)\sum_{T\sub S}(-1)^{|T|1}\min(T)max(S)T⊂S∑(−1)∣T∣1min(T) min(S)∑T⊂S(−1)∣T∣1max(T)\min(S)\sum_{T\sub S}(-1)^{|T|1}\max(T)min(S)T⊂S∑(−1)∣T∣1max(T) 这里只给出第一个式子的证明第二个式子的证明较为类似。 考虑最大值 max(S)\max(S)max(S)它成为最小值产生贡献当且近当 T{max(S)}T\{\max(S)\}T{max(S)}显然只会产生一次正贡献。 而对于不是最大值的元素 x∈Sx\in Sx∈S设比它大的元素的个数为 kkk那么它成为最小值产生贡献当且近当 TTT 为前 kkk 个元素的某个子集并上 {x}\{x\}{x}那么它的系数就是 ∑i0k(ki)(−1)i\sum_{i0}^k\binom{k}{i}(-1)^ii0∑k(ik)(−1)i 二项式反演一下 ∑i0k(ki)(−1)i∑i0k(ki)(−1)i(1)k−i(1−1)k0\sum_{i0}^k\binom{k}{i}(-1)^i\sum_{i0}^k\binom{k}{i}(-1)^i(1)^{k-i}(1-1)^{k}0i0∑k(ik)(−1)ii0∑k(ik)(−1)i(1)k−i(1−1)k0 所以所有不是最大值的元素的贡献都是0。 那么最后西格玛的结果就是 max(S)\max(S)max(S)。 注意这个式子当最小值不唯一的时候依然成立min(T)\min(T)min(T) 的含义就变为了所有并列最小值的和。但是所求的最大值必须唯一 期望
这个东西对于期望依然是成立的也就是 E(max(S))∑T⊂S(−1)∣T∣E(min(T))E(\max(S))\sum_{T\sub S}(-1)^{|T|}E(\min(T))E(max(S))T⊂S∑(−1)∣T∣E(min(T)) E(min(S))∑T⊂S(−1)∣T∣E(max(T))E(\min(S))\sum_{T\sub S}(-1)^{|T|}E(\max(T))E(min(S))T⊂S∑(−1)∣T∣E(max(T)) 把定义从元素大小的求值改为期望的求值完全不影响上面的证明过程所以还是对的。
拓展kth_max
max(S)kth∑T⊂S(∣T∣−1k−1)(−1)∣T∣−kmin(T)\max(S)_{kth}\sum_{T\sub S}\binom{|T|-1}{{k-1}}(-1)^{|T|-k}\min(T)max(S)kthT⊂S∑(k−1∣T∣−1)(−1)∣T∣−kmin(T) 并不会证 还是挺好记的k1k1k1的时候就退化成正常的min-max容斥了。
离散随机变量的几何分布 离散变量值域不连续的变量。比如我们最常见的“求期望次数”值域就是自然数。 给出一个离散变量 xxx其分布概率满足 P(xk)(1−p)k−1pP(xk)(1-p)^{k-1}pP(xk)(1−p)k−1p 其中 ppp 是一个 [0,1][0,1][0,1] 的常量。 可以把 ppp 理解成做成某件事的概率那么 P(xk)P(xk)P(xk) 就是恰好用 kkk 次做成这件事的概率。
证明一
现在求这个变量的期望也就是 ∑i1∞P(xi)i\sum_{i1}^{\infty}P(xi)ii1∑∞P(xi)i 设 q1−pq1-pq1−p那么我们就要求 ∑i1∞i×qi−1×(1−q)(1−q)∑i1∞i×qi−1\sum_{i1}^{\infty}i\times q^{i-1}\times(1-q)(1-q)\sum_{i1}^{\infty}i\times q^{i-1}i1∑∞i×qi−1×(1−q)(1−q)i1∑∞i×qi−1 设 s∑i1∞i×qi−1s\sum_{i1}^{\infty}i\times q^{i-1}s∑i1∞i×qi−1则有 qs−s∑i1∞(i×qi)−∑i1∞(i×qi−1)qs-s\sum_{i1}^{\infty}(i\times q^{i})-\sum_{i1}^{\infty}(i\times q^{i-1})qs−si1∑∞(i×qi)−i1∑∞(i×qi−1) ∑i2∞((i−1)×qi−1)−∑i1∞(i×qi−1)−∑i1∞qi−1−11−q\sum_{i2}^{\infty}((i-1)\times q^{i-1})-\sum_{i1}^{\infty}(i\times q^{i-1})-\sum_{i1}^{\infty}q^{i-1}-\frac{1}{1-q}i2∑∞((i−1)×qi−1)−i1∑∞(i×qi−1)−i1∑∞qi−1−1−q1 所以 s−1(1−q)(q−1)s-\frac{1}{(1-q)(q-1)}s−(1−q)(q−1)1 所以原式就是 ∑i1∞i×qi−1×(1−q)(1−q)s−1q−11p\sum_{i1}^{\infty}i\times q^{i-1}\times(1-q)(1-q)s-\frac{1}{q-1}\frac{1}{p}i1∑∞i×qi−1×(1−q)(1−q)s−q−11p1
证明二
还有一种更加阳间的证明方法 回到现实意义www 表示做成该件事的期望次数。 考虑做一次做成或者做不成就有 wp×1(1−p)×(w1)wp \times1(1-p)\times (w1)wp×1(1−p)×(w1) 移项得 w1pw\frac{1}{p}wp1
