题解 P3211 【[HNOI2011]XOR和路径】
pzc2004
2020-07-27 16:20:10
# 题目分析
容易发现异或时不同的二进制位不会互相影响，所以我们可以分别考虑每一个二进制位。
对于当前考虑的二进制位，显然每条边只有0或者1两种情况。同时到达每个点时当前路径的异或和也只有0或1两种情况。我们就可以直接用高斯消元计算出经过第 $i$ 个点时当前的异或和是0和1的期望次数。计算出后只需用 $n$ 节点的异或和的期望次数乘以当前二进制位的大小即可。
令 $f_{x,0}$ 表示经过点 $x$ 时异或和为0的期望，$f_{x,1}$ 表示经过点 $x$ 时异或和为1的期望，令 $tot_x$ 表示点 $x$ 的入度，$y$ 表示到 $x$ 有边权为0的点，$z$ 表示到 $x$ 有边权为1的点。则
$$f_{x,0}=\sum\limits_{y}f_{y,0}+\sum\limits_{z}f_{z,1}$$
$$f_{x,1}=\sum\limits_{y}f_{y,1}+\sum\limits_{z}f_{z,0}$$
特别的，$f_{1,0}=\sum\limits_{y}f_{y,0}+\sum\limits_{1}f_{z,1}+1$。因为一开始就经过了节点1一次。
同时注意到达 $n$ 节点时就会停止，自环只能计算一遍。
然后只需要高斯消元就好了，复杂度$O(N^3logw)$。
``` cpp
#include<bits/stdc++.h>
using namespace std;
template<class T>inline void read(T &x)
{
x=0;
char c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c))x=x*10+(c&15),c=getchar();
}
#define N 105
#define M 10001
const double eps=0.000000000001;
int n,m,head[N],cnt,tot[N];
double a[N<<1][N<<1],ans;
struct Edge//链式前向星
{
int a,b,c;
}e[M<<1];
inline void add(int a,int b,int c)
{
e[++cnt].a=head[a],e[cnt].b=b,e[cnt].c=c,head[a]=cnt;
}
signed main()
{
read(n),read(m);
for(register int i=1,x,y,z;i<=m;i++)//加边，同时断掉n节点的所有出边
{
read(x),read(y),read(z);
if(x>y)swap(x,y);
if(x==n && y==n)continue;else if(y==n || x==y)add(x,y,z),++tot[x];else if(x!=y)add(x,y,z),add(y,x,z),++tot[x],++tot[y];
}
for(register int xi=0,y=1;xi<=30;xi++,y<<=1)//2^30>1e9
{
memset(a,0,sizeof(a));
for(register int x=1;x<=n;x++)//列方程
{
a[x][x]=a[x+n][x+n]=1;
if(x==1)a[x][n<<1|1]=1;
for(register int i=head[x];i;i=e[i].a)
{
if(e[i].c&y)
{
a[e[i].b][x+n]-=1.0/tot[x];
a[e[i].b+n][x]-=1.0/tot[x];
}
else
{
a[e[i].b][x]-=1.0/tot[x];
a[e[i].b+n][x+n]-=1.0/tot[x];
}
}
}
for(register int i=1;i<=n<<1;i++)//高斯消元
{
double x=a[i][i];
for(register int j=1;j<=(n<<1|1);j++)a[i][j]/=x;
for(register int j=1;j<=n<<1;j++)
{
if(fabs(a[j][i])<=eps || j==i)continue;
x=a[j][i];
for(register int k=1;k<=(n<<1|1);k++)a[j][k]-=x*a[i][k];
}
}
ans+=a[n<<1][n<<1|1]*y;//统计答案
}
printf("%0.3lf",ans);
return 0;
}
```