「HNOI 2011」XOR和路径

题目大意：

按位处理，设 $f[i]$ 表示点 $i$ 到点 $n$ 的异或和是 $1$ 的期望，有

$$f[i]=\sum\limits_{j}\dfrac{p_j}{k}$$

其中 $j$ 为与 $i$ 相邻的点，$k$ 为 $i$ 发出的边的数量，如果边 $(i,j)$ 的权值的当前位是 $0$，则 $p_j=f[j]$，否则 $p_j=1-f[j]$。

高斯消元。

#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 105, M = 20005;
struct Edge {
    int v, w;
} e[M];
double a[N][N], ans;
int d[N], head[N], nxt[M], tot, n, m;

void add_edge(int u, int v, int w) {
    nxt[++tot] = head[u];
    head[u] = tot;
    e[tot] = (Edge){v, w};
}
void gauss(){
    for(int i = 1; i <= n; ++i) { //消去第i个未知数
        int mx = i;
        while (!a[mx][i]) ++mx; //找到绝对值最大的一行(本题绝对值最大就是1)
        if (mx != i) std::swap(a[i], a[mx]);
        double mul = a[i][i];
        for(int j = i; j <= n + 1; ++j) a[i][j] /= mul; //第i行整体除掉未知数i的系数
        for(int k = 1; k <= n; ++k) //消去第k行中的未知数i
            if (k != i && a[k][i]) {
                mul = a[k][i];
                for(int j = i; j <= n + 1; ++j)
                    a[k][j] -= mul * a[i][j]; //第k行整体减去第i行乘mul
            }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        ++d[u], add_edge(u, v, w);
        if (u != v) ++d[v], add_edge(v, u, w);
    }
    for (int i = 0; i < 30; ++i) {
        memset(a, 0, sizeof a);
        for (int u = 1; u < n; ++u) {
            a[u][u] = 1;
            for (int j = head[u]; j; j = nxt[j]) {
                int v = e[j].v;
                if (e[j].w & (1 << i))
                    a[u][v] += 1.0 / d[u], a[u][n+1] += 1.0 / d[u];
                else a[u][v] -= 1.0 / d[u];
            }
        }
        a[n][n] = 1;
        gauss();
        ans += a[1][n+1] * (1 << i);
    }
    printf("%.3lf\n", ans);
    return 0;
}

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