BZOJ2337 [HNOI2011] XOR和路径

2018 年 03 月 14 日发布.

Description

$n$个点的无向图，从$1$号点出发每次从所有相连的边随机选一个走过去，直到$n$号点结束。求路径上所有边权异或和的期望。$n\leqslant100, m\leqslant10000$，可能有重边自环。

Solution

显然每一位是互不影响的；那每一位分别计算(这一位为1的边共经过奇数次)的概率即可。高消。

Code

#include <algorithm>
#include <cstdio>
const int N = 105;
const int M = 10005;
double A[N][N];
int n;
inline double abs(double x) { return x < 0 ? -x : x; }
double solve() {
  for (int i = 1; i <= n; ++i) {
    int j = i;
    for (int k = i + 1; k <= n; ++k) if (abs(A[k][i]) > abs(A[j][i])) j = k;
    for (int k = i; k <= n + 1; ++k) std::swap(A[i][k], A[j][k]);
    for (int k = n + 1; k >= i; --k)
      A[i][k] /= A[i][i];
    for (int j = i + 1; j <= n; ++j)
      for (int k = n + 1; k >= i; --k)
        A[j][k] -= A[i][k] * A[j][i];
  }
  for (int i = n; i; --i)
    for (int j = i - 1; j; --j)
      A[j][n + 1] -= A[j][i] * A[i][n + 1];
  return A[1][n + 1];
}
int u[M], v[M], w[M], deg[N];
int main() {
  int m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; ++i) {
    scanf("%d%d%d", &u[i], &v[i], &w[i]);
    ++deg[u[i]];
    if (u[i] != v[i]) ++deg[v[i]];
  }
  double ans = .0;
  for (int i = 0; i < 32; ++i) {
    std::fill(A[0], A[n], .0);
    for (int j = 1; j <= n; ++j) A[j][j] = 1.0;
    for (int j = 0; j < m; ++j) {
      if ((w[j] >> i) & 1) {
        // f[u] += (1 - f[v]) / d[u]
        A[u[j]][v[j]] += 1.0 / deg[u[j]];
        A[u[j]][n + 1] += 1.0 / deg[u[j]];
        if (u[j] != v[j]) {
          A[v[j]][u[j]] += 1.0 / deg[v[j]];
          A[v[j]][n + 1] += 1.0 / deg[v[j]];
        }
      } else {
        // f[u] += f[v] / d[u]
        A[u[j]][v[j]] -= 1.0 / deg[u[j]];
        if (u[j] != v[j]) A[v[j]][u[j]] -= 1.0 / deg[v[j]];
      }
    }
    std::fill(A[n], A[n + 1], .0);
    A[n][n] = 1.0;
    ans += solve() * (1 << i);
  }
  printf("%.3lf\n", ans);
  return 0;
}