在概率论和统计学中，数学期望(mathematic expectation )（或均值，亦简称期望）是试验中每次可能结果的概率乘以其结果的总和，是最基本的数学特征之一。它反映随机变量平均取值的大小。
期望具有线性性质，所以我们可以很方便的求解。
P4316 绿豆蛙的归宿
这题就是教你求期望，在 DAG 上，容易想到拓扑排序后跑 DP。
设 \(f_i\) 表示从起点到 \(i\) 点的期望，\(p_i\) 表示从起点到 \(i\) 点的概率。显然有状态转移方程
\[f_i=\frac{f_j+w_{i\to j}\cdot p_j}{out_j} \]#include<bits/stdc++.h>
inline int read(){
char ch=getchar();int x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
const int N=1e5+10;
int n,m,tot,head[N],out[N],in[N];
struct edge{int v,next,w;}e[N<<1];
inline void add(int w,int v,int u){e[++tot]={v,head[u],w};head[u]=tot;out[u]++;in[v]++;}
double ans,f[N],p[N];
inline void topo(){
std::queue<int> q;
for(int i=1;i<=n;++i)if(!in[i])q.push(i);
p[1]=1;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i;i=e[i].next){
int v=e[i].v;
f[v]+=(f[u]+e[i].w*p[u])/out[u];
p[v]+=p[u]/out[u];
if(!--in[v])q.push(v);
}
}
}
int main(){
// freopen("in.in","r",stdin),freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0),std::cout.tie(0);
n=read(),m=read();
for(int i=1;i<=m;++i){
add(read(),read(),read());
}
topo();
printf("%.2lf\n",f[n]);
}
P1654 OSU!
设 \(f_i\) 表示到第 \(i\) 个位置时的期望，经过思考后发现因为取立方的缘故，不是很好转移。考虑将式子展开。
\((x+1)^3=x^3+3\cdot x^2+3\cdot x+1\) 不难发现只多了 \(3\cdot x^3+3\cdot x+1\) ，考虑将它们分别维护出来。
设 \(x1_i\) 表示 \(x\)，设 \(x2_i\) 表示 \(x^2\)，有
$x1_i=(x1_{i-1}+1)\cdot p_i $
\(x2_i=(x2_{i-1}+2\cdot x1_{i-1}+1)\cdot p_i\)
\(f_i=f_{i-1}+[3\cdot(x1_{i-1}+x2_{i-1})+1]\cdot p_i\)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 111111
#define int long long
using namespace std;
int n;
double p[maxn];
double x1[maxn],x2[maxn],ans[maxn];
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
scanf("%lf",&p[i]);
for(int i=1;i<=n;i++){
x1[i]=(x1[i-1]+1)*p[i];
x2[i]=(x2[i-1]+2*x1[i-1]+1)*p[i];
ans[i]=ans[i-1]+(3*(x1[i-1]+x2[i-1])+1)*p[i];
}
printf("%.1lf",ans[n]);
return 0;
}
时间复杂度 \(O(n)\)，观察上面的式子，发现它还可以拿矩阵快速幂来优化，故时间复杂度可以降到 \(O(n\log n)\)
本人的做法通过打表找到了一定的规律，发现每次贡献都会多一个系数为 \(6\) 的贡献，实际上原理一样，故只贴代码，不多赘述了。
#include<bits/stdc++.h>
inline int read(){
char ch=getchar();int x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
const int N=1e5+10;
int n;
double p[N],f[N],zc,last,y;
int main(){
// freopen("in.in","r",stdin),freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0),std::cout.tie(0);
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%lf",p+i);
f[1]=1*p[1];last=1;zc=0;y=0;
for(int i=2;i<=n;++i){
last*=p[i-1];y*=p[i-1];y+=6*p[i-1]*(1-p[i-2]);
zc*=p[i-1],zc+=y;
f[i]=f[i-1]*(1-p[i])+p[i]*(f[i-1]+(1-p[i-1])+zc+last);
last=(1-p[i-1])+zc+last;
}
printf("%.1lf",f[n]);
}
关于此题将 \(3\) 次方推广到 \(k\) 次方，要用到一些多项式的知识，感兴趣可以去看这里的一些讨论，此题还有一些多倍经验，如P1365 WJMZBMR打osu! / Easy 和Let's Play Osu!，做法大同小异，不多赘述。