关于期望

期望的两个公式：
通用公式： ∑ p i × v i \sum p_i\times v_i ∑pi×vi，pi 为概率，vi 为得分
等概率： ∑ v i / c n t \sum v_i/cnt ∑vi/cnt，vi 为得分，cnt 为总选择。

简单求期望

例题1：期望独立单独计算

题目描述：有 n 道题，每道题有 ai 个答案。对于第 i 道题，小明随意的蒙了一个 [ 1 , a i ] [1,a_i] [1,ai] 的答案，即每道题都有 1 / a i 1/a_i 1/ai 的概率对。可是小明抄错了，不小心把第 i 道题的答案抄在了第 i+1 道题上，第 n 道题抄在了第 1 道题上。求小明期望的对题数量。
问题分析：若 a [ i ] = a [ i + 1 ] a[i] = a[i+1] a[i]=a[i+1]，则该次期望值为 1 / a i + 1 1/a_{i+1} 1/ai+1；若 a i > a i + 1 a_i > a_{i+1} ai>ai+1 ，则答案有 a i + 1 / a i a_{i+1}/a_i ai+1/ai 的概率在 [ 1 , a i + 1 ] [1,a_{i+1}] [1,ai+1] 里，而在里面有 1 / a i + 1 1/a_{i+1} 1/ai+1 的概率做对，则该次期望值为 1 / a i 1/a_i 1/ai ；若 a i < a i + 1 a_i < a_{i+1} ai<ai+1 ，则答案有 a i / a i + 1 a_i/a_{i+1} ai/ai+1 的概率在 [ 1 , a i ] [1,a_i] [1,ai] 里，而在里面有 1 / a i 1/a_i 1/ai 的概率做对，则该次期望值为 1 / a i + 1 1/a_{i+1} 1/ai+1。

int main() {
	double ans=0;
	for(int i=1; i<=n; i++) { //第i题的答案抄在了第i+1题上
		if(a[i]==a[i+1])ans+=1.0/a[i+1];
		if(a[i]>a[i+1])ans+=1.0/a[i];
		if(a[i]<a[i+1])ans+=1.0/a[i+1];
	}
}

例题2：未迭代的期望计算

例题链接

题目描述：抢红包系统：如果现在有 w 元钱，那么抢红包的金额就在 [ 0 , w ] [0,w] [0,w] 范围之内的某一个实数。现在发了一个 w 元的红包，n 个人抢，第 k 个人期望抢到多少钱？答案对分数 1 0 9 + 7 10^9+7 109+7 取模。
状态设置： f [ i ] f[i] f[i] 为第 i i i 个人抢红包的期望
初始状态： f [ 1 ] = w / 2 f[1]=w/2 f[1]=w/2
转移方程： f [ i ] = ( w − ∑ j = 1 i − 1 f [ j ] ) / 2 = w / 2 i f[i]=(w-\sum_{j=1}^{i-1}f[j])/2=w/2^i f[i]=(w−∑j=1i−1f[j])/2=w/2i

期望dp

期望dp的基础

前言：期望dp，顾名思义问的就是满足某条件的期望值（期望次数，概率）

常见的一般为一维的概率状态转移。
dp的形式
分为顺推和逆推
已知初始状态，向最终状态转移则为顺推
已知最终状态，求初始状态转移则为逆推
期望dp的常见解决套路：
1：通常使用逆推，设 f [ i ] f[i] f[i] 表示 i 到目标状态的期望次数，已知 f [ n ] = 0 f[n]=0 f[n]=0 求 f [ 1 ] f[1] f[1]
2：偶尔也是顺推，设 f [ i ] [ j ] f[i][j] f[i][j] 表示第 i 个物品选 j 个物品，或者有 i 个 A 物品和 j 个 B 物品的期望。
逆推刷表法： f [ i ] = ∑ p [ i → j ] × f [ j ] + w [ i → j ] f[i]=\sum p[i→j]\times f[j]+w[i→j] f[i]=∑p[i→j]×f[j]+w[i→j]，其中 p 表示转移的概率，w 表示转移对答案的贡献。
【注意】：对于可能会转移回自身的问题，如果强行顺推，会出现重复迭代的情况，因此期望 dp 用逆推最好。

