juju527's blog

因为失去，所以明白

概率与期望

发布于 2020-04-21 | 分类于 概率 、 期望 、 学习笔记 | 15分钟 | 2726字数 | 浏览量：

概率

随机事件

1.可以重复做

2.可以枚举出所有可能结果

对于每一个可能结果，我们称为一个样本点

所有样本点的集合，我们称为样本空间

3.不可预料出现哪一个结果

概率的表示

A随机事件出现的概率：P(A)

B随机事件出现的概率：P(B)

A,B均出现的概率：P(AB) [积事件]

A,B至少有一个出现的概率：P(A+B)[和事件]

排列组合

排列：考虑顺序的选取

组合：不考虑顺序的选取

Anm=n!(n−m)!Cnm=AnmAmmCnm=n!m!(n−m)!A_n^m=\frac{n!}{(n-m)!}\\ C_n^m=\frac{A_n^m}{A_m^m}\\ C_n^m=\frac{n!}{m!(n-m)!}

随机变量

将随机事件映射成函数

离散型：随机变量取值有限

连续型：随机变量取值无限

期望

expectation

E(X)=∑Pi×xiPi为随机变量i出现的概率xi为随机变量i的权值E(a×X+b×Y)=a×E(X)+b×E(Y)E(X)=\sum P_i\times x_i\\ P_i为随机变量i出现的概率\\ x_i为随机变量i的权值\\ E(a\times X+b\times Y)=a\times E(X)+b\times E(Y)\\

例题：

FAVDICE - Favorite Dice

设dp[i]表示已经掷到了i个不同的面，还需掷多少次的期望

所求即dp[0]

那么对于dp[i]是怎么转移的呢

dp[i]=indp[i]+n−indp[i+1]+1有in的概率掷到已经掷到过的面，此时仍然还要掷f[i]次骰子有n−in的概率掷到没掷到过的面，此后就掷到过i+1个面了，还需掷f[i+1]次骰子无论是情况1还是情况2，我们都要掷一次骰子dp[i]=\frac{i}{n}dp[i]+\frac{n-i}{n}dp[i+1]+1\\ 有\frac{i}{n}的概率掷到已经掷到过的面，此时仍然还要掷f[i]次骰子\\ 有\frac{n-i}{n}的概率掷到没掷到过的面，此后就掷到过i+1个面了，还需掷f[i+1]次骰子\\ 无论是情况1还是情况2，我们都要掷一次骰子

至于能不能写出正推的状态转移方程

答案是否定的

qaq

One Person Game

这里我们很容易设出这样的状态

dp[i]表示已有i个点数，达到大于n个点数的期望次数

p=1.0/k1/k2/k3j∈[1,a)∪(a,k1],k∈[1,b)∪(b,k2],l∈[1,c)∪(c,k3],dp[i]=p∗(∑dp[i+j+k+l])+p∗dp[0]+1p=1.0/k1/k2/k3\\ j\in[1,a)\cup(a,k1],k\in[1,b)\cup(b,k2],l\in[1,c)\cup(c,k3],\\ dp[i]=p*(\sum dp[i+j+k+l])+p*dp[0]+1

但由于dp[i+j+k+l]已知，dp[0]未知

我们无法直接递推这个式子得到答案

其实对于这样的n+1个方程，我们可以用高斯消元搞定

但数据范围不允许n^3的复杂度

我们应另求出路

考虑设dp[i]=a[i]∗dp[0]+b[i]那么dp[0]=a[0]∗dp[0]+b[0]dp[0]=b[0]1−a[0]求得a[0],b[0]即可考虑初始方程，设i+j+k+l=xdp[i]=p∗(∑dp[x])+p∗dp[0]+1dp[x]=a[x]∗dp[0]+b[x]dp[i]=p∗((∑a[x])∗dp[0]+(∑b[x]))+p∗dp[0]+1dp[i]=p∗((∑a[x])+1)∗dp[0]+p∗(∑b[x])+1则可得a[i]=p∗((∑a[x])+1)b[i]=p∗(∑b[x])+1考虑设\\ dp[i]=a[i]*dp[0]+b[i]\\ 那么\\ dp[0]=a[0]*dp[0]+b[0]\\ dp[0]=\frac{b[0]}{1-a[0]}\\ 求得a[0],b[0]即可\\ 考虑初始方程，设i+j+k+l=x\\ dp[i]=p*(\sum dp[x])+p*dp[0]+1\\ dp[x]=a[x]*dp[0]+b[x]\\ dp[i]=p*((\sum a[x])*dp[0]+(\sum b[x]))+p*dp[0]+1\\ dp[i]=p*((\sum a[x])+1)*dp[0]+p*(\sum b[x])+1\\ 则可得\\ a[i]=p*((\sum a[x])+1)\\ b[i]=p*(\sum b[x])+1\\

