题意： 给出一个联通图，存在自环和重边，边上带权。 要求：求出从1点到n点的期望路径XOR和。
题解： XOR嘛……容易想到拆位，对于0和1的边权肯定好处理。 然后，设计状态是f(u)表示从u到n的期望XOR和。 因为f(u) = P(期望为1) * 1 + P(期望为0) * 0 即f(u)也为到n点期望为1的概率。
然后，枚举边： 若权在此位为1，f(u) += (1 - f[v]) / deg(u) 否则， f(u) += f(v) / deg(u)
然后，高斯消元，感觉精度被卡，以后中间变量全部用 long double.
void gauss(int lim) { int r, c; for(r = 1, c = 1; r <= lim && c <= lim; r++, c++) { int maxr = 0; rep(i, r, lim) if(fabs(a[i][c]) > fabs(a[maxr][c])) maxr = i; if(fabs(a[maxr][c]) < eps) { r--; continue; } swap(a[r], a[maxr]); rep(i, r + 1, lim) { if(fabs(a[i][c]) < eps) continue; long double T = a[i][c] / a[r][c]; rep(j, c, lim + 1) a[i][j] -= T * a[r][j]; } } per(i, lim, 1) { rep(j, 1, lim) if(fabs(a[i][j]) > eps) { long double T = a[i][lim + 1]; rep(k, j + 1, lim) T -= a[i][k] * f[k]; f[j] = T / a[i][j]; break; } } }