2337:[HNOI2011]XOR和路径 - BZOJ

时间:2021-06-29 11:51:08

2337:[HNOI2011]XOR和路径 - BZOJ

昨天才做了一道高斯消元,一下要精度判断,一下又不要精度判断
主要是思路很重要
很容易想到每一个二进制位算一个概率,然后求和,设f[i]为走到从i走到n这一个二进制位为1的概率
f[i]:=∑{f[j]/d[i](i到j的路径这一位是0),(1-f[j])/d[i],(i到j的路径这一位是1)}(f[n]直接设为0)

 var
f:array[..,..]of extended;
d:array[..]of longint;
v,u,w:array[..]of longint;
ans:extended;
n,m:longint; procedure swap(var x,y:extended);
var
t:extended;
begin
t:=x;
x:=y;
y:=t;
end; procedure init;
var
i:longint;
begin
read(n,m);
for i:= to m do
begin
read(v[i],u[i],w[i]);
inc(d[v[i]]);
inc(d[u[i]]);
if u[i]=v[i] then dec(d[u[i]]);
end;
end; procedure work;
var
t,i,j,k:longint;
s:extended;
begin
for t:= to do
begin
for i:= to n do
for j:= to n+ do
f[i,j]:=;
for i:= to n do
f[i,i]:=;
for i:= to m do
if w[i]and(<<t)= then
begin
f[v[i],u[i]]:=f[v[i],u[i]]-/d[v[i]];
f[u[i],v[i]]:=f[u[i],v[i]]-/d[u[i]];
if u[i]=v[i] then f[v[i],v[i]]:=f[u[i],u[i]]+/d[v[i]];
end
else
begin
f[v[i],u[i]]:=f[v[i],u[i]]+/d[v[i]];
f[u[i],v[i]]:=f[u[i],v[i]]+/d[u[i]];
f[v[i],n+]:=f[v[i],n+]+/d[v[i]];
f[u[i],n+]:=f[u[i],n+]+/d[u[i]];
if v[i]=u[i] then
begin
f[u[i],v[i]]:=f[u[i],v[i]]-/d[u[i]];
f[v[i],n+]:=f[v[i],n+]-/d[v[i]];
end;
end;
for i:= to n- do
begin
for j:=i to n- do
if f[j,i]<> then break;
for k:=i to n+ do
swap(f[i,k],f[j,k]);
for j:=i+ to n- do
if abs(f[j,i])> then
begin
s:=f[j,i]/f[i,i];
f[j,i]:=;
for k:=i+ to n+ do
f[j,k]:=f[j,k]-s*f[i,k];
end;
end;
for i:=n- downto do
begin
for j:=i+ to n- do
f[i,n+]:=f[i,n+]-f[j,]*f[i,j];
f[i,]:=f[i,n+]/f[i,i];
end;
ans:=ans+f[,]*(<<t);
end;
write(ans::);
end;