BZOJ2337: [HNOI2011]XOR和路径

题解：

异或操作是每一位独立的，所以我们可以考虑每一位分开做。

假设当前正在处理第k位

那令f[i]表示从i到n 为1的概率。因为不是有向无环图（绿豆蛙的归宿），所以我们要用到高斯消元。

若有边i->j 权值为w，若w的k位为0，则f[i]+=1/du[i] * f[j]，否则f[i]+=(1-f[j])/du[i]

注意我们现在在往回走，所以度数是i的而不是j的。

然后就可以高斯消元解出来了。

装X用模方程的lcm然后发现导致误差越来越大，WA出翔

代码：

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<string>

 #define inf 1000000000

 #define maxn 200+5

 #define maxm 200000+5

 #define eps 1e-10

 #define ll long long

 #define pa pair<int,int>

 #define for0(i,n) for(int i=0;i<=(n);i++)

 #define for1(i,n) for(int i=1;i<=(n);i++)

 #define for2(i,x,y) for(int i=(x);i<=(y);i++)

 #define for3(i,x,y) for(int i=(x);i>=(y);i--)

 #define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go)

 #define for5(n,m) for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)

 #define mod 1000000007

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}

     return x*f;

 }

 int n,m,k,tot,d[maxn],head[maxn];

 struct edge{int go,next,w;}e[maxm];

 inline void add(int x,int y,int w)

 {

     e[++tot]=(edge){y,head[x],w};head[x]=tot;

 }

 double ans,a[maxn][maxn];

 inline void gauss()

 {

     //for1(i,n){for1(j,n+1)cout<<a[i][j]<<' ';cout<<endl;}

     for1(i,n)

     {

         int k=i;

         for2(j,i+,n)if(fabs(a[j][i])>fabs(a[k][i]))k=j;

         for2(j,i,n+)swap(a[i][j],a[k][j]);

         for2(j,i+,n)

         {

           double t=a[j][i]/a[i][i];

           for2(x,i,n+)a[j][x]=a[i][x]*t-a[j][x];

         }

     }

     //for1(i,n){for1(j,n+1)cout<<a[i][j]<<' ';cout<<endl;}

     for3(i,n,)

     {

         //cout<<a[i][i]<<' '<<a[i][n+1]<<"fuck"<<endl;

         for2(j,i+,n)a[i][n+]-=a[i][j]*a[j][n+];

         a[i][n+]/=a[i][i];

         //cout<<i<<' '<<a[i][n+1]<<endl;

     }

 }

 int main()

 {

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

     for1(i,m)

     {

         int x=read(),y=read(),w=read();

         if(x!=y){d[x]++;d[y]++;add(x,y,w);add(y,x,w);}

         else {d[x]++;add(x,x,w);}

     }

     for0(j,)

     {

         memset(a,,sizeof(a));

         for1(x,n-)

         {

             a[x][x]=-1.0;

             double t=1.0/(double)d[x];

             for4(i,x)

             if(e[i].w>>j&)a[x][n+]-=t,a[x][y]-=t;

             else a[x][y]+=t;

         }

         a[n][n]=1.0;

         gauss();

         //cout<<a[1][n+1]<<' '<<(1<<j)<<endl;

         ans+=a[][n+]*(<<j);

     }

     printf("%.3f\n",ans);

     return ;

 }  

2337: [HNOI2011]XOR和路径

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 515  Solved: 281
[Submit][Status]

Description