@ysner
2018-03-30T23:48:26.000000Z
字数 1743
阅读 1951
高斯消元
期望
从 1 号节点开始,以相等的概率,随机选择与当前节点相关联的某条边,并沿这条边走到下一个节点,重复这个过程,直到走到 N 号节点为止,便得到一条从 1 号节点到 N 号节点的路径。显然得到每条这样的路径的概率是不同的并且每条这样的路径的“XOR 和”也不一样。现在请你求出该算法得到的路径的“XOR 和”的期望值。
这和[HNOI2013]游走好像啊。点概率和边概率的公式一模一样。于是没怎么动脑子就切了。
但我们发现XOR和的期望值不太好处理,因为期望是不能异或的。
根据异或的套路,我们应该分位计算。
在分位的情况下,有公式(是边的意思)
于是我们就可以get一个叫的新姿势。
这显然不能DP,于是便想想高斯消元,化化式子。
默默移项
接下来就只要注意自环问题了。
// luogu-judger-enable-o2
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=200;
int h[N*N<<1],cnt,in[N],n,m;
double dp[N][N],x[N],ans=0;
struct Edge
{
int to,next;ll w;
}e[N*N<<1];
il void add(re int u,re int v,re int w)
{
e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;
}
il int gi()
{
re int x=0,t=1;
re char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
il void Gauss()
{
fp(i,1,n)
fp(j,i+1,n)
fq(k,n+1,1) dp[j][k]-=dp[i][k]*dp[j][i]/dp[i][i];
fq(i,n,1)
{
x[i]=dp[i][n+1];
fq(j,n,i+1) x[i]-=dp[i][j]*x[j];
x[i]/=dp[i][i];
}
}
int main()
{
memset(h,-1,sizeof(h));
n=gi();m=gi();
fp(i,1,m)
{
re int u=gi(),v=gi(),w=gi();
add(u,v,w);++in[v];
if(u^v) add(v,u,w),++in[u];
}
fp(ysn,0,30)
{
memset(dp,0,sizeof(dp));
fp(u,1,n-1)
{
dp[u][u]=1;
for(re int i=h[u];i+1;i=e[i].next)
{
re int v=e[i].to,w=e[i].w&(1<<ysn);
if(w) dp[u][v]+=1.0/in[u],dp[u][n+1]+=1.0/in[u];
else dp[u][v]-=1.0/in[u];
}
}
dp[n][n]=1;
Gauss();
ans+=x[1]*(1<<ysn);
}
printf("%.3lf\n",ans);
return 0;
}