[BZOJ2337/Luogu3211][HNOI2011]XOR和路径(高斯消元)

发布于 2018-05-24  178 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2337/Luogu3211][HNOI2011]XOR和路径(高斯消元)

Description

给定一个无向连通图,其节点编号为 1 到 N,其边的权值为非负整数。试求出一条从 1 号节点到 N 号节点的路径,使得该路径上经过的边的权值的“XOR 和”最大。该路径可以重复经过某些节点或边,当一条边在路径中出现多次时,其权值在计算“XOR 和”时也要被重复计算相应多的次数。
直接求解上述问题比较困难,于是你决定使用非完美算法。具体来说,从 1 号节点开始,以相等的概率,随机选择与当前节点相关联的某条边,并沿这条边走到下一个节点,重复这个过程,直到走到 N 号节点为止,便得到一条从 1 号节点到 N 号节点的路径。显然得到每条这样的路径的概率是不同的并且每条这样的路径的“XOR 和”也不一样。现在请你求出该算法得到的路径的“XOR 和”的期望值。

Tag

高斯消元

解决思路

$XOR$不能直接消元计算,那么就分开每一位来算。
对于每一位,设$F[i]$表示$i$到$n$的路径异或和为$1$的概率,则有(其中$i-u$权为$0$,$i-v$权为$1$)
$$F[i]=\sum \frac{F[u]}{Degree[i]}+\sum \frac{1-F[v]}{Degree[i]}$$
另外,由于到达$n$后就停止行动,所以有$F[n]=0$。
这样就可以得到$n$个方程,大力消元就好。
最后把答案统计起来,设当前层为$bit$,则$Ans+=F[1]*2^{bit}$-

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2337/Luogu3211][HNOI2011]XOR和路径(高斯消元)


HNCJ OIer