注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ2337】【HNOI2011】【Xor和路径】  

2014-04-07 08:59:37|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
      话说这道题是 Xor/和路径 还是 Xor和/路径咩?
      祝wsh君的烧早点好起来~0w0,虐题依旧如日常。
      题目大意:从起点出发,每一次从相邻的点以等概率选择一个走过去,然后走到终点停止,然后求这样的路径的长度和的期望值。
      面对期望...咱一般能用的东西就是全期望公式。然后咱来复习一下全期望公式...全期望公式实际上就是这样的:要乃们算一个东西的期望值,然后假设咱们可以把这个东西拆成互不相交的几个事件,然后咱们能算出这些事件的期望Ei以及其发生的概率pi,那么咱们算的东西的期望就是 ∑pi*Ei。

      然后咱每次都只会用这个东西来求.....这题然后就不会做了= =。
      然后咱又是厚颜无耻地看题解党.... 题解君1 题解君2
      然后咱是非常傻叉的想要了解这个分析的来龙去脉...所以又对着这些题解的那些数学yy了半天...(不过也是这样咱非常喜欢埃勒里奎因)

      首先要知道一点...这里的xor运算不会产生进位操作,所以每一位都是独立的,所以咱们可以一位位做,求出每一位的期望(这个Xor的思想其实经常碰见的,比如spoj的那一道xor标号的...不过咱脑洞大竟然没想到233)
      之前咱的障碍在于用全期望公式的时候,无论怎么分类实际上都是非常难求的,但是化成进制的话就可能好做多了...因为进制最后的答案只有可能有2个,0或者1,然后假设咱们能统计出0或者1的道路的比例,也许就能够算了。但是...这里的状态数实际上是无限的233.....
      状态数是无数的咱没做过啊 T T
      但是无数有时候也是可以做的... 

(ps:以下的一些证明还没想清...,错误应该是非常多的)

      咱们设 x[i]  表示从点i走到终点n的期望异或和。这个东西很多题解君们都是直接讲了...但是咱是蒟蒻= =所以理解不能。这里写下咱的理解,也许希望能帮助到那些同样困惑在这里的朋友们吧。

      首先咱们回忆一下全期望公式...然后咱们开始下面的思路...实际上所有的路径都可以表示成从点i开始,在点1~N-1中随机走,直到某次走到一个N的邻接点,然后从这个点走向了N,即咱们可以把所有的路径按从哪个点走向N来划分。咱们只需要分类计算不同的路径的期望,然后用全期望公式即可。每一个事件发生的概率就是 1/cnt[j](cnt[j]表示点j的度数)
      咱们上面设了 x[i] 表示从点i走到点N的期望异或和。咱们尝试表示一下它:

      x[i]=∑∑Wuv*∏1/cnt[u],

      其中第二个∑不是加法而是xor。∑Wuv*∏1/cnt[u] 表示的就是一条从i到N的路径及其概率的乘积(这个很显然就是一个全期望公式)

      但是这样的路径有很多条...咱们不能够直接枚举出来。但是咱们发现...咱们又可以把这些路径按照这条路径是从哪个点到达i的分类!设与 i 相邻的点集合为Vi(不包括点N),那么发现,到达Vi的路径的集合加上一条Vi到i的边,就可以构成到达i的路径,即Vi的每一条路径都对应着i的一条路径!在这个的条件下咱们尝试列举两条对应路径间的关系。

      枚举vi的其中一条路径 ∑Wuv*∏1/cnt[u],那么实际上它对应着 i的一条路径 

      ((∑Wuv) xor Wvi i)*∏1/cnt[u]*1/cnt[vi],

      咱们发现,当Wvi i =1的时候,如果∑Wuv=1,这条路径就对答案无贡献,然后∑Wuv=0,才有意义,即咱们需要求 vi的所有路径中 Wuv =0的将它们变成1的时候,Wuv=1的将它们变成0的时候的答案,即Wuv要取反。这个比较好办...咱们发现 ∑Wuv*∏1/cnt[u]要变成(∑Wuv xor 1)*∏1/cnt[u],实际上只需要变成 (1-∑Wuv)*∏1/cnt[u],然后这个的总式子就是:
     ∑(1-∑Wuv)*∏1/cnt[u]  
   =∑∏1/cnt[u]-∑∑Wuv*∏1/cnt[u]
   =∑∏1/cnt[u]-x[vi]
     而∑∏1/cnt[u]实际上是趋近于1的(为什么呢?咱不知道...0w0实际上这个∑∏1/cnt[u]就应该是随机走无限步能够走到vi的概率,考虑补集:走无限步不能走到vi的概率...那个的话显然是趋近于0的,所以这个就是趋近于1的。但是如果真要推导应该是这样子推得把...)所以咱们证明了,这个式子的最终形式就是:

      ∑∏1/cnt[u]-x[vi]=1-x[vi]

     即当 i 与相邻点 vi间的边的边权为1的时候,vi的期望对i的期望的贡献就是 (1-x[vi])/cnt[vi]。
     然后这只是Wvii=1的,Wvii=0的时候实际上不用上面那么麻烦的推导了....咱们可以发现就是 x[vi]了,所以这个的贡献就是 x[vi]/cnt[vi],然后就这样...

     注意上面的推导中没有提及自环或者重边,但是咱们还是推导出来了,所以这道题的重边自环啥的咱们无视就可以了。
     然后咱们可以对每个点都列出一个方程,可以列出N-1个方程,然后有N-1个未知数(x[i]),然后高斯消元即可得到N-1个x[i]。答案就是X[1]
 
     然后这题有个想法就是为什么不能设x[i]表示从起点到N的期望异或和....这个的主要原因是因为走到N以后就必须强行终止这个设定。如果这个来列的话,就需要在x[n]的方程里面特殊考虑每一个相邻点被走到的概率。但是这个咱们求不出来。

     最后写的时候...突然发现自己忘了高斯消元怎么写的了233...又一次成功蒟蒻= =
