题目链接
题意:给一张n个点,m条边的带环无向连通图,求1-n
路径上的权值Xor起来的期望。
即无向有环图上求路径Xor期望。
因为是Xor操作,所以我们可以按二进制位分开考虑。
设考虑到了第k
位,
那么现在这个图中的边权只有0
或1
。
期望问题反着设一般比较好列方程,所以我们设f[i]
为从i这个点走到n
Xor值是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])
即为在j
Xor值是0的期望。
然后有了这些Dp方程后,发现无法Dp,因为是带环的,所以不能够以某一个顺序计算, 这时可以用高斯消元解决。把每个f[i]
当作变量,n
个变量,n
个方程,解一下就好了。
程序实现时,注意自环度数只能算1。
代码:https://gist.github.com/zrt/041f840129ba29309c54