2337: [HNOI2011]XOR和路径

题意：一个边权无向连通图，每次等概率走向相连的点，求1到n的边权期望异或和

这道题和之前做过的高斯消元解方程组DP的题目不一样的是要求期望异或和，期望之间不能异或所以不能直接求

发现每个二进制位是独立的，我们可以一位一位考虑，设当前考虑第i位

\(f[u]\)表示从u到n异或和为1的概率，

可以同乘\(degree_u\)来减少精度损失

为什么要逆推呢？

我们需要知道异或和不为1的概率\(1-f(i)\)

如果正推的话，\(1-f(i)\)代表的不仅从1到i异或和不为1的概率，还包含了从1不走到i的概率，无法转移

对于逆推，一定是从i走到n，\(1-f(i)\)还是走到n，就没有这样的问题

注意自环存在！这时候只能连一次边并且度数只能加1

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

using namespace std;

typedef unsigned long long ll;

const int N=105, P=1e9+7;

const double eps=1e-8;

inline int read() {

	char c=getchar(); int x=0, f=1;

	while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}

	while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}

	return x*f;

}

int n, m, u, v, w, Max;

struct edge{int v, w, ne;}e[N*N<<1];

int cnt=1, h[N], de[N];

inline void ins(int u, int v, int w) { e[++cnt]=(edge){v, w, h[u]}; h[u]=cnt; }

double a[N][N];

void build(int now) {

	memset(a, 0, sizeof(a));

	a[n][n]=1; a[n][n+1]=0;

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

		a[u][u] = de[u];

		for(int i=h[u];i;i=e[i].ne) {

			int v=e[i].v;

			if(e[i].w & now) a[u][v]++, a[u][n+1]++;

			else a[u][v]--;

		}

	}

	//for(int i=1; i<=n; i++) for(int j=1; j<=n+1; j++) printf("%lf%c",a[i][j],j==n+1?'\n':' ');

}

void gauss() {

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

		int r=i;

		for(int j=i; j<=n; j++) if(abs(a[j][i])>abs(a[r][i])) r=j;

		if(r!=i) for(int j=1; j<=n+1; j++) swap(a[r][j], a[i][j]);

		for(int k=i+1; k<=n; k++) if(abs(a[k][i]) > eps) {

			double t = a[k][i]/a[i][i];

			for(int j=i; j<=n+1; j++) a[k][j] -= t*a[i][j];

		}

	}

	for(int i=n; i>=1; i--) {

		for(int j=n; j>i; j--) a[i][n+1] -= a[i][j]*a[j][n+1];

		a[i][n+1] /= a[i][i];

	}

}

int main() {

	freopen("in","r",stdin);

	n=read(); m=read();

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

		u=read(); v=read(); w=read(); Max=max(Max, w);

		de[u]++;

		ins(u, v, w); if(u!=v) ins(v, u, w), de[v]++;

	}

	double ans=0;

	for(int now=1; now<=Max; now<<=1)

		build(now), gauss(), ans += now*a[1][n+1];

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

}