债卷收集问题

例题1：一维筛子收集，求次数（逆推）

例题链接

题目描述： n 面的筛子，每次可以掷到一个面，求每面都掷到过的期望次数。
状态设置： f [ i ] f[i] f[i] 为已有 i 面，还需要的期望次数
初始状态： f [ n ] = 0 f[n]=0 f[n]=0
问题分析：有 i n \frac{i}{n} ni 的概率掷到已经掷到过的面，此后还要掷 f [ i ] f[i] f[i] 次；有 n − i n \frac{n-i}{n} nn−i 的概率掷到没有掷到过的面，此后还要掷 f [ i + 1 ] f[i+1] f[i+1] 次。
转移方程： f [ i ] = i n × f [ i ] + n − i n × f [ i + 1 ] + 1 f[i]=\frac{i}{n}\times f[i]+\frac{n-i}{n}\times f[i+1]+1 f[i]=ni×f[i]+nn−i×f[i+1]+1
移项得到： f [ i ] = f [ i + 1 ] + n n − i f[i]=f[i+1]+\frac{n}{n-i} f[i]=f[i+1]+n−in
目标状态： f [ 0 ] f[0] f[0]

int main(){
	f[n]=0;
	for(int i=n-1;i>=0;i--)f[i]=f[i+1]+1.0*n/(n-i);
	printf("%.2f\n",f[0]);  
}

例题2：一维邮票收集，求花费（逆推）

例题链接

题目描述： n 种邮票，每次等概率的抽到 n 种邮票中的任意一种，第 i 次抽需要 i 元钱，求每种邮票都收集到的期望花费。
状态设置： f [ i ] , g [ i ] f[i],g[i] f[i],g[i] 为已有 i 种邮票，还需要的期望次数和期望花费。
初始状态： f [ n ] = 0 , g [ n ] = 0 f[n]=0,g[n]=0 f[n]=0,g[n]=0
问题分析：
有 i n \frac{i}{n} ni 的概率掷到已经掷到过的面，此后还要掷 f [ i ] f[i] f[i] 次，还会花费 f [ i ] + g [ i ] + 1 f[i]+g[i]+1 f[i]+g[i]+1；有 n − i n \frac{n-i}{n} nn−i 的概率掷到没有掷到过的面，此后还要掷 f [ i + 1 ] f[i+1] f[i+1] 次，还会花费 f [ i + 1 ] + g [ i + 1 ] + 1 f[i+1]+g[i+1]+1 f[i+1]+g[i+1]+1。
转移方程：
f [ i ] = i n × f [ i ] + n − i n × f [ i + 1 ] + 1 f[i]=\frac{i}{n}\times f[i]+\frac{n-i}{n}\times f[i+1]+1 f[i]=ni×f[i]+nn−i×f[i+1]+1
g [ i ] = i n × ( f [ i ] + g [ i ] + 1 ) + n − i n × ( f [ i + 1 ] + g [ i + 1 ] + 1 ) g[i]=\frac{i}{n}\times (f[i]+g[i]+1)+\frac{n-i}{n}\times (f[i+1]+g[i+1]+1) g[i]=ni×(f[i]+g[i]+1)+nn−i×(f[i+1]+g[i+1]+1)
移项得到：
f [ i ] = f [ i + 1 ] + n n − i f[i]=f[i+1]+\frac{n}{n-i} f[i]=f[i+1]+n−in
g [ i ] = i n − i × ( f [ i ] + 1 ) + f [ i + 1 ] + g [ i + 1 ] + 1 g[i]=\frac{i}{n-i}\times(f[i]+1)+f[i+1]+g[i+1]+1 g[i]=n−ii×(f[i]+1)+f[i+1]+g[i+1]+1
目标状态： g [ 0 ] g[0] g[0]

int main() {
    f[n]=g[n]=0;
    for(int i=n-1;i>=0;i--){
    	f[i]=f[i+1]+1.0*n/(n-i);
    	g[i]=1.0*i/(n-i)*(f[i]+1)+f[i+1]+g[i+1]+1;
	}
	printf("%.2f",g[0]);
}

