自动搬运

查看原文

来自洛谷，原作者为

	花里心爱 大好きなの！

搬运于2025-08-24 21:46:32，当前版本为作者最后更新于2019-03-20 07:51:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目链接

一般来说，遇到求期望的题时，我们都要转化期望的形式使其便于求解。

对于这道题，我们可以将它转化为一个期望dp模型。

我们先试着列一下dp式子：

设$f[i]$为当前在$i$号节点，走到$n$号节点得到的异或和的期望值。

然后对于每个$f[i]$，它可以由每个与它相邻的节点的状态转移过来。所以状态转移方程为：

$$f[i] = \sum{(f[to[p]] \operatorname{xor} val[p])/deg[i]} $$

（这里$p$表示与$i$相邻的边，$to[p]$为这条边连接的另一个点，$val[p]$为边权，$deg[i]$表示$i$的度）

然后我们就可以愉快地转移……了吗？

由于这个图不是一个$DAG$，所以通过一个点可能经过某条路径使它能够回到原点。也就是说，这里的状态是有后效性的。

看起来状态有后效性的题我们似乎并不能dp求解。

然而这里的答案（期望）显然是存在的。

于是我们设所有的$f[i]$为未知数，根据上面的式子列方程求解。

我们把原式转化一下：

$$deg[i] \times f[i] = \sum{(f[to[p]] \operatorname{xor} val[p])} $$

（其中所有的$f$为未知量）

我们需要用到高斯消元，时间复杂度为$O(n^3)$

然后我们就会发现，上面列的dp式子带一个$\operatorname{xor}$，不能直接用这个式子列方程。

于是我们就考虑期望的各种神奇的性质（好吧我们知道的关于期望的性质只有一个，那就是期望具有线性性，即$E(a+b) = E(a) + E(b)$）

那么由于异或运算的每一位互不影响，我们可以把每一位拆开。这样我们的$val[p]$就只剩下了0或1。

然后我们的$f[i]$定义就变成了：当前在$i$号节点，走到$n$号节点得到的异或和为1的期望值（也就是该位为1的概率）。

然后我们就能把$\operatorname{xor}$拆成两种情况，即：

$$deg[i] \times f[i] = \sum_{val[p]=0}{f[to[p]]}+\sum_{val[p]=1}{(1-f[to[p]])} $$$$\sum_{val[p]=0}{f[to[p]]}-\sum_{val[p]=1}{f[to[p]]} - deg[i] \times f[i] = -\sum_{val[p]=1}{1} $$

（因为$1\operatorname{xor}0=0\operatorname{xor}1=1$）

对于每一位都做一遍，最终答案为$\sum_{i=0}^{30}{2^if[1]}$

时间复杂度为$O(30n^3)$

下面放代码：

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define maxn 105
#define maxm 20005
inline int read() {
	int d=0;char ch=getchar();while(!isdigit(ch))ch=getchar();
	while(isdigit(ch)){d=d*10+ch-48;ch=getchar();}return d;
}

const double eps = 1e-9;
inline double fabs(double x) {return x < 0 ? -x : x;}
inline int sgn(double x) {return x > eps ? 1 : x < -eps ? -1 : 0;}

int n, m, u, v, w;
int head[maxn], ver[maxm], edge[maxm], nxt[maxm], tot;
int deg[maxn];

inline void add(int u, int v, int w) {
	ver[++tot] = v, edge[tot] = w, nxt[tot] = head[u], head[u] = tot;
}

double a[maxn][maxn];
double ans;

void gauss() { // 高斯消元过程
	double div;
	for(int i = 1; i <= n; ++i) {
		int m = i;
		for(int j = i+1; j <= n; ++j)
			if(sgn(fabs(a[j][i])-fabs(a[m][i])) == 1)
				m = j;
		for(int k = i; k <= n+1; ++k)
			std::swap(a[m][k], a[i][k]);
		div = a[i][i];
		for(int k = i; k <= n+1; ++k)
			a[i][k] /= div;
		for(int j = 1; j <= n; ++j) {
			if(j != i) {
				div = a[j][i];
				for(int k = i; k <= n+1; ++k)
					a[j][k] -= div*a[i][k];
			}
		}
	}
}

int main() {
	n = read(), m = read();
	for(int i = 1; i <= m; ++i) {
		u = read(), v = read(), w = read();
		if(u == v) { // 注意有自环的情况，此时只能统计一次
			++deg[u];
			add(u, v, w);
		}
		else {
			++deg[u], ++deg[v];
			add(u, v, w), add(v, u, w);
		}
	}
	for(int k = 30; k >= 0; --k) { // 对于每一位拆开来做
		memset(a, 0, sizeof(a));
		for(int i = 1; i < n; ++i) {
			a[i][i] = -deg[i];
			for(int p = head[i]; p; p = nxt[p]) {
				int v = ver[p], w = (edge[p]>>k)&1; // w为边权在2进制下的第k位
				if(w) a[i][v] -= 1, a[i][n+1] -= 1;
				else a[i][v] += 1; 
			}
		}
		a[n][n] = 1;
		gauss();
		ans += (1<<k)*a[1][n+1]; // 合并答案
	}
	printf("%.3lf", ans);
	return 0;
}