概率期望题目合集(1)

51Nod 1632 B君的连通

我们可以看出删去$i$条边会有$i+1$个联通块，所以可以得出以下的式子：$ans=sum _{i=0}^{n-1} (frac {1}{2})^{n-1} extrm{C} _{n-1}^{i}(i+1)$

因为最后答案要乘上$2^{n-1}$，所以化简一下(倒序相加)可以得到$ans=(n+1)2^{n-2}$

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
using namespace std;

const int maxn=100000+5,mod=1e9+7;

int n,ans; 

inline int power(int x,int y){
	int res=1;
	while(y){
		if(y&1)
			res=(1LL*res*x)%mod;
		x=(1LL*x*x)%mod,y>>=1;
	}
	return res;
}

signed main(void){
	scanf("%d",&n);
	for(int i=1,x;i<n;i++)
		scanf("%d%d",&x,&x);
	ans=1LL*(n+1)%mod*power(2,n-2)%mod;
	printf("%d
",ans);
	return 0;
}

 POJ 3557 Map Generator

应该是一个概率DP的问题，记$f[i]$为$i$个点联通的概率，如果我们正着考虑直接计算，那么没加入一个点我们就要枚举这个点是作为单独的一个联通块和剩下的大小为$i-1$的一个联通块连起来还是作为中间点连接多个联通块，然后枚举块的大小什么的，很麻烦...所以我们干脆反过来考虑，考虑不联通的概率，记为$g[i]$

我们枚举当前加入的点在大小为$j$的联通块，那么这$j$个点和剩下的$(i-j)$个点是不能有边相连的...

$g[i]=sum _{j=1}^{i-1} extrm{C} _{i-1}^{j-1}f[j](1-p)^{(j(i-j))}$...

$f[i]=1-g[i]$...

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
using namespace std;

const int maxn=20+5;

int n,c[maxn][maxn];

double p,f[maxn];

inline double power(double x,int y){
	double ans=1.0;
	while(y){
		if(y&1)
			ans*=x;
		x*=x,y>>=1;
	}
	return ans;
}

signed main(void){
	scanf("%d%lf",&n,&p);f[1]=1.0;
	for(int i=0;i<=n;i++)
		c[i][0]=c[i][i]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<i;j++)
			c[i][j]=c[i-1][j-1]+c[i-1][j];
	for(int i=2;i<=n;i++){
		double tmp=0;
		for(int j=1;j<=i-1;j++)
			tmp+=c[i-1][j-1]*f[j]*power(1-p,j*(i-j));
		f[i]=1.0-tmp;
	}
	printf("%.3f
",f[n]);
	return 0;	
}