===================================

program hnoi2011day2b;
const maxm=20010;
type edge=record
v,w,pre:longint;
end;

var e:array[0..maxm shl 1]of edge;
n,m,tot,t:longint;
cnt,last:array[0..110]of longint;
f:array[0..110,0..110]of double;
ans,now:double;

procedure addedge(u,v,w:longint);
begin
inc(tot);e[tot].v:=v;e[tot].w:=w;
e[tot].pre:=last[u];last[u]:=tot;
if u=v then exit;
inc(tot);e[tot].v:=u;e[tot].w:=w;
e[tot].pre:=last[v];last[v]:=tot;
end;

procedure init;
var i,j,k,u,v,w,max,tmp:longint;
tt:double;
begin
read(n,m);
max:=-1;
fillchar(cnt,sizeof(cnt),0);
fillchar(last,sizeof(last),0);
tot:=0;
for i:=1 to m do
begin
read(u,v,w);
addedge(u,v,w);
if max<w then max:=w;
inc(cnt[u]);
if u<>v then inc(cnt[v]);
end;
t:=0;ans:=0;
while max<>0 do
begin
inc(t);
max:=max shr 1;
end;
for t:=0 to t-1 do
begin
for i:=1 to n do
begin
for j:=1 to n+1 do f[i][j]:=0;
tmp:=last[i];
while tmp<>0 do
begin
if e[tmp].w and 1=0 then
f[i][e[tmp].v]:=f[i][e[tmp].v]+1/cnt[i]
else
begin
f[i][e[tmp].v]:=f[i][e[tmp].v]-1/cnt[i];
f[i][n+1]:=f[i][n+1]-1/cnt[i];
end;
tmp:=e[tmp].pre;
end;
f[i][i]:=f[i][i]-1;
end;
for i:=1 to n-1 do
begin
max:=i;
for j:=i+1 to n-1 do
if abs(f[j][i])>abs(f[max][i])then max:=j;
if (max<>i) then
for j:=1 to n+1 do
begin
tt:=f[i][j];f[i][j]:=f[max][j];f[max][j]:=tt;
end;
for j:=i+1 to n-1 do
if abs(f[j][i])>0 then
begin
tt:=f[j][i]/f[i][i];
for k:=i to n+1 do
f[j][k]:=f[j][k]-tt*f[i][k];
end;
end;
for i:=n-1 downto 1 do
begin
for j:=i+1 to n-1 do
f[i][n+1]:=f[i][n+1]-f[j][n+1]*f[i][j];
f[i][n+1]:=f[i][n+1]/f[i][i];
end;
writeln(f[1][n+1]:0:3);
ans:=ans+f[1][n+1]*(1<<t);
for i:=1 to tot do
e[i].w:=e[i].w shr 1;
end;
write(ans:0:3);
end;

begin
init;
end.


  评论这张
 
阅读(53)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017