[关闭]
@ysner 2018-03-30T23:48:26.000000Z 字数 1743 阅读 1968

[HNOI2011]XOR与路径

高斯消元 期望


题面

从 1 号节点开始,以相等的概率,随机选择与当前节点相关联的某条边,并沿这条边走到下一个节点,重复这个过程,直到走到 N 号节点为止,便得到一条从 1 号节点到 N 号节点的路径。显然得到每条这样的路径的概率是不同的并且每条这样的路径的“XOR 和”也不一样。现在请你求出该算法得到的路径的“XOR 和”的期望值。


解析

这和[HNOI2013]游走好像啊。点概率和边概率的公式一模一样。于是没怎么动脑子就切了。
但我们发现XOR和的期望值不太好处理,因为期望是不能异或的。
根据异或的套路,我们应该分位计算。

在分位的情况下,有公式(是边的意思)

于是我们就可以get一个叫的新姿势。

这显然不能DP,于是便想想高斯消元,化化式子。
默默移项
接下来就只要注意自环问题了。

Update:记得提醒我写篇期望总结。

  1. // luogu-judger-enable-o2
  2. #include<iostream>
  3. #include<cmath>
  4. #include<cstring>
  5. #include<cstdio>
  6. #include<cstdlib>
  7. #include<algorithm>
  8. #define ll long long
  9. #define re register
  10. #define il inline
  11. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  12. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  13. using namespace std;
  14. const int N=200;
  15. int h[N*N<<1],cnt,in[N],n,m;
  16. double dp[N][N],x[N],ans=0;
  17. struct Edge
  18. {
  19. int to,next;ll w;
  20. }e[N*N<<1];
  21. il void add(re int u,re int v,re int w)
  22. {
  23. e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;
  24. }
  25. il int gi()
  26. {
  27. re int x=0,t=1;
  28. re char ch=getchar();
  29. while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  30. if(ch=='-') t=-1,ch=getchar();
  31. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  32. return x*t;
  33. }
  34. il void Gauss()
  35. {
  36. fp(i,1,n)
  37. fp(j,i+1,n)
  38. fq(k,n+1,1) dp[j][k]-=dp[i][k]*dp[j][i]/dp[i][i];
  39. fq(i,n,1)
  40. {
  41. x[i]=dp[i][n+1];
  42. fq(j,n,i+1) x[i]-=dp[i][j]*x[j];
  43. x[i]/=dp[i][i];
  44. }
  45. }
  46. int main()
  47. {
  48. memset(h,-1,sizeof(h));
  49. n=gi();m=gi();
  50. fp(i,1,m)
  51. {
  52. re int u=gi(),v=gi(),w=gi();
  53. add(u,v,w);++in[v];
  54. if(u^v) add(v,u,w),++in[u];
  55. }
  56. fp(ysn,0,30)
  57. {
  58. memset(dp,0,sizeof(dp));
  59. fp(u,1,n-1)
  60. {
  61. dp[u][u]=1;
  62. for(re int i=h[u];i+1;i=e[i].next)
  63. {
  64. re int v=e[i].to,w=e[i].w&(1<<ysn);
  65. if(w) dp[u][v]+=1.0/in[u],dp[u][n+1]+=1.0/in[u];
  66. else dp[u][v]-=1.0/in[u];
  67. }
  68. }
  69. dp[n][n]=1;
  70. Gauss();
  71. ans+=x[1]*(1<<ysn);
  72. }
  73. printf("%.3lf\n",ans);
  74. return 0;
  75. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注