BZOJ2337 [HNOI2011]XOR和路径 高斯消元

发布于 2017-09-26  6.13k 次阅读


[toggle hide="yes" title="题目" color=""]

BZOJ2337
BZOJ2337

[/toggle]

题目链接

一遍填以前的坑,一遍翻达哥的题表,结果就做了一堆高斯消元= =

考虑到二进制上每一位都是独立的,我们可以按位分别计算概率。

还是倒着做,设f[i]:从i点到达n点,该二进制位异或和为1的概率。

当遇到一条二进制为1的边时,意味着通过这条边,按照定义,概率应该取对立面,所以f[i]=p[i]*(1-f[j])。否则,过了这条边异或和不变,f[i]=p[i]*f[j]。

注意处理重边。期望概率题倒着做确实很方便啊。

 

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974