洛谷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$$

高斯消元带进去乱搞

 //minamoto

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,:;}

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while((ch=getc())>''||ch<'')

     (ch=='-')&&(flag=true);

     for(res=num;(ch=getc())<=''&&ch>='';res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 const int N=,M=2e4+;const double eps=1e-;

 int head[N],Next[M],ver[M],edge[M],tot;

 inline void add(int u,int v,int e){

     ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e;

 }

 int n,m,mx,dg[N];double res,ans[N],f[N][N];

 void build(int x){

     f[n][n]=;

     for(int u=;u<n;++u){

         f[u][u]=dg[u];

         for(int i=head[u];i;i=Next[i]){

             int v=ver[i];

             if(edge[i]&x) ++f[u][v],++f[u][n+];

             else --f[u][v];

         }

     }

 }

 void Gauss(){

     for(int i=;i<=n;++i){

         int k=i;

         for(int j=i+;j<=n;++j)

         if(fabs(f[k][i])<fabs(f[j][i])) k=j;

         if(k!=i) swap(f[i],f[k]);

         double div=f[i][i];

         for(int j=i;j<=n+;++j) f[i][j]/=div;

         for(int j=i+;j<=n;++j){

             double t=f[j][i];

             for(int k=i;k<=n+;++k)

             f[j][k]-=t*f[i][k];

         }

     }

     ans[n]=f[n][n+]/f[n][n];

     for(int i=n-;i;--i){

         for(int j=i+;j<=n;++j)

         f[i][n+]-=f[i][j]*ans[j];

         ans[i]=f[i][n+]/f[i][i];

     }

     for(int i=;i<=n;++i) for(int j=;j<=n+;++j) f[i][j]=;

 }

 int main(){

 //    freopen("testdata.in","r",stdin);

     n=read(),m=read();

     for(int i=,u,v,e;i<=m;++i){

         u=read(),v=read(),e=read();

         add(u,v,e),++dg[u];

         if(u!=v) add(v,u,e),++dg[v];

         cmax(mx,e);

     }

     for(int i=;i<=mx;i<<=)

     build(i),Gauss(),res+=ans[]*i;

     printf("%.3lf\n",res);

     return ;

 }

秒客网

洛谷P3211 [HNOI2011]XOR和路径（期望dp+高斯消元）

相关文章