例题3：二维 bug 收集，求次数（逆推）

题目描述：一个计算机有 s 个系统，会产生 n 种 bug，一个程序员每天会发现一个 bug ，这个 bug 属于某个系统，属于某种 bug 。求发现 n 种 bug 且 s 个系统都找到 bug 的期望次数。
状态设置： f [ i ] [ j ] f[i][j] f[i][j] ：已经找到 i 种系统的 bug，j 种 bug，达到目标情况的期望次数
初始状态： f [ s ] [ n ] = 0 f[s][n]=0 f[s][n]=0
问题分析：
i , j i,j i,j 有 i s j n \frac{i}{s}\frac{j}{n} sinj 的概率转移到 f [ i ] [ j ] f[i][j] f[i][j]
i , j i,j i,j 有 s − i s j n \frac{s-i}{s}\frac{j}{n} ss−inj 的概率转移到 f [ i + 1 ] [ j ] f[i+1][j] f[i+1][j]
i , j i,j i,j 有 i s n − j n \frac{i}{s}\frac{n-j}{n} sinn−j 的概率转移到 f [ i ] [ j + 1 ] f[i][j+1] f[i][j+1]
i , j i,j i,j 有 s − i s n − j n \frac{s-i}{s}\frac{n-j}{n} ss−inn−j 的概率转移到 f [ i + 1 ] [ j + 1 ] f[i+1][j+1] f[i+1][j+1]
转移方程： f [ i ] [ j ] = f [ i ] [ j ] × i s j n + f [ i + 1 ] [ j ] × s − i s j n + f [ i ] [ j + 1 ] × i s n − j n + f [ i + 1 ] [ j + 1 ] × s − i s n − j n + 1 f[i][j]=f[i][j]\times \frac{i}{s}\frac{j}{n}+f[i+1][j]\times \frac{s-i}{s}\frac{j}{n}+f[i][j+1]\times \frac{i}{s}\frac{n-j}{n}+f[i+1][j+1]\times \frac{s-i}{s}\frac{n-j}{n}+1 f[i][j]=f[i][j]×sinj+f[i+1][j]×ss−inj+f[i][j+1]×sinn−j+f[i+1][j+1]×ss−inn−j+1
移项得到： f [ i ] [ j ] = ( f [ i + 1 ] [ j ] × ( s − i ) × j + f [ i ] [ j + 1 ] × i × ( n − j ) + f [ i + 1 ] [ j + 1 ] × ( s − i ) × ( n − j ) + s × n ) / ( s × n − i × j ) f[i][j]=(f[i+1][j]\times(s-i)\times j+f[i][j+1]\times i\times (n-j)+f[i+1][j+1]\times (s-i)\times (n-j)+s\times n)/(s\times n-i\times j) f[i][j]=(f[i+1][j]×(s−i)×j+f[i][j+1]×i×(n−j)+f[i+1][j+1]×(s−i)×(n−j)+s×n)/(s×n−i×j)

int main() {
	f[s][n]=0;
	for(int i=s; i>=0; i--) {
		for(int j=n; j>=0; j--) {
			if(i==s&&j==n)continue;
			f[i][j]=(f[i+1][j]*(s-i)*j+
			f[i][j+1]*i*(n-j)+
			f[i+1][j+1]*(s-i)*(n-j)+s*n)/(s*n-i*j);
		}
	}
}

通用公式：概率加权和

例题1：拓扑图上起点到终点的期望路径（逆推）

例题链接

题目描述： n 个点 m 条边的有向无环图，有边权 w i w_i wi 。每个点向其出点都有等概率的移动转移。求起点 1 到终点 n 的期望长度。
状态设置： f [ i ] f[i] f[i] 为 i 到终点的路径期望长度。
初始状态： f [ n ] = 0 f[n]=0 f[n]=0
转移方程： f [ u ] = ∑ 1 i n [ u ] × ( f [ v ] + e [ i ] . w ) f[u]=\sum \frac{1}{in[u]}\times (f[v]+e[i].w) f[u]=∑in[u]1×(f[v]+e[i].w)
目标状态： f [ 0 ] f[0] f[0]
由于最终状态已知，所以dp的过程是逆推，拓扑图也是反向建立

