算法进阶指南0x38概率与数学期望

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 3;
int n,last[3],a[maxn],b[maxn];
double ansxor,ansand,ansor;
void Rainbow(int k)
{
	last[0]=last[1]=0;
	int c1=0,c2=0;
	double w=(1<<k)*1.0/n/n;//最后写成/(n*n)就爆int了
	for(int i=1;i<=n;i++) {
		b[i]=(a[i]>>k)&1;
		if(b[i])/*区间长度为1即l=r=i*/ {
			ansxor+=w;
			ansand+=w;
			ansor+=w;
		}
		//以下计算长度大于等于2的区间 
		if(!b[i]) ansor+=2*w*last[1];
		else {
			ansand+=2*w*(i-1-last[0]); //减1是因为区间[r,r]已经被计算过了 
			ansor+=2*w*(i-1);
		} 
		ansxor+=2*w*(b[i]?c1:c2);
		c1++;
		if(b[i]) swap(c1,c2);
		last[b[i]]=i;
	}
} 
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=0;i<31;i++) Rainbow(i);
	printf("%.3lf %.3lf %.3lf",ansxor,ansand,ansor);
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 3;
int tot,ver[maxn],head[maxn],Next[maxn],edge[maxn],deg[maxn],out[maxn];
double d[maxn];
void add(int x,int y,int z)
{
	ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot;
}
void bfs(int s)
{
	queue<int> q;
	q.push(s);
	while(!q.empty())
	{
		int x=q.front(),y,z;
		q.pop();
		for(int i=head[x];i;i=Next[i]) {
			y=ver[i],z=edge[i];
			d[y]+=(d[x]+z)/out[y];
			deg[y]--;
			if(!deg[y]) q.push(y);
		}	
	}
}
int main()
{
	int n,m,a,b,c;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) {
		scanf("%d%d%d",&a,&b,&c);
		deg[a]++; out[a]++;//反图中的入度，原图中的出度，两者等价 
		add(b,a,c);//建原图的反图 
	} 
	bfs(n);//从n倒着算到1 
	printf("%.2lf",d[1]);
	return 0;
}