BZOJ 2337 HNOI2011 XOR跟路径 期望DP+高斯消元

BZOJ 2337 HNOI2011 XOR和路径 期望DP+高斯消元

题目大意：给定一个无向连通图，从1出发，每次等概率沿着任意一条出边走到n为止，求路径上的边权的异或和的期望值

首先既然是位运算的问题我们的一般处理办法就是拆位，按位处理

对于每一位 令f[i]为从i节点出发到n的期望值

对于每条出边，如果这条边边权为1，那么f[x]+=f[y]/d[x] 否则f[x]+=(1-f[y])/d[x] 其中d[x]表示x的度数

特殊地，f[n]=1

由于这个图不是拓扑图，因此我们用高斯消元来解这个方程组，n个方程n个未知数(代码里写SB了- -)

解出方程后f[1]*2^k就是第k位对答案的贡献值

统计答案输出即可 注意边集不要开小 重边只要连一条

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 550
using namespace std;
struct edge{
	int x,y;
}edges[M*M];
struct abcd{
	int to,next;
}table[M*M<<1];
int head[M],tot;
int n,m,degree;
void Add(int x,int y)
{
	degree[x]++;
	table[++tot].to=y;
	table[tot].next=head[x];
	head[x]=tot;
}
int main()
{
	int i,x,y;
	cin>>n>>m;
	for(i=1;i<=m;i++)
		scanf("%d%d",&x,&y),Add(x,y),Add(y,x);
	return 0;
}