void bfs(){
	f[n]=0;
	q.push(n);
	while(!q.empty()){
		int u=q.front();
		for(int i=vex[u];i;i=e[i].next){
			int v=e[i].v;
			in[v]--;
			f[v]+=1.0/p[v]*(f[u]+e[i].w);
			if(in[v]==0)q.push(v);
		}
		q.pop();
	}
    printf("%.2f",f[1]);
}
int main(){
	long long m,u,v,w;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		add(v,u,w);
		in[u]++;
		p[u]++;
	}
	bfs();
}

例题2：不等概率转移到大于等于自己的一个点（逆推）

例题链接

题目描述：给定正整数 n，正整数序列 w 1 , w 2 , … … , w n w_1,w_2,……,w_n w1,w2,……,wn 。一个栈，初始时栈中仅有一个元素 1 。需要进行若干次如下的「调试」操作：每个时刻，设栈顶元素为 i，对于 i < = j < = n i<=j<=n i<=j<=n，有 w j ∑ k = i n w k \frac{w_j}{\sum_{k=i}^n w_k} ∑k=inwkwj 的概率将 j 入栈，且每个时刻恰好只会将一个 j 入栈，当栈顶为 n 时立刻停止调试。求最后 ( 1 , 2 , 3 … … n ) (1,2,3……n) (1,2,3……n) 都在栈中出现至少一次的概率，答案对 1 0 9 + 7 10^9+7 109+7 取模
方法1：顺推极限求概率（不建议）
状态设置： f [ i ] f[i] f[i] 为 1 − i 1-i 1−i 都在栈中的概率
初始状态： f [ 1 ] = 1 f[1]=1 f[1]=1
概率分析： i i i 有 w i s u f i \frac{wi}{sufi} sufiwi的概率转移到自身，有 w i + 1 s u f i \frac{w_{i+1}}{sufi} sufiwi+1的概率转移到 i + 1 i+1 i+1，自身 i 又有 w i s u f i \frac{wi}{sufi} sufiwi 的概率转移到自身，有 w i + 1 s u f i \frac{w_{i+1}}{sufi} sufiwi+1 的概率转移到 i + 1 i+1 i+1
则转移到 i + 1 i+1 i+1 的概率为： p [ i ] = ∑ j = 0 t p[i]=\sum_{j=0}^t p[i]=∑j=0t w i + 1 s u f i \frac{w_{i+1}}{sufi} sufiwi+1*( w i s u f i ) j \frac{w_{i}}{sufi})^j sufiwi)j
lim ⁡ t → + ∞ p [ i ] = w i + 1 s u f i − w i = w i + 1 s u f i + 1 \lim_{t\to+\infty}p[i]=\frac{w_{i+1}}{suf_{i}-w_i}=\frac{w_{i+1}}{suf_{i+1}} limt→+∞p[i]=sufi−wiwi+1=sufi+1wi+1
转移方程： f [ i + 1 ] = f [ i ] × w i + 1 s u f i + 1 f[i+1]=f[i]\times \frac{w_{i+1}}{suf_{i+1}} f[i+1]=f[i]×sufi+1wi+1，顺推即可
方法2：逆推公式求概率
状态设置： f [ i ] f[i] f[i] 为 1 − i 1-i 1−i 已经在栈中了， 1 − n 1-n 1−n 都在栈中的概率
初始状态： f [ n ] = 1 f[n]=1 f[n]=1
概率分析： i i i 有 w i s u f i \frac{w_{i}}{suf_{i}} sufiwi 的概率转移到 i i i ， i i i 有 w i + 1 s u f i \frac{w_{i+1}}{suf_{i}} sufiwi+1 的概率转移到 i + 1 i+1 i+1
转移方程： f [ i ] = f [ i ] × w i s u f i + f [ i + 1 ] × w i + 1 s u f i f[i]=f[i]\times \frac{w_{i}}{suf_{i}}+f[i+1]\times \frac{w_{i+1}}{suf_{i}} f[i]=f[i]×sufiwi+f[i+1]×sufiwi+1
移项得到： f [ i ] = f [ i + 1 ] × w i + 1 s u f i + 1 f[i]=f[i+1]\times \frac{w_{i+1}}{suf_{i+1}} f[i]=f[i+1]×sufi+1wi+1，逆推即可

