Mathematical probability expectation summary

Because I'm not very good at probability, I especially write a summary...

Collect stamps

The code of this problem is relatively short, but the thinking content is really high. In addition, the description of the transfer equation in some online problem solutions is too obvious, so some people may not understand this problem.

First consider whether you can directly push the formula calculation. You will find that not only the formula is difficult to push, but also it seems that it can't be calculated at all. So consider another routine method, dynamic programming.

If you directly set the expected cost of purchasing \ (I \) stamps as \ (f_i \), and then transfer it, you will find that you are stuck again, because the amount of money when you buy a stamp is related to the number of stamps, and the stamps you buy may be those you have bought before. What will happen between the two? dp has aftereffect.

Can't dp? It seems that there is nothing to push in the ordinary formula, so we think about how to eliminate the aftereffect. Assuming that we already know how many times we expect to buy this \ (n \) sheet after buying this time, we can calculate the cost in advance and eliminate the aftereffect.

So you can set \ (f_i \) as the expected purchase times of all \ (n \) kinds of stamps after you buy \ (I \), and set \ (g_i \) to represent the expected purchase cost of all \ (n \) kinds after you buy \ (I \), and consider the transfer of \ (f_i \) first, because it is used to assist the transfer of \ (g \) groups. Think about the impact after you buy this stamp, and you may buy the types you have bought. The probability is \ (\ frac{i}n \), Then buy all the expectations of \ (n \) or \ (f_i \) at this time. When learning probability dp for the first time, you may feel that there are some problems in this transfer. Can you transfer yourself?? In fact, this is only used to push the formula, so as to visualize an endless process, because you can buy stamps every time, and then buy them all the time.... Although this is my own tongue, I do understand it. Then I consider that the probability of buying a stamp that I haven't bought before is \ (\ frac{n-i}n \), and then there are \ (i+1 \) stamps. The expectation of buying all \ (n \) becomes \ (f_{i+1} \), which can also be understood from the perspective of collection. The cost 1 is expanded from collection \ (I \) to collection \ (i+1 \). I think it's easy to understand. Finally, I spent one purchase this time, The probability is obviously 1, so add a 1, that is

\[f_i=\frac{i}n\times f_i + \frac{n-i}n\times f_{i+1} + 1 \]

It is found that the recurrence formula of \ (f_i \) can be obtained after the migration merger,

\[f_i=f_{i+1}+\frac{n}{n-i} \]

The next step is the transfer of \ (g_i \). With the \ (f \) array, the aftereffect can be eliminated by calculating the cost in advance. The thinking of the transfer is similar to the above, except for the differences. If you buy the \ (I \) stamps you have bought this time, you need to add 1 to the cost of the \ (f_i \) stamps you want to buy later, and add a total of \ (f_i \) charges. This is the cost calculation in advance, and then transfer.

#include<cstdio>
const int N=1e4+10;
typedef double db;
db f[N],g[N];
int main(){
	freopen("D.in","r",stdin);
	freopen("D.out","w",stdout);
	int n;
	scanf("%d",&n);
	for(int i=n-1;i>=0;i--)
		f[i]=f[i+1]+1.0*n/(n-i);
	for(int i=n-1;i>=0;i--)
		g[i]=g[i+1]+f[i+1]+f[i]*i/(n-i)+1.0*n/(n-i);
	printf("%.2lf\n",g[0]);
	return 0;
}

Dice Basic Edition

Throw a dice \ (n \) times, and then ask the probability that the sum of points is greater than or equal to \ (X \).

This feeling will be better if it is included in the counting dp?? emm considers that the total number of cases thrown \ (n \) times is fixed, so it can calculate the total number of legal cases, and then calculate it with the most original method of calculating probability.
During calculation, define \ (f_{i,j} \) to indicate that it is the \ (I \) throw, the number of points and the number of schemes with \ (j \), and then transfer.

#include<iostream>
#define ll long long
using namespace std;
const int lqs=200;
ll f[lqs][lqs];
ll gcd(ll a,ll b){
	return b==0?a:gcd(b,a%b);
}
int main(){
	int n,x;
	cin>>n>>x;
	for(int i=1;i<=6;i++)
		f[1][i]=1;
	for(int i=2;i<=n;i++)
	for(int j=1;j<=6*i;j++)
	for(int k=1;k<=6;k++)
		if(j>k)
			f[i][j]+=f[i-1][j-k];
	ll ans=0,cnt=1;
	for(int i=1;i<=n;i++)cnt*=6;
	for(int i=x;i<=6*n;i++)
		ans+=f[n][i];
	if(ans==0)cout<<"0";
	else if(ans==cnt)cout<<"1";
	else {
		ll g=gcd(ans,cnt);
		cout<<ans/g<<'/'<<cnt/g;
	}
	return 0;
}

Congcong and cocoa

