【HNOI2011】XOR和路径

会了高斯消元这就是个水题

首先既然是XOR,那么肯定要把边权拆成二进制然后算

那么计算点1每一位到点n的期望大小

因为每一条边都是0或者1,那么规定f[i]为当前位i点到n点的XOR和期望大小(也可理解为到n点XOR和为1的概率),d[i]为i点的度数

显而易见,对于i的每一个邻点j,若边(i,j)为0,则f[i]+f[j]/d[i],否则f[i]+(1-f[j])/d[i]。

则可以建立n元一次方程,每次解出f[1]即可。

说点什么

您将是第一位评论人!

提醒
wpDiscuz