#include<iostream>
using namespace std;

const int N=1e6+100;
const long long mod=1e9+7;

long long hou[N],w[N],f[N];

long long x,y;

void ex_gcd(long long a,long long b) {
	if(b==0) {
		x=1;
		y=0;
		return;
	}
	ex_gcd(b,a%b);
	long long t=x;
	x=y;
	y=t-a/b*y;
}

int main() {
	int n;
	cin>>n;
	for(int i=1; i<=n; i++)scanf("%lld",&w[i]);
	for(int i=n; i>=1; i--)hou[i]=hou[i+1]+w[i];

	f[1]=1;
	for(int i=1; i<n; i++) {
		ex_gcd(hou[i]-w[i],mod);
		x=(x%mod+mod)%mod;
		
		f[i+1]=f[i]*w[i+1]%mod*x%mod;
	}
	cout<<f[n];
	return 0;
}

例题3：dp 加了个期望（顺推）

例题链接

这其实并不能算是一道期望dp，只能说与期望有关
题目描述： n 个时间段上课，m 个申请换教室机会。如果第 i 个时间不换教室，那么第 i 个时间段会在 d i d_i di 教室上课；如果换了，那么第 i 个时间段会在 c i c_i ci 教室上课。申请第 i 时间段换教室有 p i p_i pi 的概率换成功。每个申请的概率相互独立，并且只能在最初没上课前递交申请。教室构成一张 v v v 个点 e e e 条边的无向连通图，边权为 w j w_j wj。问在使用换教室申请不超过 m m m 个的情况下，最小期望路径。
状态设置： f [ i ] [ j ] f[i][j] f[i][j] 前 i 个时间段，使用 j 个换教室机会，的最小期望路径。
。。。失败，发现 dp 过程与上一个时间段的位置有关，而我们无法确定。
状态设置： f [ i ] [ j ] [ 0 / 1 ] f[i][j][0/1] f[i][j][0/1] ：前 i 个时间段，使用 j 个换教室机会，第 i 次不换与换下，的最小期望路径。
转移方程：
不换： f [ i ] [ j ] [ 0 ] = m i n ( f [ i − 1 ] [ j ] [ 0 ] + d i s ( d i − 1 , d i ) , f [ i − 1 ] [ j ] [ 1 ] + d i s ( c i − 1 , d i ) × p i − 1 + d i s ( d i − 1 , d i ) × ( 1 − p i − 1 ) ) f[i][j][0]=min(f[i-1][j][0]+dis(d_{i-1},d_i),f[i-1][j][1]+dis(c_{i-1},d_i)\times p_{i-1}+dis(d_{i-1},d_i)\times(1-p_{i-1})) f[i][j][0]=min(f[i−1][j][0]+dis(di−1,di),f[i−1][j][1]+dis(ci−1,di)×pi−1+dis(di−1,di)×(1−pi−1))
换： f [ i ] [ j ] [ 1 ] = m i n ( f [ i − 1 ] [ j − 1 ] [ 0 ] + p i × d i s ( d i − 1 , c i ) + ( 1 − p i ) × d i s ( d i − 1 , d i ) , f [ i − 1 ] [ j − 1 ] [ 1 ] + 四种距离的期望，懒得打了 ) f[i][j][1]=min(f[i-1][j-1][0]+p_i\times dis(d_{i-1},c_i)+(1-p_i)\times dis(d_{i-1},d_i),f[i-1][j-1][1]+四种距离的期望，懒得打了) f[i][j][1]=min(f[i−1][j−1][0]+pi×dis(di−1,ci)+(1−pi)×dis(di−1,di),f[i−1][j−1][1]+四种距离的期望，懒得打了)
初始值： f [ 1 ] [ 0 ] [ 0 ] = f [ 1 ] [ 1 ] [ 1 ] = 0 , f [ i ] [ 0 ] [ 0 ] = f [ i − 1 ] [ 0 ] [ 0 ] + d i s ( d i − 1 , d i ) f[1][0][0]=f[1][1][1]=0,f[i][0][0]=f[i-1][0][0]+dis(d_{i-1},d_i) f[1][0][0]=f[1][1][1]=0,f[i][0][0]=f[i−1][0][0]+dis(di−1,di)

