Endless Spin
2024-10-13 00:36:08
clj的题。图是假的别看
得先做这个[HAOI2015]按位或
本题如果还用[HAOI2015]按位或
的方法，2^50拜拜
但是思路一定是这样的：min-max容斥，考虑每个S的第一触及次数期望
这个题和[HAOI2015]按位或
一个不同之处是，每个区间的选择等概率随机！
这启发我们可以对许多状态一起统计！
发现，第一次触碰到S的概率和全是0的区间个数有关，符号和1的个数有关，为了方便转移还要记录最后一个1出现的位置
f[i][j][0/1]表示最后一个1的位置在i，全是0的区间个数为j，1的奇偶性是0/1
O(n^4)大力dp即可
T组数据，考虑统计答案
可以枚举最后一个1的位置pos，pos+1~n的全0的区间个数再计算
然后计算触及一次的期望次数tmp：1/[(C(n,2)+n)-cntzerointerval]
tmp*f[][][]*符号
贡献到ans里
或者更巧妙的做法是
钦定n+1位选择1
然后统计f[n+1][j][0/1]即可。当然多处理一个51，还要把0/1的状态奇偶性变过来。
总结：
抓住等概率的条件
抓住相同的S个数和方案
批量处理
喜大普奔
（置换批量处理的思想也是这样）
最新文章
- linux一些基本命令
- char*和char []
- Mongodb 和Redis 的相同点和不同点
- discuz 发布分类信息，能不能设置单版块去掉“发帖子”（默认点发帖后为自定义的默认分类信息模版）
- Moduli number system
- android 中文件加密 解密 算法实战
- python高级编程之最佳实践,描述符与属性01
- 【JUnit4.10来源分析】0导航
- 【外文翻译】使用Timer类去调度任务 ——java
- [故障公告]14:39-15:39博客站点部分负载均衡遭遇3次20G以上的流量攻击
- springboot(三)：Spring boot中Redis的使用
- C语言中变量的存储方式
- oracle 当前年到指定年的年度范围求取
- lsof -i
- 4、new一个对象的时候，初始化顺序:
- day 28 面向对象 三种特性之一 多态 鸭子类型 反射（反省）
- 变量 var &函数new
- 【转】OpenCV对图片中的RotatedRect进行填充
- Codeforces.919E.Congruence Equation(同余 费马小定理)
- python3 sort