【HNOI2011/bzoj2337】XOR和路径
2024-10-19 13:28:43
第二道高斯消元练习题
题意
一张无向图,从点 $1$ 出发每次随机选一条出边走,走到 $n$ 停止,求经过的所有边权异或和的期望。
$n\le 100$
题解
注意一点,异或和的期望 $≠$ 期望的异或和,因为期望是小数,但小数(在 c++ 里)不能异或,而且“期望”具体是什么期望啊。
异或有一个神奇的性质就是每个二进制位互不关联。
所以我们可以拆开考虑每一个二进制位的异或和。
拆位考虑后,还能发现一位的异或和只能是 $0$ 或 $1$,还比较好维护。
对于当前考虑的一个二进制位,设 $dp(i)$ 表示走到点 $i$ 时异或和为 $1$ 的概率,则 $1-dp(i)$ 表示异或和为 $0$ 的概率。
转移也比较显然:$$f(i) = \frac{\sum_{w=0} f(x) + \sum_{w=1} (1-f(x))}{du_i}$$
其中点 $x$ 表示与点 $i$ 直接相连的点,$w$ 表示这条连边的边权。
通过拆 $\sum$、移项得到 $$-\sum_{w=1} 1 = \sum_{w=0} f(x) - \sum_{w=1} f(x) - f(i)\times du_i$$
这就是标准高斯消元的方程了。
合并每个二进制位的答案:$ans+=2^i\times dp_i(n)$
最新文章
- SSAS:OLE DB 错误: OLE DB 或 ODBC 错误 : Login failed for user 'NT Service\MSSQLServerOLAPService'
- php 日期时间操作-可算出几天后的时间
- _BLOCK_TYPE_IS_VALID错误
- Flexigrid的API
- AngularJS学习笔记4
- [Python Study Notes]字符串处理技巧(持续更新)
- ASP.NET Core 2.1 : 十四.静态文件与访问授权、防盗链
- C# 中String.Join()方法
- 异常--finally关键字
- 一、Oracle 安装
- 深度学习原理与框架-递归神经网络-RNN_exmaple(代码) 1.rnn.BasicLSTMCell(构造基本网络) 2.tf.nn.dynamic_rnn(执行rnn网络) 3.tf.expand_dim(增加输入数据的维度) 4.tf.tile(在某个维度上按照倍数进行平铺迭代) 5.tf.squeeze(去除维度上为1的维度)
- 浅谈ESB中的DataRow、DataSet、DataBag 、DataBox
- FireFox升级后FireBug不能使用
- JavaScript学习 - 基础(八) - DOM 节点 添加/删除/修改/属性值操作
- MongoDB ReplicaSet 集群搭建
- 使用U盘安装Ubuntu系统
- [原]使用Fiddler捕获java的网络通信数据
- 3-urllib的post请求方式
- Egret3D学习笔记一 (Unity插件使用)
- npm设置仓库