搞定qaq

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=505;
double x[maxn],y[maxn];
int read(){
	int x=0,y=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*y;
}
int main(){
	int t;
	t=read();
	while(t--){
		int n,k1,k2,k3,a,b,c;
		n=read();
		k1=read();k2=read();k3=read();
		a=read();b=read();c=read();
		double p=1.0/k1/k2/k3;
		x[n+1]=0;
		y[n+1]=0;
		for(int i=n;i>=0;i--){
			x[i]=p;
			y[i]=1;
			for(int j=1;j<=k1;j++){
				for(int k=1;k<=k2;k++){
					for(int l=1;l<=k3;l++){
						if(j==a&&k==b&&l==c)continue;
						int v=i+j+k+l;
						if(v>n)v=n+1;
						x[i]+=p*x[v];
						y[i]+=p*y[v];
					}
				}
			}
		}
		printf("%.15f\n",y[0]/(1-x[0]));
	}
	return 0;
}

Maze

容易想到的期望dp状态

dp[i]=k[i]∗dp[1]+e[i]∗0+(1−k[i]−e[i])∗1.0/edge∗((∑dp[j])+1)dp[i]=k[i]*dp[1]+e[i]*0+(1-k[i]-e[i])*1.0/edge*((\sum dp[j])+1)

由于j为所有与i有直接边相连的节点

想到树形dp

将父节点与子节点分开计算

设p=(1−k[i]−e[i])∗1.0/edgedp[i]=k[i]∗dp[1]+e[i]∗0+p∗dp[fa]+p∗(∑dp[son])+p设 p=(1-k[i]-e[i])*1.0/edge\\ dp[i]=k[i]*dp[1]+e[i]*0+p*dp[fa]+p*(\sum dp[son])+p

由于dp[1]未知

我们考虑采取上一题类似的方法

设dp[i]=a[i]∗dp[1]+b[i]∗dp[fa]+c[i]dp[1]=c[i]1−a[i]故推得系数a,b,c即可代入初始dp方程dp[i]=k[i]∗dp[1]+e[i]∗0+p∗dp[fa]+p∗(∑(a[son]∗dp[1]+b[son]∗dp[i]+c[son]))+pdp[i]=k[i]∗dp[1]+p∗dp[fa]+p∗dp[1]∗(∑a[son])+p∗dp[i]∗(∑b[son])+p∗(∑c[son])+p(1−p∗(∑b[son]))dp[i]=(k[i]+p∗(∑a[son]))∗dp[1]+p∗dp[fa]+p∗(∑c[son])+pdp[i]=k[i]+p∗(∑a[son])1−p∗(∑b[son])∗dp[1]+p1−p∗(∑b[son])∗dp[fa]+p∗(∑c[son])+p1−p∗(∑b[son])故a[i]=k[i]+p∗(∑a[son])1−p∗(∑b[son])b[i]=p1−p∗(∑b[son])c[i]=p∗(∑c[son])+p1−p∗(∑b[son])设 dp[i]=a[i]*dp[1]+b[i]*dp[fa]+c[i]\\ dp[1]=\frac{c[i]}{1-a[i]}\\ 故推得系数a,b,c即可\\ 代入初始dp方程\\ dp[i]=k[i]*dp[1]+e[i]*0+p*dp[fa]+p*(\sum (a[son]*dp[1]+b[son]*dp[i]+c[son]))+p\\ dp[i]=k[i]*dp[1]+p*dp[fa]+p*dp[1]*(\sum a[son])+p*dp[i]*(\sum b[son])+p*(\sum c[son])+p\\ (1-p*(\sum b[son]))dp[i]=(k[i]+p*(\sum a[son]))*dp[1]+p*dp[fa]+p*(\sum c[son])+p\\ dp[i]=\frac{k[i]+p*(\sum a[son])}{1-p*(\sum b[son])}*dp[1]+\frac{p}{1-p*(\sum b[son])}*dp[fa]+\frac{p*(\sum c[son])+p}{1-p*(\sum b[son])}\\ 故\\ a[i]=\frac{k[i]+p*(\sum a[son])}{1-p*(\sum b[son])}\\ b[i]=\frac{p}{1-p*(\sum b[son])}\\ c[i]=\frac{p*(\sum c[son])+p}{1-p*(\sum b[son])}

