AcWing 326. XOR和路径

大型补档计划

题目链接

如果整体来做，发现既有加法，也有整体异或，这样不容易搞。

考虑异或，各个位置互不干扰，按位考虑一下。

枚举每一位 \(k\)

发现如果设 \(f[u]\) 为这一位的期望结果还是不好做。

由于 每个位置只有 0 或者 1 两种操作，不妨设 \(f[u]\) 为 \(u - n\) 这一位路径为 1 的概率，最后对答案的贡献是 \(2 ^ k * f[1]\)。

然后一个按照题意的转移：\(f[u] = \frac{1}{deg[u]}(\sum_{w = 0}f[v] + \sum_{w = 1}(1 - f[v]))\)，这是一个只涉及加减运算的方程组，就能高斯消元了。

#include <cstdio>

#include <iostream>

#include <cstring>

#include <cmath>

using namespace std;

const int N = 105, M = 10005;

int n, m, d[N];

int head[N], numE = 0;

double a[N][N];

struct E{

	int next, v, w;

} e[M << 1];

void add(int u, int v, int w) {

	e[++numE] = (E) { head[u], v, w };

	head[u] = numE; d[u]++;

}

void gauss() {

	int r, c;

	for (r = 1, c = 1; c < n; c++) {

		int t = -1;

		for (int i = r; i < n; i++)

			if (fabs(a[i][c]) && (t == -1 || fabs(a[i][c]) > fabs(a[t][c]))) t = i;

		for (int i = c; i <= n; i++) swap(a[r][c], a[t][c]);

		for (int i = n; i >= c; i--) a[r][i] /= a[r][c];

 		for (int i = 1; i < n; i++) {

			if (i != r) for (int j = n; j >= c; j--) a[i][j] -= a[r][j] * a[i][c];

 		}

	    r++;

	}

}

int main() {

	scanf("%d%d", &n, &m);

	for (int i = 1, u, v, w; i <= m; i++) {

		scanf("%d%d%d", &u, &v, &w);

		add(u, v, w); if(u != v) add(v, u, w);

	}

	double ans = 0;

	for (int i = 30; ~i; i--) {

		memset(a, 0, sizeof a);

		for (int u = 1; u < n; u++) {

			a[u][u] = d[u];

			for (int j = head[u]; j; j = e[j].next) {

				int v = e[j].v;

				if (e[j].w >> i & 1) {

					a[u][n]++;

					if (v != n) a[u][v]++;

				} else {

					if (v != n) a[u][v]--;

				}

			}

		}

		gauss();

		ans += (1 << i) * a[1][n];

	}

	printf("%.3lf\n", ans);

	return 0;

}