[总结] Min-Max容斥学习笔记
min-max 容斥
给定集合 \(S\) ,设 \(\max(S)\) 为 \(S\) 中的最大值,\(\min(S)\) 为 \(S\) 中的最小值,则:
\[\max(S)=\sum_{T\in S}(-1)^{|T|-1}\min(T)\]
这个东西叫 min-max容斥。
证明可以拿二项式反演证
例题
hdu4336 Card Collector
有 \(n\) 种卡片,每一秒都有 \(P_i\) 的概率获得一张第 \(i\) 种卡片,求每张卡片都至少有一张的期望时间。
记 \(\max(S)\) 为 \(S\) 中最后获得的那种卡片第一次获得的期望时间, \(\min(S)\) 为 \(S\) 中第一个获得的那种卡片第一次获得的期望时间,仍然满足:
\[\max(S)=\sum_{T\in S}(-1)^{|T|-1}\min(T)\]
又因为 \(\min(T)=\frac 1{\sum\limits_{i\in T}P_i}\)
直接算就行了。
HAOI2015 按位或
记 \(\max(S)\) 为 \(S\) 中最后被或到的元素第一次被或到的期望时间, \(\min(S)\) 为 \(S\) 中第一个被或到的元素第一次被或到的期望时间,还是那个式子:
\[\max(S)=\sum_{T\in S}(-1)^{|T|-1}\min(T)\]
但是这里互相不是独立的,怎么算 \(\min(T)\) 呢
\[\min(T)=\frac 1{\sum_{S\cap T\ne \emptyset} P_S}\]
也就是所有与 \(T\) 有交的集合 \(S\) 的概率之和
正难则反,求出所有与 \(T\) 交集为空的集合 \(S'\) 的概率之和,则它们的补集就是与 \(T\) 有交的集合 \(S\)。
求出 \(S'\) 的概率之和拿 \(1\) 再减掉就好啦。这个东西拿 \(FWT\) 或者 \(FMT\) 都阔以优化一哈。
推广 kth min-max 容斥
\[\max(S,k)=\sum_{T\in S}(-1)^{|T|-k}\cdot C(|T|-1,k-1)\cdot \min(T)\]
其中 \(\max(S,k)\) 表示 \(S\) 集合中第 \(k\) 大的元素。
例题
重返现世
全网就这一道 kth min-max 容斥orz
首先式子还是那个式子,但是这里的 \(n\) 是 \(1000\),不能 \(2^n\) 枚举子集。考虑递推系数求解。
有 \(\min(T)=\frac m{sum(T)}\),其中 \(sum(T)=\sum\limits_{i\in T}p_i\)
设 \(f[i][j][x]\) 表示前 \(i\) 个元素,选的 \(sum(T)\) 为 \(j\),且将 \(k=x\) 代入式子后前面那一大串系数的值。
这样设状态的原因就是把等价类划分到了一起,并且容易递推。
由组合数的性质 \(C_n^m=C_n^{n-m},C_n^m=C_{n-1}^m+C_{n-1}^{m-1}\)
可以列出 \(DP\) 转移 \(f[i][j][x]=f[i-1][j][x]+(f[i-1][j-p[i]][x-1]-f[i-1][j-p[i]][x])\)
可以拿组合数证。
最新文章
- 进击的Python【第四章】:Python的高级应用(一)
- wex5 实战 wex5与js的组件关系与执行顺序(父子与先后)
- 出现( linker command failed with exit code 1)错误总结 (转)
- MongoDB 安装(Window/Linux)
- adobe photoshop cc 2014 安装失败 解决办法之一
- eclipse+tomcat开发web项目
- POJ-2481 Cows (线段树单点更新)
- Mysql 应该选择什么引擎
- svnserve: E000098: 不能绑定服务器套接字: 地址已在使用
- Javscript的函数链式调用基础篇
- 利用反射获取数据列+emit生成属性+单例模式
- 2017 ACM-ICPC西安网赛B-Coin
- Infopath 2013 通过UserProfileService读取AD用户信息
- Scala进阶之路-Spark本地模式搭建
- rt.jar sun package
- 胖子哥的大数据之路(11)-我看Intel&;&;Cloudera的合作
- 未能加载文件或程序集“Microsoft.SqlServer.Management.Sdk.Sfc, Version=11.0.0.0, Culture=neutral, PublicKeyToken=89845dcd8080cc91”或它的某一个依赖项。系统找不到指定的文件。
- Appium安卓与环境配置
- cocos2dx 安卓真机调试问题汇总
- django 定制管理页面外观 模板文件不生效的解决方法