bzoj 2337: [HNOI2011]XOR和路径

2022-03-09 11:31:02

Description

Input

Output

Sample Input

Sample Output

HINT

Source

Day2

终于把这个史前遗留的坑给填了。。。

首先异或的话由位无关性，可以按位处理。。。

那么对于每一位，设f[i]表示从i出发第一次到达n且xor和为1的概率，out[i]为i的出边，那么转移就比较容易了。。。

if(w(i,j)&xxx) f[i]+=(1-f[j)/out[i];// 这条边该位为1，需要xor上0，xor和才为1

else f[i]+=f[j]/out[i];//同上。。。

但是这个有环，而且可以走重边自环，肯定是不能dp的，

但是我们发现对于每个f[i]=f[j]/out[i]+(1-f[j']/out[i])...都是一个线性方程。。。所以这是一个线性方程组。。。

然后我们由已知f[n]=1，所以可以用高斯消元解决。。。很妙啊。。。

// MADE BY QT666

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<iostream>

#include<cstring>

using namespace std;

typedef long long ll;

const int N=150;

const int M=200050;

int out[N];

int head[M],nxt[M],to[M],cnt,w[M],n,m;

double a[N][N],ans;

void gauss() {

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

    int t=i;

    while(!a[t][i]) t++;

    if(i!=t) swap(a[t],a[i]);

    double k=a[i][i];

    for(int j=i;j<=n+1;j++) a[i][j]/=k;

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

      if(j!=i&&a[j][i]) {

    k=a[j][i];

    for(int p=i;p<=n+1;p++) a[j][p]-=k*a[i][p];

      }

  }

}

void lnk(int x,int y,int z){

  to[++cnt]=y,nxt[cnt]=head[x],w[cnt]=z,head[x]=cnt;

}

int main(){

  scanf("%d%d",&n,&m);

  for(int i=1;i<=m;i++){

    int u,v,val;scanf("%d%d%d",&u,&v,&val);

    lnk(u,v,val);out[u]++;

    if(u!=v) out[v]++,lnk(v,u,val);

  }

  int gg;

  for(int k=0;k<=30;k++){

    if(k==0) gg=1;else gg=gg<<1;

    memset(a,0,sizeof(a));

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

      a[i][i]=-1.0;

      for(int j=head[i];j;j=nxt[j]){

    int y=to[j];

    if(w[j]&gg){

      a[i][y]-=1.0/out[i],a[i][n+1]-=1.0/out[i];

    }

    else a[i][y]+=1.0/out[i];

      }

    }

    a[n][n]=-1.0;gauss();ans+=a[1][n+1]*gg;

  }

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

  return 0;

}

码农公寓