【BZOJ2337】Xor和路径（高斯消元）

时间：2023-03-10 04:18:07
【BZOJ2337】Xor和路径（高斯消元）

【BZOJ2337】Xor和路径（高斯消元）

题面

BZOJ

题解

我应该多学点套路：

对于xor之类的位运算，要想到每一位拆开算贡献

所以，对于每一位拆开来看

好了，既然是按位来算

我们就只需要计算从\(1\)号点开始

到\(n\)的路径中，路径的异或和为\(1\)的概率

显然没法算

还是一样的

考虑高斯消元

对于每一个节点\(i\)

\[f[i]=\sum_{w(u,i)=1}\frac{1-f[u]}{op[u]}+\sum_{w(u,i)=1}\frac{f[u]}{op[u]}
\]

其中，\(op\)是出度

所以可以美滋滋的高斯消元

然后计算了

复杂度\(O(n^3logw)\)

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 150

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

struct Line{int v,next,w;}e[MAX*MAX];

int h[MAX],cnt=2;

int op[MAX];

int n,m;

double g[MAX][MAX];

double f[MAX];

inline void Add(int u,int v,int w){e[cnt]=(Line){v,h[u],w};h[u]=cnt++;op[u]++;}

void Build(int l)

{

	memset(g,0,sizeof(g));

	for(int i=1;i<=n;++i)g[i][i]=1;

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

		for(int i=h[u];i;i=e[i].next)

			if(e[i].w&(1<<l))g[u][e[i].v]+=1.0/op[u],g[u][n+1]+=1.0/op[u];

			else g[u][e[i].v]-=1.0/op[u];

}

void Guess()

{

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

	{

		double bs=g[i][i];

		for(int j=1;j<=n+1;++j)g[i][j]/=bs;

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

		{

			bs=g[j][i];

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

				g[j][k]-=g[i][k]*bs;

		}

	}

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

	{

		f[i]=g[i][n+1];

		for(int j=i-1;j;--j)

			g[j][n+1]-=f[i]*g[j][i];

	}

}

int main()

{

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

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

	{

		int u=read(),v=read(),w=read();

		Add(u,v,w);

		if(u!=v)Add(v,u,w);

	}

	double ans=0;

	for(int i=0;i<=30;++i)

	{

		Build(i);Guess();

		ans+=(1<<i)*f[1];

	}

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

	return 0;

}

相关文章