[HNOI2011]XOR和路径题解

运用高斯消元来$dp$.

XOR的期望比较难算。我们可以针对每一位算出期望，再加起来。
于是，我们只需要算出第i位是1的概率，在$\times 2^i$，加起来即可。
怎么$dp$？
设$dp[u]$表示从$u$到$n$点时第$i$位为1的概率。
那么考虑所有u连向的节点v，即可转移：

$dp[u]=\sum_{(u\rightarrow v)\in E\ and\ w\ bitand \ bit ==1}\frac{(1-dp[v])}{dg[u]}+\sum_{(u\rightarrow v)\in E\ and\ w\ bitand \ bit ==0}\frac{(dp[v])}{dg[u]}$

含义是，$u$到$v$概率乘上对应$v$的概率，再加起来即可。
同样的，使用高斯消元解$dp$数组。

/**
 * @Author: Mingyu Li
 * @Date:   2019-03-19T20:22:18+08:00
 * @Last modified by:   Mingyu Li
 * @Last modified time: 2019-03-19T21:23:07+08:00
 */
#include <bits/stdc++.h>
#define Go(i , x , y) for(register int i = x; i <= y; i++)
#define God(i , y , x) for(register int i = y; i >= x; i--)

const int N = 100 + 5;

// dp[u] : u点 第i位为1的概率

// dp[u] = \sum_{(u , v) & bit} (1 - dp[v]) * (1 / deg[u]) + \sum_{u , v & bit == 0} dp[v] * (1 / deg[u])

// dp[u] = (1 / deg[u]) ...
// \sum_{u , v & bit} -1   =  -deg[u]dp[u] + \sum_{(u , v) & bit} -dp[v] + \sum_{u , v & bit == 0} dp[v]
// deg[u]dp[u] = \sum_{(u , v) & bit} (1 - dp[v]) + \sum_{u , v & bit == 0} dp[v]

void chkmax(int& a , int b) {a = std::max(a, b);}
// dp[n] = 0
int n, m, mx , dg[N];
std::vector <std::pair <int,int> > G[N];
double g[N][N];

void Build(int bit) {
  memset(g , 0 , sizeof(g));
  g[n][n] = 1;
  Go(i , 1 , n-1) {
    g[i][i] = -dg[i];
    for(int j = 0; j < (int)(G[i].size()); j++) {
      int v = G[i][j].first , w = G[i][j].second;
      if(w&bit) {
        g[i][n+1]--, g[i][v]--;
      }
      else g[i][v]++;
    }
  }
}

void Gauss() {
  Go(i , 1 , n) {
    int now = i;
    Go(j , i+1 , n) if(fabs(g[now][i]) < fabs(g[j][i])) now = j;
    Go(j , 1 , n+1) std::swap(g[now][j] , g[i][j]);
    Go(j , i+1 , n+1) g[i][j] /= g[i][i];
    g[i][i] = 1;
    Go(j , i+1 , n) {
      Go(k , i+1 , n+1) {
        g[j][k] -= g[j][i] * g[i][k];
      }
      g[j][i] = 0;
    }
  }
  God(i , n , 1) {
    Go(j , i+1 , n) g[i][n+1] -= g[i][j] * g[j][n+1];
    g[i][n+1] /= g[i][i];
    g[i][i] = 1;
  }
}
int main() {
  scanf("%d%d" , &n , &m);
  Go(i , 1 , m) {
    int u , v , w;
    scanf("%d%d%d" , &u , &v , &w);
    G[u].push_back({v, w}); ++dg[u];
    if(u == v) continue;
    G[v].push_back({u , w}); ++dg[v];
    chkmax(mx , w);
    // 自环
  }

  double ans = 0;
  for(int bit = 1; bit <= mx; bit <<= 1) {
    Build(bit); Gauss(); ans += g[1][n+1] * bit;
  }

  std::cout << std::fixed << std::setprecision(3) << ans << std::endl;
  return 0;
}

# 概率期望dp, 高斯消元

[HNOI2011]XOR和路径题解

评论

分类

Your browser is out-of-date!

[HNOI2011]XOR和路径 题解

评论

分类

Your browser is out-of-date!

[HNOI2011]XOR和路径题解