A better probability dp problem is only realized by memory search.
In fact, it seems that the most difficult thing to do is the walking method of the cat, because the walking method of the cat should not be the same for different positions of the cat and the mouse, so the preprocessed \ (nxt \) array represents the next walking method of the cat when the cat is \ (i \) and the mouse is \ (j \), and then we can do it.
Let \ (f_{i,j} \) denote the expected number of steps for the cat to catch the mouse when \ (i \) and the mouse is in \ (j \). It is not difficult to find out that when \ (i==j \), the value is 0, otherwise when \ (i \) can reach \ (j \) in one or two steps, the value is 1. Other situations can be transferred, mainly considering the direction of the mouse's next step. The rest is quite understandable.

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
struct Edge{
	int to,nxt;
}e[N<<1];
int h[N],idx;
void Ins(int a,int b){
	e[++idx].to=b;e[idx].nxt=h[a];h[a]=idx;
}
int nxt[N][N],dis[N][N];
void bfs(int s){
	queue<int> q;q.push(s);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=h[u];i;i=e[i].nxt){
			int v=e[i].to;
			if(dis[s][v])continue;
			dis[s][v]=dis[s][u]+1;
			q.push(v);
		}
	}
	dis[s][s]=0;
}
double f[N][N];
int d[N];
double dfs(int s,int t){
	if(f[s][t])return f[s][t];
	if(s==t)return 0;
	int fir=nxt[s][t];
	int sec=nxt[fir][t];
	if(fir==t||sec==t)return 1;
	f[s][t]=1;
	for(int i=h[t];i;i=e[i].nxt){
		int v=e[i].to;
		f[s][t]+=dfs(sec,v)*1.0/(d[t]+1);
	}
	f[s][t]+=dfs(sec,t)*1.0/(d[t]+1);
	return f[s][t];
}
int main(){
	int n,m,s,t;
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1;i<=m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		Ins(a,b);Ins(b,a);
		d[a]++;d[b]++;
	}
	memset(nxt,0x3f,sizeof(nxt));
	for(int i=1;i<=n;i++)bfs(i);
	for(int i=1;i<=n;i++){
		for(int j=h[i];j;j=e[j].nxt){
			int v=e[j].to;
			for(int k=1;k<=n;k++)if(dis[i][k]==dis[v][k]+1)nxt[i][k]=min(nxt[i][k],v);
		}
	}
	printf("%.3lf\n",dfs(s,t));
	return 0;
}

OSU

This question is also to push the formula. It is also to consider using one-step difference. The contribution change of length from \ (x \) to \ (x+1 \) is \ ((x+1)^3-x^3 \), and then push the formula to get that this formula is related to \ (x^2 \) and \ (x \), but note that the expected square is not equal to the expectation of square, so we need to deduce \ (x^2 \) and \ (x \).

#include<cstdio>
#include<iostream>
typedef double ll;
using namespace std;
int main(){
	int n;
	scanf("%d",&n);
	ll ans=0,E1=0,E2=0;
	for(int i=1;i<=n;i++){
		ll p;
		scanf("%lf",&p);
		ans+=(3*E1+3*E2+1)*p;
		E2=(E2+2*E1+1)*p;
		E1=(E1+1)*p;
	}
	printf("%.1lf",ans);
}

The guardian's challenge

An obvious probability \ (dp \)?, According to the meaning of the question, the state transition equation \ (f_{i,j,k} \) can be set to represent the probability of winning \ (k \) times when the current level is reached \ (I \), the backpack capacity is still \ (j \). The backpack capacity may be negative, so you need to shift the coordinate origin

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=400+10;
typedef double db;
db f[205][N][205],p[N];
int typ[N];
int main(){
	int n,L,K;
	scanf("%d%d%d",&n,&L,&K);
	for(int i=1;i<=n;i++){
		int x;scanf("%d",&x);
		p[i]=1.0*x/100;
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&typ[i]);
	}
	f[0][n][0]=1.0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=n*2;j++){
			f[i][j][0]+=f[i-1][j][0]*(1-p[i]);
			for(int k=1;k<=i;k++){
				if(typ[i]+j>=0){
					f[i][min(j+typ[i],2*n)][k]+=f[i-1][j][k-1]*p[i];
					f[i][j][k]+=f[i-1][j][k]*(1-p[i]);
				}
			}
		}
	}
	db ans=0;
	for(int i=n-K;i<=n*2;i++)
		for(int j=L;j<=n;j++)
			ans+=f[n][i][j];
	printf("%.6lf\n",ans);
	return 0;
}


Easy