树形dp即可

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=10005;
struct Edge{
    int to;
    int nxt;
}e[2*maxn];
int cnt;
int head[maxn];
double p1[maxn],p2[maxn];
double a[maxn],b[maxn],c[maxn];
int read(){
    int x=0,y=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*y;
}
void add(int u,int v){
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt++;
    return ;
}
void dfs(int x,int fa){
    int edge=1;
    if(!fa)edge=0;
    double suma=0,sumb=0,sumc=0;
    for(int i=head[x];i!=-1;i=e[i].nxt){
        int tmp=e[i].to;
        if(tmp==fa)continue;
        dfs(tmp,x);
        edge++;
        suma+=a[tmp];
        sumb+=b[tmp];
        sumc+=c[tmp];
    }
    double p=(1-p1[x]-p2[x])*1.0/edge,val=1-p*sumb;
    a[x]=(p1[x]+p*suma)*1.0/val;
    b[x]=p*1.0/val;
    c[x]=(p*sumc+1-p1[x]-p2[x])/val;
    return ;
}
int main(){
    int t,cas=0;
    t=read();
    while(t--){
        int n;
        n=read();
        cnt=0;
        memset(head,-1,sizeof(head));
        for(int i=1;i<n;i++){
            int x,y;
            x=read();y=read();
            add(x,y);
            add(y,x);
        }
        for(int i=1;i<=n;i++){
            int x,y;
            x=read();y=read();
            p1[i]=x*1.0/100;
            p2[i]=y*1.0/100;
        }
        dfs(1,0);
        cas++;
        if(a[1]==1)printf("Case %d: impossible\n",cas);
        else printf("Case %d: %.6f\n",cas,c[1]/(1-a[1]));
    }
    return 0;
}#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=10005;
struct Edge{
    int to;
    int nxt;
}e[2*maxn];
int cnt;
int head[maxn];
double p1[maxn],p2[maxn];
double a[maxn],b[maxn],c[maxn];
int read(){
    int x=0,y=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*y;
}
void add(int u,int v){
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt++;
    return ;
}
void dfs(int x,int fa){
    int edge=1;
    if(!fa)edge=0;
    double suma=0,sumb=0,sumc=0;
    for(int i=head[x];i!=-1;i=e[i].nxt){
        int tmp=e[i].to;
        if(tmp==fa)continue;
        dfs(tmp,x);
        edge++;
        suma+=a[tmp];
        sumb+=b[tmp];
        sumc+=c[tmp];
    }
    double p=(1-p1[x]-p2[x])*1.0/edge,val=1-p*sumb;
    a[x]=(p1[x]+p*suma)*1.0/val;
    b[x]=p*1.0/val;
    c[x]=(p*sumc+1-p1[x]-p2[x])/val;
    return ;
}
int main(){
    int t,cas=0;
    t=read();
    while(t--){
        int n;
        n=read();
        cnt=0;
        memset(head,-1,sizeof(head));
        for(int i=1;i<n;i++){
            int x,y;
            x=read();y=read();
            add(x,y);
            add(y,x);
        }
        for(int i=1;i<=n;i++){
            int x,y;
            x=read();y=read();
            p1[i]=x*1.0/100;
            p2[i]=y*1.0/100;
        }
        dfs(1,0);
        cas++;
        if(a[1]==1)printf("Case %d: impossible\n",cas);
        else printf("Case %d: %.6f\n",cas,c[1]/(1-a[1]));
    }
    return 0;
}
# 概率 # 期望 # 学习笔记
网络流 上一篇
二分图 下一篇
0%