题目描述

给定一个无向连通图，其节点编号为 $1$ 到 $N$，其边的权值为非负整数。

试求出一条从 $1$ 号节点到 $N$ 号节点的路径，使得该路径上经过的边的权值的 XOR 和最大。

该路径可以重复经过某些节点或边，当一条边在路径中出现多次时，其权值在计算 XOR 和时也应被重复计算相应多的次数。

直接求解上述问题比较困难，于是你决定使用非完美算法。

具体来说，从 $1$ 号节点开始，以相等的概率，随机选择与当前节点相关联的某条边，并沿着这条边走到下一个节点，重复这个过程直到走到 $N$ 号节点为止，便得到一条从 $1$ 号节点到 $N$ 号节点的路径。

显然得到每条这样的路径的概率是不同的，并且每条这样的路径的 XOR 和也不一样。

现在请你求出该算法得到的路径的 XOR 和的期望值。

输入格式

第一行包含两个整数 $N$ 和 $M$，表示节点数和边数。

接下来 $M$ 行，每行包含三个整数 $u, v, w$，表示存在一条边 $(u, v)$，权值为 $w$。

图中可能存在重边或自环。

输出格式

输出包含一个实数，表示 XOR 和的期望值，结果保留三位小数。

样例

2 2
1 1 2
1 2 3

2.333

样例解释

图结构

• $N = 2$，$M = 2$
• 边 1：$(1, 1)$，权值 $2$（自环）
• 边 2：$(1, 2)$，权值 $3$

可能的路径及概率

从节点 1 出发，每一步等概率选择当前节点的出边。

情况分析

设从节点 1 出发，走到节点 2 结束。

出边情况：

• 节点 1 有 2 条出边：一条到节点 1（权值 2），一条到节点 2（权值 3）。

可能的路径：

1. 直接选择边 $(1, 2)$，一步到达节点 2。

   • 概率：$\frac{1}{2}$
   • XOR 和：$3$

2. 先选择自环 $(1, 1)$，再走到节点 2。

   • 概率：$\frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$
   • XOR 和：$2 \oplus 3 = 1$（因为 $2 \oplus 3 = 1$）

3. 选择两次自环，再走到节点 2。

   • 概率：$\frac{1}{2} \times \frac{1}{2} \times \frac{1}{2} = \frac{1}{8}$
   • XOR 和：$(2 \oplus 2) \oplus 3 = 0 \oplus 3 = 3$

4. 选择 $k$ 次自环，再走到节点 2。

   • 概率：$\left(\frac{1}{2}\right)^{k+1}$
   • XOR 和：如果 $k$ 是偶数，$2 \oplus 2 \oplus \dots \oplus 2$（$k$ 次）$\oplus 3 = 0 \oplus 3 = 3$；如果 $k$ 是奇数，$2 \oplus 2 \oplus \dots \oplus 2$（$k$ 次）$\oplus 3 = 2 \oplus 3 = 1$。

期望值计算

将路径按自环次数 $k$ 分类：

• $k$ 为偶数（包括 0）：概率和为 $\sum_{i=0}^{\infty} \left(\frac{1}{2}\right)^{2i+1} = \frac{1/2}{1 - 1/4} = \frac{2}{3}$，XOR 和均为 $3$。
• $k$ 为奇数：概率和为 $\sum_{i=0}^{\infty} \left(\frac{1}{2}\right)^{2i+2} = \frac{1/4}{1 - 1/4} = \frac{1}{3}$，XOR 和均为 $1$。

期望值 $E = \frac{2}{3} \times 3 + \frac{1}{3} \times 1 = 2 + \frac{1}{3} \approx 2.333$。

数据范围

• $2 \le N \le 100$
• $M \le 10000$
• $1 \le u, v \le N$
• $0 \le w \le 10^9$

算法分析

这是一个 随机游走 问题，需要计算从节点 1 到节点 N 的随机路径的 XOR 和期望值。

关键点

1. 路径可以重复经过边和节点，且自环和重边是允许的。
2. 随机选择：每一步从当前节点的所有出边中等概率选择一条。
3. 终止条件：到达节点 N 时停止。

思路

设 $E(u)$ 表示从节点 $u$ 出发，随机游走到达节点 N 的路径 XOR 和的期望值。

对于节点 $u$，设其出度为 $deg(u)$，出边集合为 $\{(u, v_i, w_i)\}$。

则有：

$$E(u) = \frac{1}{deg(u)} \sum_{(u,v,w) \in \text{out}(u)} \left[ w \oplus E(v) \right], \quad \text{如果 } u \neq N$$

当 $u = N$ 时，$E(N) = 0$（已经到达终点，无需再走）。

注意：这里的 $\oplus$ 是按位异或，不是算术加法，因此这不是线性方程组！不能直接这样列方程。

正确解法

由于 XOR 的按位独立性，我们可以按位处理。

设二进制第 $k$ 位（从低到高）的期望值为 $E_k(u)$，表示从 $u$ 出发，随机游走到 N 的路径 XOR 和的第 $k$ 位的期望值（取值为 0 或 1 的概率加权平均）。

由于每一位独立，我们可以对每个 $k$ 建立方程组：

对于节点 $u \neq N$：

$$E_k(u) = \frac{1}{deg(u)} \sum_{(u,v,w) \in \text{out}(u)} \left[ w_k \oplus E_k(v) \right]$$

其中 $w_k$ 是边权 $w$ 的第 $k$ 位（0 或 1），$\oplus$ 是二进制异或（即 $a \oplus b = (a + b) \mod 2$）。

因为 $w_k$ 和 $E_k(v)$ 都是 0 或 1，且 $E_k(u)$ 是实数，我们需要展开：

• 当 $w_k = 0$ 时，$0 \oplus E_k(v) = E_k(v)$
• 当 $w_k = 1$ 时，$1 \oplus E_k(v) = 1 - E_k(v)$

所以：

$$E_k(u) = \frac{1}{deg(u)} \left[ \sum_{(u,v,w): w_k=0} E_k(v) + \sum_{(u,v,w): w_k=1} (1 - E_k(v)) \right]$$

整理得：

$$deg(u) \cdot E_k(u) - \sum_{(u,v,w): w_k=0} E_k(v) + \sum_{(u,v,w): w_k=1} E_k(v) = \sum_{(u,v,w): w_k=1} 1$$

边界条件：$E_k(N) = 0$。

这样我们得到一个关于 $E_k(u)$ 的线性方程组，可以用高斯消元求解。

最后，总期望值为：

$$E = \sum_{k=0}^{K-1} 2^k \cdot E_k(1)$$

其中 $K$ 是最大位数（由于 $w \le 10^9$，取 $K=31$ 或 $32$ 即可）。

注意

• 方程组可能有唯一解、无解或无穷多解，但根据随机游走的性质应该有唯一解。
• 自环和重边需要正确处理：自环 $(u,u,w)$ 在 $deg(u)$ 中计 1，且同时出现在求和的两部分中（根据 $w_k$ 的值）。
• 图是无向连通图，但边在随机游走中是有向的（从当前节点到邻居），所以按出边处理。

复杂度

• 每个二进制位需要解一个 $N \times N$ 的线性方程组，$O(N^3)$。
• 共 $K=31$ 位，总复杂度 $O(K N^3)$，在 $N\le100$ 时可接受。