#include<bits/stdc++.h>
using namespace std;
const int N=2005;
int d[N],c[N];
double f[N][N][2],p[N],dis[N][N];

int main(){
	int n,m,v,e,x,y;
	double w;
	cin>>n>>m>>v>>e;
	for(int i=1;i<=n;i++)cin>>d[i];
	for(int i=1;i<=n;i++)cin>>c[i];
	for(int i=1;i<=n;i++)cin>>p[i];
	
	for(int i=1;i<=v;i++){
		for(int j=1;j<=v;j++){
			if(i!=j)dis[i][j]=1e9;
		} 
	}
    for(int i=1;i<=e;i++){
    	cin>>x>>y>>w;
    	dis[x][y]=dis[y][x]=min(dis[x][y],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=0;i<=n;i++){
		for(int j=0;j<=m;j++){
			f[i][j][0]=f[i][j][1]=1e9;
		}
	}
	f[1][0][0]=0;
	f[1][1][1]=0;
	for(int i=2;i<=n;i++)f[i][0][0]=f[i-1][0][0]+dis[d[i-1]][d[i]]; 
	for(int i=2;i<=n;i++){
		for(int j=1;j<=min(i,m);j++){
			f[i][j][0]=min(f[i-1][j][0]+dis[d[i-1]][d[i]],f[i-1][j][1]+p[i-1]*dis[c[i-1]][d[i]]+(1-p[i-1])*dis[d[i-1]][d[i]]);
			f[i][j][1]=f[i-1][j-1][0]+p[i]*dis[d[i-1]][c[i]]+(1-p[i])*dis[d[i-1]][d[i]];
			f[i][j][1]=min(f[i][j][1],f[i-1][j-1][1]+p[i]*p[i-1]*dis[c[i-1]][c[i]]+(1-p[i])*p[i-1]*dis[d[i]][c[i-1]]+p[i]*(1-p[i-1])*dis[c[i]][d[i-1]]+(1-p[i])*(1-p[i-1])*dis[d[i-1]][d[i]]);
		}
	}
	double ans=1e9;
	for(int j=0;j<=min(n,m);j++)ans=min(ans,min(f[n][j][0],f[n][j][1]));
	printf("%.2lf",ans);
	return 0;
}

例题4：

例题链接

题目描述：对于一个只包含 o,x 的字符串，其计算分数的方式为： ∑ ( 连续 o 的个数 ) 2 \sum (连续 o 的个数)^2 ∑(连续o的个数)2，例如：ooxoooxo： 2 × 2 + 3 × 3 + 1 × 1 2\times2+3\times 3+1\times 1 2×2+3×3+1×1。现有一个包含 o,x,? 的字符串，? 有 50% 概率是 o ，有 50% 概率是 x 。问期望分数。
状态设置： f [ i ] f[i] f[i]：只有前 i 个字符时的期望分数
初始状态： f [ 0 ] = 0 f[0]=0 f[0]=0
问题分析：
设 len 为到第 i-1 个字符的期望连续 o 数量。
若第 i 个字符为 x ，则 f [ i ] = f [ i − 1 ] ， l e n = 0 f[i]=f[i-1]，len=0 f[i]=f[i−1]，len=0
若第 i 个字符为 o，则 f [ i ] = f [ i − 1 ] + ( l e n + 1 ) 2 − l e n 2 ， l e n + + f[i]=f[i-1]+(len+1)^2-len^2，len++ f[i]=f[i−1]+(len+1)2−len2，len++
若第 i 个字符为 ?，o,x 概率各位 0.5 ，那么期望就是两种情况的均值
则 f [ i ] = ( f [ i − 1 ] + ( l e n + 1 ) 2 − l e n 2 + f [ i − 1 ] ) / 2 ， l e n = ( l e n + 1 + 0 ) / 2 f[i]=(f[i-1]+(len+1)^2-len^2+f[i-1])/2，len=(len+1+0)/2 f[i]=(f[i−1]+(len+1)2−len2+f[i−1])/2，len=(len+1+0)/2

int main() {
	int i;
	double len=0;
	for(i=0; s[i]!='\0'; ) {
		switch(s[i++]) {
			case 'x': {
				len=0;
				f[i]=f[i-1];
				break;
			}
			case 'o': {
				f[i]=f[i-1]+2*len+1;
				len++;
				break;
			}
			case '?': {
				f[i]=f[i-1]+len+0.5;
				len=(len+1)/2;
				break;
			}
		}
	}
	printf("%.4lf",f[i]);
}

等概率（ ∑ / ∑ \sum/\sum ∑/∑）

例题1：拓扑图上的所有路径期望路径长度（ ∑ / ∑ \sum/\sum ∑/∑）

例题链接

题目描述： n 个点 m 条边的有向无环图。可能存在重边。随机选择一条路径，选择所有路径的概率相等。路径的起点和终点可以相同。定义一条路径的长度为经过的边数，那么路径长度的期望是多少，答案对 998244353 取模。
问题分析： a n s = ∑ v i / c n t ans=\sum v_i/cnt ans=∑vi/cnt，其中 ∑ v i \sum v_i ∑vi 为所有路径之和， c n t cnt cnt 为路径数量。
状态设置： f [ i ] f[i] f[i]：终点为 i 的所有路径的长度之和， g [ i ] g[i] g[i]：终点为 i 的路径数量
初始值： f [ i ] = 0 , g [ i ] = 1 f[i]=0,g[i]=1 f[i]=0,g[i]=1
转移方程： f [ v ] + = f [ u ] + g [ u ] ， g [ v ] + = g [ u ] f[v]+=f[u]+g[u]，g[v]+=g[u] f[v]+=f[u]+g[u]，g[v]+=g[u]
目标： ∑ f [ i ] / ∑ g [ i ] \sum f[i]/\sum g[i] ∑f[i]/∑g[i]

void bfs(){
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=vex[u];i;i=e[i].next){
			int v=e[i].v;
			in[v]--;
			f[v]=(f[v]+f[u]+g[u])%mod;
			g[v]=(g[v]+g[u])%mod;
			if(in[v]==0)q.push(v);
		} 
	}
} 
int main(){
	int n,m,u,v;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		add(u,v);
		in[v]++;
	}
	for(int i=1;i<=n;i++){
		if(in[i]==0)q.push(i);
		g[i]=1;
	}
	bfs();
	long long a=0,b=0;
	for(int i=1;i<=n;i++){
		a=(a+f[i])%mod,b=(b+g[i])%mod;
	}
	cout<<a*ksm(b,mod-2)%mod; 
	return 0;
}

