洛谷P3211 [HNOI2011]XOR和路径（期望dp+高斯消元）
高斯消元还是一如既往的难打……板子都背不来……Kelin大佬太强啦
不知道大佬们是怎么发现可以按位考虑贡献，求出每一位是$1$的概率
然后设$f[u]$表示$u->n$的路径上这一位为$1$的概率，然后设$deg[u]$表示$u$的出度
那么$1-f[u]$就是路径上这一位为$0$的概率
然后瞎推可以得到$$f[u]=frac1{dg[u]}(sum_{w(u,v)=0}f[v]+sum_{w(u,v)=1}1-f[v])$$
$$ dg[u]f[u]=sum_{w(u,v)=0}f[v]+sum_{w(u,v)=1}1-f[v]$$
然后移个项$$dg[u]f[u]-sum_{w(u,v)=0}f[v]+sum_{w(u,v)=1}f[v]=sum_{w(u,v)=1}1$$
高斯消元带进去乱搞
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 8 char buf[1<<21],*p1=buf,*p2=buf; 9 template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} 10 inline int read(){ 11 #define num ch-'0' 12 char ch;bool flag=0;int res; 13 while((ch=getc())>'9'||ch<'0') 14 (ch=='-')&&(flag=true); 15 for(res=num;(ch=getc())<='9'&&ch>='0';res=res*10+num); 16 (flag)&&(res=-res); 17 #undef num 18 return res; 19 } 20 const int N=105,M=2e4+5;const double eps=1e-9; 21 int head[N],Next[M],ver[M],edge[M],tot; 22 inline void add(int u,int v,int e){ 23 ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e; 24 } 25 int n,m,mx,dg[N];double res,ans[N],f[N][N]; 26 void build(int x){ 27 f[n][n]=1; 28 for(int u=1;u<n;++u){ 29 f[u][u]=dg[u]; 30 for(int i=head[u];i;i=Next[i]){ 31 int v=ver[i]; 32 if(edge[i]&x) ++f[u][v],++f[u][n+1]; 33 else --f[u][v]; 34 } 35 } 36 } 37 void Gauss(){ 38 for(int i=1;i<=n;++i){ 39 int k=i; 40 for(int j=i+1;j<=n;++j) 41 if(fabs(f[k][i])<fabs(f[j][i])) k=j; 42 if(k!=i) swap(f[i],f[k]); 43 double div=f[i][i]; 44 for(int j=i;j<=n+1;++j) f[i][j]/=div; 45 for(int j=i+1;j<=n;++j){ 46 double t=f[j][i]; 47 for(int k=i;k<=n+1;++k) 48 f[j][k]-=t*f[i][k]; 49 } 50 } 51 ans[n]=f[n][n+1]/f[n][n]; 52 for(int i=n-1;i;--i){ 53 for(int j=i+1;j<=n;++j) 54 f[i][n+1]-=f[i][j]*ans[j]; 55 ans[i]=f[i][n+1]/f[i][i]; 56 } 57 for(int i=1;i<=n;++i) for(int j=1;j<=n+1;++j) f[i][j]=0; 58 } 59 int main(){ 60 // freopen("testdata.in","r",stdin); 61 n=read(),m=read(); 62 for(int i=1,u,v,e;i<=m;++i){ 63 u=read(),v=read(),e=read(); 64 add(u,v,e),++dg[u]; 65 if(u!=v) add(v,u,e),++dg[v]; 66 cmax(mx,e); 67 } 68 for(int i=1;i<=mx;i<<=1) 69 build(i),Gauss(),res+=ans[1]*i; 70 printf("%.3lf ",res); 71 return 0; 72 }