洛谷 P3211 [HNOI2011] XOR和路径

洛谷 P3211

思路

题目是在一个地图上的期望且可以来回走就用高斯消元

因为有异或且想要用高斯消元就必须是加法，所以就考虑拆位

还是设表示的路径这一位为的概率

那么就是的路径这一位为的概率

表示的出度

再推式子的时候就可以先不用考虑来回走的问题，高消会给出答案

就可以高斯消元,最后

注意这题虽然是无向图,但是自环也不能加两次,需要特判

代码

#include<bits/stdc++.h> using namespace std; struct edge{ int v,w; };int n; double a[110][110]; double abss(double x){ if(x<0)return -x; else return x; } vector<edge>v[110];int d[110]; const double eps=1e-9; void gass(){ for(int i=1;i<=n;i++){ int h=i; for(int j=i+1;j<=n;j++){ if(abss(a[h][i])<abss(a[j][i])){ h=j; } } if(i!=h)swap(a[i],a[h]); double div=a[i][i]; for(int j=i;j<=n+1;j++)a[i][j]/=div; for(int j=i+1;j<=n;j++){ div=a[j][i]; for(int k=i;k<=(n+1);k++){ a[j][k]-=a[i][k]*div; } } } for(int i=n-1;i>=1;i--){ for(int j=i+1;j<=n+1;j++){ a[i][n+1]-=(a[i][j]*a[j][n+1]); } } } int main(){ // ios::sync_with_stdio(0); // cin.tie(0);cout.tie(0); int m;cin>>n>>m; for(int i=1;i<=m;i++){ int x,y,z;cin>>x>>y>>z; if(x!=y){ d[x]++;d[y]++; v[x].emplace_back((edge){y,z}); v[y].emplace_back((edge){x,z}); }else{ d[x]++; v[x].emplace_back((edge){y,z}); } } double ans=0; for(int k=0;k<=30;k++){ memset(a,0,sizeof(a)); for(int i=1;i<n;i++){ a[i][i]=d[i]; for(edge t:v[i]){ if(t.w&(1<<k)){ a[i][t.v]+=1; a[i][n+1]+=1; }else{ a[i][t.v]-=1; } } } a[n][n]=1; gass();ans+=(1<<k)*1.0*a[1][n+1]; } printf("%.3lf",ans); return 0; }