例题2：等概率转移到比自己小的一个点（ ∑ / ∑ \sum/\sum ∑/∑）

例题链接

题目描述：给定一个 n 行 m 列的矩阵，每个位置都有权值 a i j a_{ij} aij 。给定出发点 s（x,y），每次都等概率的跳到比当前点权值低的点中的任意一个，并得到得分（两个点距离的平方）。问期望得分为多少。
问题分析：先将 n,m 个点的权值从小到大排个序，将二维变为一维。
状态设置： f [ i ] f[i] f[i] ：从 i 点开始的期望得分。
初始状态： f [ 1 ] = 0 f[1]=0 f[1]=0，其中 t t t 为终点，即权值最低点。
目标状态： f [ s ] f[s] f[s]
转移方程： f [ i ] = ( ∑ a [ j ] < a [ i ] f [ j ] + d i s ( i , j ) ) / c n t f[i]=(\sum_{a[j]<a[i]}f[j]+dis(i,j))/cnt f[i]=(∑a[j]<a[i]f[j]+dis(i,j))/cnt
如何计算 ∑ d i s ( i , j ) \sum dis(i,j) ∑dis(i,j)： ∑ ( x i − x j ) 2 + ( y i − y j ) 2 = ∑ x j 2 + ∑ y j 2 − 2 x i ∑ x j − 2 y i ∑ y j + c n t × x i 2 + c n t × y i 2 \sum (x_i-x_j)^2+(y_i-y_j)^2=\sum x_j^2+\sum y_j^2-2x_i\sum x_j-2y_i\sum y_j+cnt\times x_i^2+cnt\times y_i^2 ∑(xi−xj)2+(yi−yj)2=∑xj2+∑yj2−2xi∑xj−2yi∑yj+cnt×xi2+cnt×yi2

