题解 BZOJ 2337 [HNOI2011]XOR和路径

题目链接
题意:给一张n个点,m条边的带环无向连通图,求1-n路径上的权值Xor起来的期望。
即无向有环图上求路径Xor期望。

因为是Xor操作,所以我们可以按二进制位分开考虑。
设考虑到了第k位,
那么现在这个图中的边权只有01
期望问题反着设一般比较好列方程,所以我们设f[i]为从i这个点走到nXor值是1的期望,显然f[n]==0
∑2^k*f[1]即为答案。
P[i]为从i点出发的走每条边的概率,应该等于1/degree[i]
我们可以列一组dp方程:
f[i]=∑P[i]*f[j](w[j,i]==0)+∑P[i]*(1-f[j])(w[j,i]==1)
w[j,i]==0则从这条边走过来Xor值不变,w[j,i]==1则从这条边走过来Xor值取反,(1-f[j])即为在jXor值是0的期望。

然后有了这些Dp方程后,发现无法Dp,因为是带环的,所以不能够以某一个顺序计算, 这时可以用高斯消元解决。把每个f[i]当作变量,n个变量,n个方程,解一下就好了。

程序实现时,注意自环度数只能算1。
代码:https://gist.github.com/zrt/041f840129ba29309c54

评论小助手

评论正在加载...

Tip: 点击下方链接切换到 Disqus 评论框可以获得邮件提醒哦
🗣️ 加载 Disqus 评论框