概率期望
xukuan
2020-08-10 20:58:00
## 公式
期望=$\sum$ 概率\*收益
设E(A)表示A的期望
$E(AB)=E(A)*E(B)$
## 例题
### P4550 收集邮票
线性期望例题
用$g_i$表示取i张邮票的期望步数
这里收益都是1，所以期望=概率
显然$g_i=g_{i-1}+\frac{n}{i}$
用$f_i$表示取第i张邮票要花的钱
$f_i=\frac{n-i}{i}*(g_i+1)+g_{i-1}+f_{i-1}+1$
这个主要是收益的式子，过程比较乱，就不写了，根据这个去推：对于第i张邮票，为了获得它的平均价格是购买前i张邮票的期望次数之和
代码：
```cpp
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll N=10010;
ll n;
double g[N],f[N];
int main(){
cin>>n;
for(ll i=1; i<=n; i++){
g[i]=g[i-1]+n*1.0/i;
f[i]=f[i-1]+g[i-1]+(n-i)*1.0/i*(g[i]+1)+1;
}
printf("%.2lf",f[n]);
return 0;
}
```
### P1365 WJMZBMR打osu! / Easy
二维期望例题
用$len_i$表示第i个点连续期望有$len_i$个o,$f_i$表示第i个点连续得分为$f_i$
当$s_i='o'$时：
- $len_i=len_{i-1}+1$
- $f_i=f_{i-1}+len_i^2-len_{i-1}^2=f_{i-1}+2*len{i-1}+1$
当$s_i='x'$时
- $len_{i}=0$
- $f_i=f_{i-1}$
当$s_i='?'$时
当前点有$\frac{1}{2}$的概率为x，有$\frac{1}{2}$的概率为o：$f_i$,$len_i$的期望为上述的平均值。
- $len_i=\frac{len_{i-1}+1}{2}$
- $f_i$的期望为$\frac{f_{i-1}+f_{i-1}+2*len{i-1}+1}{2}=f_{i-1}+len_{i-1}+\frac{1}{2}$
代码：
```cpp
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll N=300010;
ll n;
char s[N];
double len,f[N];
int main(){
scanf("%lld",&n);
scanf("%s",s+1);
for(ll i=1; i<=n; i++){
if(s[i]=='o'){
f[i]=f[i-1]+2*len+1;
len++;
}
else if(s[i]=='x'){
f[i]=f[i-1];
len=0;
}
else if(s[i]=='?'){
f[i]=f[i-1]+len+0.5;
len=(len+1)/2;
}
}
printf("%.4lf",f[n]);
return 0;
}
```
### P1654 OSU!
高维期望例题
直接给式子
$(x+1)^3-x^3=3x^2+3x+1$
$f_i$表示答案的期望，$len2_i$表示连续长度的二次方的期望，$len1_i$连续长度的期望
$f_i=f_{i-1}+a_i*(3*len2_i+3*len1_i+1)\\len2_i=(len2_i+2*len1_{i}+1)*a_i\\len1_i=(len1_i+1)*a_i\\$
代码：
```cpp
//(x+1)^3-x^3=3x^2+3x+1
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll N=100010;
ll n;
double a[N],f[N],len1,len2;
int main(){
scanf("%lld",&n);
for(ll i=1; i<=n; i++) scanf("%lf",&a[i]);
for(ll i=1; i<=n; i++){
f[i]=f[i-1]+a[i]*(3*len2+3*len1+1);
len2=(len2+2*len1+1)*a[i];
len1=(len1+1)*a[i];
}
printf("%.1lf",f[n]);
return 0;
}
```
### P1850 换教室
多状态期望例题
用$f_{i,j,k}$表示前i节课申请j个，第i节课在哪个教室上课的期望，$k=1$表示换教室，$k=0$不换
$1 \leq v \leq 300$，可直接floyd求任意两点间距离
前一个到后一个的期望$=\sum$前一个的期望\*前一个向后一个转移的概率
由前一个推到后一个的时候
$f_{i,j,0}=\min(f_{i-1,j,0}+d_{c1,c3},f_{i-1,j,1})+f_{c1,c3}*(1-k_{i-1})+d_{c2,c3}*k_{i-1}$
$f_{i,j,1}=\min(f_{i-1,j-1,0}+d_{c1,c3}*(1-k_i)+d_{c1,c4}*k_i,f_{i-1,j-1,1}+d_{c2,c4}*k_i*k_{i-1}+d_{c2,c3}*k_{i-1}*(1-k_i)+d_{c1,c4}*(1-k_{i-1})*k_i+d_{c1,c3}*(1-k_{i-1})*(1-k_i)$
```cpp
#include<bits/stdc++.h>
#define ll long long
#define INF 2147483647
using namespace std;
double k[20010],dp[2010][2010][2],Min=INF;
ll a[2010][2010],c[20010],d[20010],n,m,v,e,f[2010][2010];
inline void floyd(){
for(ll k=1; k<=v; k++){
for(ll i=1; i<=v; i++){
for(ll j=1; j<=v; j++){
f[i][j]=f[j][i]=min(f[i][j],f[i][k]+f[k][j]);
}
}
}
}
int main(){
scanf("%lld %lld %lld %lld",&n,&m,&v,&e);
for(ll i=1; i<=n; i++) scanf("%lld",&c[i]);
for(ll i=1; i<=n; i++) scanf("%lld",&d[i]);
for(ll i=1; i<=n; i++) scanf("%lf",&k[i]);
for(ll i=1; i<=v; i++){
for(ll j=1; j<i; j++){
f[i][j]=f[j][i]=INF;
}
}
for(ll i=1; i<=n; i++){
for(ll j=0; j<=m; j++){
dp[i][j][0]=dp[i][j][1]=INF;
}
}
while(e--){
ll a,b,w;
scanf("%lld %lld %lld",&a,&b,&w);
f[a][b]=f[b][a]=min(f[a][b],w);
}
floyd();
dp[1][0][0]=dp[1][1][1]=0;
for(ll i=2; i<=n; i++){
double add=f[c[i-1]][c[i]];
for(ll j=0; j<=m&&j<=i; j++){
dp[i][j][0]=min(dp[i-1][j][0]+add,dp[i-1][j][1]+f[d[i-1]][c[i]]*k[i-1]+f[c[i-1]][c[i]]*(1-k[i-1]));
if(j) dp[i][j][1]=min(dp[i-1][j-1][0]+f[c[i-1]][d[i]]*k[i]+f[c[i-1]][c[i]]*(1-k[i]),dp[i-1][j-1][1]+f[c[i-1]][c[i]]*(1-k[i-1])*(1-k[i])+f[c[i-1]][d[i]]*(1-k[i-1])*k[i]+f[d[i-1]][c[i]]*(1-k[i])*k[i-1]+f[d[i-1]][d[i]]*k[i-1]*k[i]);
}
}
for(ll i=0; i<=m; i++) Min=min(Min,min(dp[n][i][0],dp[n][i][1]));
printf("%.2lf",Min);
return 0;
}
```
### BZOJ3270 博物馆
环型点期望例题
对于任意的$x$,$y$,$x \neq y$:
- $x \rightarrow u$，y不动
- $y \rightarrow v$，x不动
- $x \rightarrow u,y \rightarrow v$
- $x,y$都不动
我们用$a_{(x,y),(u,v)}$表示从状态$(x,y)$到状态$(u,v)$的概率。
根据上面的推断，我们得出结论：
当x与u相连或x=u，而且y与v相连或y=v时
$$
a_{(x,y),(u,v)}=\left\{
\begin{aligned}
-1,x=u \space and \space y=v\\
\frac{1-p_v}{degree_v}*p_x,x=u \space and \space y \neq v\\
\frac{1-p_u}{degree_u}*p_y,y=v \space and \space x \neq u\\
\frac{1-p_u}{degree_u}*\frac{1-p_v}{degree_v},x \neq u \space and \space y \neq v\\
\end{aligned}
\right.
$$
结果状态是$a_{id(s,t),endpos}=1$
其他情况$a_{(x,y),(u,v)}$均为0
因为状态里面有环，直接高斯消元
最后输出$a_{id(i,i),endpos}$
我在代码里把endpos用作$n*n+1$
代码：
```cpp
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll N=30;
ll n,m,s,t,degree[N];
vector<ll> G[N];
double a[N*N][N*N],p[N];
inline ll read(){
ll x=0,tmp=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') tmp=-1;
ch=getchar();
}
while(isdigit(ch)){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return tmp*x;
}
inline ll id(ll x,ll y){
return (x-1)*n+y;
}
inline void Gauss(ll n){
for(ll i=1; i<=n; i++){
ll k=i;
for(ll j=i+1; j<=n; j++){
if(fabs(a[k][i])<fabs(a[j][i])) k=j;
}
swap(a[i],a[k]);
double div=a[i][i];
for(ll j=1; j<=n+1; j++) a[i][j]/=div;
for(ll j=1; j<=n; j++){
if(i==j) continue;
div=a[j][i];
for(ll k=1; k<=n+1; k++) a[j][k]-=a[i][k]*div;
}
}
}
int main(){
n=read(); m=read(); s=read(); t=read();
for(ll i=1; i<=n; i++) a[i][i]=1;
while(m--){
ll x=read(),y=read();
G[x].push_back(y);
G[y].push_back(x);
degree[x]++;
degree[y]++;
}
for(ll i=1; i<=n; i++) scanf("%lf",&p[i]);
for(ll x=1; x<=n; x++){
for(ll y=1; y<=n; y++){
if(x==y) a[id(x,y)][id(x,y)]=-1;
else a[id(x,y)][id(x,y)]=p[x]*p[y]-1;
for(ll i=0; i<(ll)G[x].size(); i++){
ll u=G[x][i];
if(u==y) continue;
a[id(x,y)][id(u,y)]=(1-p[u])/degree[u]*p[y];
}
for(ll i=0; i<(ll)G[y].size(); i++){
ll v=G[y][i];
if(x==v) continue;
a[id(x,y)][id(x,v)]=(1-p[v])/degree[v]*p[x];
}
for(ll i=0; i<(ll)G[x].size(); i++){
ll u=G[x][i];
for(ll j=0; j<(ll)G[y].size(); j++){
ll v=G[y][j];
if(u==v) continue;
a[id(x,y)][id(u,v)]=(1-p[u])/degree[u]*(1-p[v])/degree[v];
}
}
}
}
a[id(s,t)][n*n+1]=-1;
Gauss(n*n);
for(ll i=1; i<=n; i++) printf("%.6lf ",a[id(i,i)][n*n+1]); putchar('\n');
return 0;
}
```
### P3232 [HNOI2013]游走
环形边期望例题
我们求出每一条边的期望
首先到了n点之后就不会走出去，所以我们直接把n点作为结束状态
$a_{i,i}=1(1 \leq i <n),a_{1,n}=1$
然后对于所有边，$a_{x,y}-=\frac{1}{degree_y}$
这个可以认为是走过去再走回来的补偿概率
然后跑高斯消元
最后每条边的期望是$\sum \frac{a_{x,n}}{degree_x}+\frac{a_{y,n}}{degree_y}$
最后按边的期望排序，期望小的序号大
代码：
```cpp
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll N=510,M=125010;
ll n,m,x[M],y[M],degree[N];
double a[N][N],w[M],ans;
inline ll read(){
ll x=0,tmp=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') tmp=-1;
ch=getchar();
}
while(isdigit(ch)){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return tmp*x;
}
inline void Gauss(){
for(ll i=1; i<n; i++){
ll k=i;
for(ll j=i+1; j<n; j++){
if(fabs(a[k][i])<fabs(a[j][i])) k=j;
}
swap(a[i],a[k]);
double div=a[i][i];
for(ll j=1; j<=n; j++) a[i][j]/=div;
for(ll j=1; j<n; j++){
if(i==j) continue;
div=a[j][i];
for(ll k=1; k<=n; k++) a[j][k]-=a[i][k]*div;
}
}
}
inline bool cmp(double x,double y){
return x>y;
}
int main(){
n=read(); m=read();
for(ll i=1; i<=m; i++){
x[i]=read(); y[i]=read();
degree[x[i]]++;
degree[y[i]]++;
}
for(ll i=1; i<n; i++) a[i][i]=1;
a[1][n]=1;
for(ll i=1; i<=m; i++){
if(x[i]==n||y[i]==n) continue;
a[x[i]][y[i]]-=1.0/degree[y[i]];
a[y[i]][x[i]]-=1.0/degree[x[i]];
}
Gauss();
for(ll i=1; i<=m; i++) w[i]+=a[x[i]][n]/degree[x[i]]+a[y[i]][n]/degree[y[i]];
sort(w+1,w+1+m,cmp);
for(ll i=1; i<=m; i++) ans+=w[i]*i;
printf("%.3lf",ans);
return 0;
}
```
### P4564 [CTSC2018]假面
有干扰的线性期望例题
这题直接维护期望会非常难理解，由于概率非常好处理，所以维护概率
设$f_{i,j}$表示当前第i个人的血量为j的概率
转移方程只有2中情况：被打了掉血或不掉血。特别的，0血的人不会被打
$
f_{i,j}=\left\{
\begin{aligned}
f_{i,j+1}*p+f_{i,j}*(1-p),j \geq 1\\
f_{i,j+1}*p+f_{i,j},j=0\\
\end{aligned}
\right.
$
对于每一个怪而言：
期望直接用 $\sum$概率\*收益 来求
dp类似01背包的压维，倒着跑
$
dp_j=\left\{
\begin{aligned}
g_i*dp_{j-1}+(1-g_i)*dp_j,j \geq 1\\
(1-g_i)*dp_j,j=0
\end{aligned}
\right.
$
理论上可以出答案了，但跑的太慢，所以要优化。
活着就是血量不为0，概率可以直接得出
$g_i=1-f_{i,0}$
然后继续推
没人死就直接抄：当$g_i=1$时$sum_j=dp_{j+1}$
因为是在不死的人里面选，
$
sum_j=\left\{
\begin{aligned}
\frac{dp_j+sum_{j-1}*g_i}{1-g_i},j \geq 1\\
\frac{dp_j}{1-g_i},j=0\\
\end{aligned}
\right.
$
代码：
```cpp
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll N=2010,mod=998244353;
ll n,a[N],f[N][N],g[N],dp[N],sum[N];
inline ll read(){
ll x=0,tmp=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') tmp=-1;
ch=getchar();
}
while(isdigit(ch)){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return tmp*x;
}
inline void write(ll x){
if(x<0){
putchar('-');
x=-x;
}
ll y=10,len=1;
while(y<=x){
y=(y<<3)+(y<<1);
len++;
}
while(len--){
y/=10;
putchar(x/y+48);
x%=y;
}
}
inline ll ksm(ll x,ll y){
ll ans=1;
while(y){
if(y&1) ans=ans*x%mod;
x=x*x%mod;
y>>=1;
}
return ans;
}
inline ll inv(ll x){
return ksm(x,mod-2);
}
int main(){
n=read();
for(ll i=1; i<=n; i++){
a[i]=read();
f[i][a[i]]=1;
}
for(ll q=read(); q; q--){
ll op=read();
if(op==0){
ll x=read(),fenzi=read(),fenmu=read();
ll gailv=fenzi*inv(fenmu)%mod;
f[x][0]=(f[x][0]+f[x][1]*gailv%mod)%mod;
for(ll i=1; i<=a[x]; i++) f[x][i]=(f[x][i]*(mod+1-gailv)%mod+f[x][i+1]*gailv%mod)%mod;
}
else if(op==1){
ll m=read();
for(ll i=1; i<=m; i++){
ll x=read();
g[i]=(mod+1-f[x][0])%mod;
}
memset(dp,0,sizeof(dp));
dp[0]=1;
for(ll i=1; i<=m; i++){
for(ll j=i; j>=0; j--){
if(j) dp[j]=(g[i]*dp[j-1]%mod+(mod+1-g[i])%mod*dp[j]%mod)%mod;
else dp[j]=(mod+1-g[i])%mod*dp[j]%mod;
}
}
for(ll i=1; i<=m; i++){
if(!g[i]){
putchar('0'); putchar(' ');
continue;
}
if(g[i]==1){
for(ll j=0; j<m; j++) sum[j]=dp[j+1];
}
else{
ll x=inv((mod+1-g[i])%mod);
sum[0]=dp[0]*x%mod;
for(ll j=1; j<m; j++) sum[j]=(dp[j]+mod-sum[j-1]*g[i]%mod)%mod*x%mod;
}
ll ans=0;
for(ll j=0; j<m; j++) ans=(ans+sum[j]*inv(j+1)%mod)%mod;
write(g[i]*ans%mod); putchar(' ');
}
putchar('\n');
}
else cout<<"FUCK "<<op<<endl;
}
for(ll i=1; i<=n; i++){
ll ans=0;
for(ll j=1; j<=a[i]; j++) ans=(ans+j*f[i][j])%mod;
write(ans); putchar(' ');
}
putchar('\n');
return 0;
}
```