One day WJMZBMR was playing osu ~ ~ ~ but he was too weak. In some places, he relied entirely on luck:(
Let's simplify the rules of the game
There are n clicks to do. Success is O and failure is x. The score is calculated according to comb. A continuous a comb has aa points, and comb is a great continuous o. For example, ooxxxooxxx, the score is 22 + 4 * 4 = 4 + 16 = 20.
Sevenkplus's idle panic depends on his playing a game. Some places have nothing to do with luck, either o or x. in some places, O or x are 50% possible, use? Sign. Like oo?xx is a possible input.
So what is the expected score of WJMZBMR osu in this game? Like oo?xx words,? If it is o, it means oooxx = > 9. If it is x, it means ooxxx = > 4. Naturally, it is expected that (4 + 9) / 2 = 6.5

In fact, it's similar to the above topic, except that? Look forward to it when you need it, and then deal with the rest as usual.

#include<cstdio>
#include<iostream>
using namespace std;
const int N=3e5+10;
char s[N];
int main(){
	int n;
	cin>>n>>s;
	double ans=0,len=0;
	for(int i=0;i<n;i++){
		if(s[i]=='o'){
			ans+=2*len+1;
			len++;
		}else if(s[i]=='x')
			len=0;
		else {
			ans+=(2*len+1)*0.5;
			len=(len+1)*0.5;
		}
	}
	printf("%.4lf",ans);
}

Single choice dislocation

Because each question is only related to the one exchanged with it, consider what happens when a question moves to the position of another question. Assuming that there are \ (Min \) and \ (max \) with smaller options, the probability of choosing the right one is \ (\ frac{1}{Min}\times \frac{Min}{Max}=\frac{1}{Max} \), and then it's gone.

Card game

In this problem, we find that in this game, the probability of a person winning has nothing to do with who is left on the field, only with how many people are left on the field and who is the dealer. Further, it has nothing to do with who is the dealer, only with the relative position of the dealer and the person who wins finally. Therefore, the state \ (f_{i,j} \) can be defined as the probability of a person remaining \ (i \) on the field and who is away from the dealer \ (j \), Then enumerate the cards drawn for transfer. Assuming that the position of the dealer in the next round after drawing the card is \ (p \), discuss the relationship between \ (p \) and \ (j \). If \ (p==j \) doesn't matter, the distance between \ (p > j \) is \ (p-j \), otherwise \ (i-(p-j) \) is the length of the other half of the ring.

#include<cstdio>
#include<cstring>
#include<algorithm>
const int N=60;
int card[N];
double f[N][N];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)scanf("%d",&card[i]);
	f[1][1]=100;
	for(int i=2;i<=n;i++){
		for(int j=1;j<=i;j++){
			for(int k=1;k<=m;k++){
				int pos=card[k]%i;
				if(pos==0)pos+=i;
				if(pos>j)f[i][j]+=f[i-1][i-pos+j]/m;
				else if(pos<j)f[i][j]+=f[i-1][j-pos]/m;
			}
		}
	}
	for(int i=1;i<=n;i++)printf("%.2lf%% ",f[n][i]);
	return 0;
}

Change classroom

This question may be similar to the ordinary dp routine. First, throw the restrictions in the question into the state, define \ (f_{i,j,k} \) as the first \ (I \) class, apply \ (j \), whether to apply for the \ (I \) time, and then transfer.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2010;
int dis[N][N],c[N],d[N];
double p[N],f[N][N][2];
int main(){
	memset(dis,0x3f,sizeof(dis));
	int n,m,v,e;
	scanf("%d%d%d%d",&n,&m,&v,&e);
	for(int i=1;i<=n;i++)scanf("%d",&c[i]);
	for(int i=1;i<=n;i++)scanf("%d",&d[i]);
	for(int i=1;i<=n;i++)scanf("%lf",&p[i]);
	for(int i=1;i<=v;i++)dis[i][i]=0;
	for(int i=1;i<=e;i++){
		int a,b,w;
		scanf("%d%d%d",&a,&b,&w);
		dis[a][b]=dis[b][a]=min(dis[a][b],w);
	}
	for(int k=1;k<=v;k++)
		for(int i=1;i<=v;i++)
			for(int j=1;j<=v;j++)
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
	for(int i=1;i<=n;i++)
		for(int j=0;j<=m;j++)
			f[i][j][0]=f[i][j][1]=1e30;
	f[1][1][1]=f[1][0][0]=0;
	for(int i=2;i<=n;i++)
		for(int j=0;j<=m;j++){
			f[i][j][0]=min(f[i-1][j][0]+dis[c[i-1]][c[i]],f[i-1][j][1]+p[i-1]*dis[d[i-1]][c[i]]+(1-p[i-1])*dis[c[i-1]][c[i]]);
			if(j)f[i][j][1]=min(f[i-1][j-1][0]+p[i]*dis[c[i-1]][d[i]]+(1-p[i])*dis[c[i-1]][c[i]],f[i-1][j-1][1]+p[i-1]*p[i]*dis[d[i-1]][d[i]]+(1-p[i-1])*p[i]*dis[c[i-1]][d[i]]+p[i-1]*(1-p[i])*dis[d[i-1]][c[i]]+(1-p[i-1])*(1-p[i])*dis[c[i-1]][c[i]]);
		}
	double ans=1e30;
	for(int i=0;i<=m;i++)ans=min(ans,min(f[n][i][0],f[n][i][1]));
	printf("%.2lf\n",ans);
	return 0;
}


Posted by Asday on Sun, 22 May 2022 11:57:45 +0300