#include<bits/stdc++.h>
using namespace std;
const int N=1010*1010;
struct E{
	long long v,x,y;
}a[1010*1010];
long long cnt=0,g[N][5],pre[N],b[1010][1010],f[N];
long long mod=998244353;
int cmp(E a,E b){
	return a.v<b.v;
}
long long ksm(long long a,long long b){
	long long res=1;
	while(b){
		if(b&1)res=res*a%mod;
		a=a*a%mod;
		b=b/2;
	}
	return res;
}
int main(){
	int n,m,x,y,v;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>v;
		    a[++cnt].v=v;
		    a[cnt].x=i;
		    a[cnt].y=j;
		}
	}
	cin>>x>>y;
	
	sort(a+1,a+cnt+1,cmp);
	
	for(int i=1;i<=cnt;i++){
		g[i][1]=(g[i-1][1]+a[i].x*a[i].x)%mod;
		g[i][2]=(g[i-1][2]+a[i].y*a[i].y)%mod;
		g[i][3]=(g[i-1][3]+a[i].x)%mod;
		g[i][4]=(g[i-1][4]+a[i].y)%mod;
	}
	
	int top=1,preid;
	while(a[top].v==a[1].v){
		f[top]=0;
		if(a[top].x==x&&a[top].y==y){
			cout<<f[top];
			return 0;
		}
		top++; 
	}
	for(int i=top;i<=cnt;i++){
		if(a[i].v!=a[i-1].v)preid=i-1;
	    f[i]=pre[preid]+g[preid][1]+g[preid][2]-2*a[i].x*g[preid][3]-2*a[i].y*g[preid][4]+preid*a[i].x%mod*a[i].x%mod+preid*a[i].y%mod*a[i].y%mod;
	    f[i]=(f[i]%mod+mod)%mod;
	    f[i]=f[i]*ksm(preid,mod-2)%mod;
	    pre[i]=(pre[i-1]+f[i])%mod;
	    if(a[i].x==x&&a[i].y==y){
	    	cout<<f[i];
	    	return 0;
		}
	}
	return 0;
}

期望与期望dp/概率dp关于期望简单求期望期望dp

关于期望

简单求期望

例题1：期望独立单独计算

例题2：未迭代的期望计算

期望dp

期望dp的基础

债卷收集问题

例题1：一维筛子收集，求次数（逆推）

例题2：一维邮票收集，求花费（逆推）

例题3：二维 bug 收集，求次数（逆推）

通用公式：概率加权和

例题1：拓扑图上起点到终点的期望路径（逆推）

例题2：不等概率转移到大于等于自己的一个点（逆推）

例题3：dp 加了个期望（顺推）

例题4：

等概率（ ∑ / ∑ \sum/\sum ∑/∑）

例题1：拓扑图上的所有路径期望路径长度（ ∑ / ∑ \sum/\sum ∑/∑）

例题2：等概率转移到比自己小的一个点（ ∑ / ∑ \sum/\sum ∑/∑）

继续阅读

查找算法之二分查找查找算法之二分查找

查找算法学习之二分查找（Python版本）——BinarySearch

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

Command Network(POJ 3164)---定根最小树形图模板题题目描述输入格式输出格式输入样例输出样例分析源程序

开源低带宽语音编解码器

241 Different Ways to Add Parentheses（C代码版）

【趋高机器视觉】机器视觉技术原理解析及解决方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制规程及特点4． CSMA/CD协议5． CSMA/CD的优点6．结束语

极大似然法(ML)与最大期望法(EM)

C++ 第十五周报告1--《冒泡法排序》

HDU 1160 FatMouse's Speed （记录路径的最长上升子序列）

笔试面试题目：滑动窗口(二)

数据结构与算法（27）——排序（二）

Dijkstra--简易版（最短路径）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

hdu7108哈希