题解——P3211 [HNOI2011]XOR和路径

在此之前，建议先完成本题，解决方式是类似的。

（1）转移方程

我们设置 \(f_u\) 表示节点 \(u\) 到 \(n\) 路径异或和的期望，发现这是由与 \(u\) 相连的节点转移而来的，于是就有：

\[f_u=\frac{1}{deg_u}\sum_{(u,v)\in E}(f_v \operatorname{xor} w) \]

然而我们面临两个问题。

首先，这个方程并非在 \(\operatorname{DAG}\) 上，不能靠拓扑排序等方式直接转移。其次，若使用上面例题“游走”的高斯消元，这个 \(\operatorname{xor}\) 运算也是不可做的。

（2）求解

然而你发现，期望是线性的，因此每一位上的贡献之和（按位进制转换后）就是我们的答案，因此考虑把每个权值拆开。发现每一位贡献只可能是 \(0/1\)，然后仿照上式就得到：

\[f_u=\frac{1}{deg_u}\left(\sum_{w(u,v)=0} f_v+\sum_{w(u,v)=1} (1-f_v)\right) \]

然后把式子再拆一拆，就能得到：

\[f_u\times deg_u-\sum_{w(u,v)=0} f_v+\sum_{w(u,v)=1}f_v=\sum_{w(u,v)=0}1 \]

显然套到高斯消元里就能求解了。

inline void G(int n){
	for(int i=1;i<=n;i++){
		int pos=i;
		for(int j=i+1;j<=n;j++){
			if(fabs(a[j][i])-fabs(a[pos][i])>eps)
				pos=j;
		}
		if(pos!=i) swap(a[i],a[pos]);
		db q=a[i][i];
		for(int j=i;j<=n+1;j++){
			a[i][j]/=q;
		}
		for(int j=1;j<=n;j++){
			if(i!=j){
				q=a[j][i];
				for(int k=i;k<=n+1;k++){
					a[j][k]-=q*a[i][k];
				}
			}
		}
	}
}
db ans;
int main(){
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),w=read();
		add_edge(u,v,w); deg[u]++;
		if(u!=v){
			add_edge(v,u,w); deg[v]++;
		}
	}
	for(int k=30;k>=0;k--){
		memset(a,0,sizeof(a));
		for(int u=1;u>k)&1;
				if(w){
					a[u][v]-=1.0; a[u][n+1]-=1.0;
				}
				else{
					a[u][v]+=1.0;
				}
			}
		}
		a[n][n]=1.0;
		G(n);
		ans+=(1<