一些定义及性质：
1.$P(A)$表示事件A发生的概率，$E(A)$表示事件A的期望。
2.独立事件：若事件A与B满足$P(AB)=P(A) imes P(B)$，则称A与B互相独立。同时它们也满足$E(AB)=E(A) imes E(B)$。
3.期望的线性性：对于任意事件A与B，均有$E(A+B)=E(A)+E(B)$。
证明：
$E(X+Y)=sum sum {P(x=i且y=j) imes(i+j)}$
$=sum sum {P(x=i且y=j) imes i}+sum sum {P(x=i且y=j) imes j}$
$=sum {i imes sum P(x=i且y=j)}+sum {j imes sum P(y=j且x=i)}$
$=sum {i imes P(x=i)}+sum {j imes P(y=j)}$
$=E(X)+E(Y)$
4.期望的本质就是算概率。
5.概率的可加性：对于若干个两两互不相容的事件，$P(这些事件均发生)=sum P(其中某个事件发生)$
常用技巧——前缀和技巧：对于离散变量x，$P(x=k)=P(xleq k)-P(xleq k-1)$。
例1：n个元素每个从1-s随机取值，求这些元素中最大值的期望。
解：
令S为最终答案，X为元素中的最大值。
由期望的线性性可得$E(S)=sum E(X)=sum {P(X=i) imes i}$
由于$P(X=i)=P(Xleq i)-P(Xleq {i-1})=(frac{i}{s})^{n}-(frac{i-1}{s})^{n}$
所以$E(S)=sum {P(X=i) imes i}=sum {i imes[(frac{i}{s})^{n}-(frac{i-1}{s})^{n}]}$
例2：每次操作发生概率为p的事件期望$frac{1}{p}$次操作后发生。
证：
令S为最终答案，X为该事件在第X次发生。
由期望的线性性可得$E(S)=sum E(X)=sum {P(X=i) imes i}$
由于$P(X=i)=P(Xgeq i)-P(Xgeq {i-1})=(1-p)^{i-1}-(1-p)^{i}$
所以$E(S)=sum {P(X=i) imes i}=sum {[(1-p)^{i-1}-(1-p)^{i}] imes i}=sum_{i=0}^{infty}{(1-p)^{i}}=frac{1}{p}$
结论：$E(X)=sum {P(Xgeq i)}$
证明1：同上。
证明2：
$E(X)=sum_{i=1}^{infty}{P(X=i) imes i}=sum_{i=1}^{infty}{P(X=i) imes sum_{j=1}^{i}1}=sum_{j=1}^{infty}{1 imes {sum_{i=j}^{infty}P(X=i)}}=sum {P(Xgeq i)}$
拿球问题：
1.有n个球1-n，求从里面拿m次球不放回的期望点数之和。
解：
令S表示最终答案，Xi表示i对答案的贡献。
由期望的线性性可得$E(S)=sum E(Xi)=sum {P(Xi=i) imes i}$
由于$P(Xi=i)=frac{C_{n-1}^{m-1}}{C_n^m}=frac{m}{n}$
所以$E(S)=sum {P(Xi=i) imes i}=sum {frac{m}{n} imes i}=frac{m}{n} imes sum i=frac{m imes(n+1)}{2}$
2.有n个球1-n，求从里面拿m次球放回的期望点数之和。
解：显然$ans=frac{1+n}{2} imes m=frac{m imes(n+1)}{2}$
3.有n个球1-n，每次从里面拿一个球，有pi的概率放回i个与这个球相同点数的球。求拿m次的期望点数之和。
解：
令S表示最终答案，Xi表示i对答案的贡献，Yi表示i被拿了几次。显然有$E(Xi)=E(Yi) imes i$。
由期望的线性性可得$E(S)=sum E(Xi)=sum {E(Yi) imes i}$
由于一共拿了m次，易得$sum Yi=m$
所以$sum E(Yi)=E(m)=m$
由于每个球的概率均等，所以每个球在这个问题里是等价的，所以$E(Y1)=E(Y2)=cdots=E(Yn)=frac{m}{n}$
所以$E(S)=sum {E(Yi) imes i}=sum {frac{m}{n} imes i}=frac{m imes(n+1)}{2}$
结论：拿球问题中只要保证每个球等价，那么放不放回去，放回去几个对期望答案没有影响。
游走问题：（每次等概率选一条边走出去）
1.求在一条链上从一端随机游走到另一端的期望步数。
解：
令S表示最终答案，Xi表示从i第一次走到i+1的步数。
由期望的线性性可得$E(S)=sum E(X_{i})$
由于$E(X_{i})=0.5 imes1+0.5 imes[1+E(X_{i-1})+E(X_{i})]$和$E(X1)=1$，可以解出$E(X_{i})=E(X_{i-1})+2$
所以$E(S)=sum E(X_{i})=(n-1)^2$
2.求在完全图上从一个点走到另一个点的期望步数。
解：相当于每次操作有$frac{1}{n-1}$的概率成功，于是需要$n-1$步。
3.求在2n个点的完全二分图上从一个点走到另一个点的期望步数。
解：
令A表示两个点在同侧的期望步数，B表示两个点在异侧的期望步数。
则有$B=frac{1}{n}+frac{n-1}{n} imes (1+A),A=1+B$
解得$A=2n,B=2n-1$
4.求在菊花图上从一个点走到另一个点的期望步数。
解：
令A表示从一个叶子走到另一个叶子的期望步数，B表示从根走到一个叶子的期望步数。
则有$A=1+B,B=frac{1}{n-1}+frac{n-2}{n-1} imes (1+A)$
解得$B=2n-3,A=2n-2$
5.求在一棵树上从一个点随机游走到另一个点的期望步数。
解：
首先将两个点中的其中一个点作为根，然后树形dp。
设$g(u)$表示从u第一次走到u的父亲的期望步数，$d(u)$表示u点的度数，$v$表示u的儿子。
则有$g(u)=frac{1}{d(u)}+sum {frac{1}{d(u)} imes (1+g(v)+g(u))}$
解出答案后dp出整棵树的答案，然后根据期望的线性性，将从目标点到根的路径上所有$g(x)$求和即可。
6.构造一个200个点的图，使得存在两个点之间随机游走的期望步数$geq 10^6$
解：
考虑到一条链上的$E(1)=1$而$E(S)=(n-1)^2$，发现$10^6$大约是$n^3$级别，所以只需要将$E(1)$构造到n级别即可。
那么显然可以构造一个完全图加一条链。期望步数$n^3$步。
经典问题：
1.每次随机一个1-N的整数，求期望几次凑齐所有数。
解：
令S为最终答案，Xi为从凑齐i-1个数到凑齐i个数的步数。
由期望的线性性可得$E(S)=sum E(Xi)$
考虑$E(Xi)$，发现每次操作能够多凑出一个数的概率为$frac{n-i+1}{n}$
根据“概率为p的事件发生的期望次数为$frac{1}{p}”$，得到$E(Xi)=frac{n}{n-i+1}$
所以$E(S)=sum frac{n}{n-i+1}$
2.随机一个长度为n的排列p，求p[1]~p[i]中p[i]是最大的数的概率。
解：在大小关系上1-p的每个前缀和一个1-i的排列是等价的。由于1-i的排列i出现在每一位上的概率均等，所以所求概率为$frac {1}{i}$
3.求上一题中i的个数的平方的期望。（平方的期望≠期望的平方）
解：
令S为最终答案，Xi为i是不是前i个数中最大的那个数。
可得$E(S^2)=E((sum{Xi})^2)=E(sum_{i≠j}{XiXj}+sum {Xi^2})$
由期望的线性性可得$E(S^2)=sum_{i≠j}{E(XiXj)}+sum{E(Xi^2)}$
考虑一组i与j，容易发现$P(XiXj)$为i是且j是max的概率，由于i与j独立可以得到$P(XiXj)=frac{1}{i imes j}$
那么$sum_{i≠j}{E(XiXj)}=sum_{i≠j}{P(XiXj)}=sum_{i≠j}{frac{1}{i imes j}}$
所以$E(S^2)=sum_{i≠j}{frac{1}{i imes j}}+sum{frac{1}{i}}$
4.求排列p中i在j后面的概率（i≠j）。
解：由于i在j后面的概率和j在i后面的概率是一样的，并且和为1，所以概率为$frac{1}{2}$
5.求排列p中包含W[1]~W[m]的概率。
解：
做法一：包含的情况总数为$C_n^{m} imes(n-m)!=frac{n!}{m!(n-m)!} imes (n-m)!=frac{n!}{m!}$，情况总数为$n!$
于是概率为$frac{frac{n!}{m!}}{n!}=frac{1}{m!}$
做法二：发现包含W的概率与包含W的任一排列的概率均相等。而只要W合法则p中一定包含W的某个排列。故概率和为1，每种的概率为$frac{1}{m!}$
6.求排列p中包含W[1]~W[m]且连续的概率。
解：简单组合计数。答案为$frac{(n-m+1) imes (n-m)!}{n!}$
7.有n堆石头，每堆有ai个，每次随机选一个石头然后把那一整堆扔了，求第1堆期望第几次被扔。
解：
令Xi为i期望第几次被扔。
根据排名的定义，我们有$Xi=sum{Xjleq Xi}$，其中$Xjleq Xi$是一个01状态。
由期望的线性性可得$E(X1)=sum{E(Xi<Xj)}+1=sum{P(Xi<X1)}+1$
考虑一组i与j，显然有$P(Xi<Xj)=frac{ai}{ai+aj}$
所以$E(X1)=sum{frac{ai}{ai+a1}}+1$
8.有n个数，每次操作删除一个，并把两边的序列拼回去，求i和j在过程中相邻的概率。
解：
问题可以转化为有一个排列p，求i和j之间的数都小于等于i和j的概率。
那么只考虑i到j这一段，得到概率为$frac{2 imes (j-i-1)!}{(j-i+1)!}=frac{2}{(j-i+1)(j-i)}$
9.随机一个01串，假设每一位有p的概率为1，定义x是所有连续的1的长度的平方之和，求x的期望。
解：
逐位dp，我们设$Y_i$表示1-i最后一段连续1的长度，$X_i$表示1-i所求答案。
考虑位置i，若该位为0：$Y_{i}=0,X_{i}=X_{i-1}$
若该位为1：$Y_{i}=Y_{i-1}+1,X_{i}=X_{i-1}-(Y{i-1}^2)+((Y_{i-1}+1)^2)=X_{i-1}+2Y_{i-1}+1$
由期望的线性性可得
$E(X_{i})=p imes E(X_{i-1}+2Y_{i-1}+1)+(1-p) imes E(X_{i-1})=p imes (E(X_{i-1})+2E(Y_{i-1})+1)+(1-p) imes E(X_{i-1})$
$E(Y_{i})=p imes (1+E(Y_{i-1}))+(1-p) imes 0=p imes (1+E(Y_{i-1}))$
按位求解即可。
10.给定一棵树，将所有边随机后依次插入，求u,v期望什么时候联通。
解：
考虑枚举u到v的边最后一次出现的位置i，分别统计。
记$dis(u,v)=k$，由期望的线性性得$E(S)=sum E(Xi)=sum_{i=k}^{n-1}{frac{C_{i-1}^{k-1} imes k! imes (n-1-k)!}{(n-1)!}} imes i$
11.给定1-n这些数，每次随机选一个数并删掉所有这个数的约数，求期望几次删完。
解：
将问题转化为：每次选一个数，如果它没被标黑就标黑它的所有约数并删掉它，否则直接删掉它，求期望删到几个没被标黑的数。
（目标：从一次操作删除多个转化为一次操作删除一个，以使用期望的线性性）
令S为最终答案，Xi为i是否有贡献。
由期望的线性性得$E(S)=sum E(Xi)=sum P(Xi)$
发现i有贡献相当于i的所有倍数都在它后面被删。
根据“一个排列m个元素的集合中第m个元素排在第一位的概率是$frac{1}{m}$”可以得到$P(Xi)=frac{1}{lfloor{frac{n}{i}} floor}$
那么得到$E(S)=sum {frac{1}{lfloor{frac{n}{i}} floor}}$
一些练习题：
1.一个序列每次删一个数，贡献是左右两数之积，求期望贡献和。
解：
令S为最终答案，Xi,j表示i位置与j位置是否有贡献。
由期望的线性性得$E(S)=sum E(Xi,j) imes Wi imes Wj=sum P(Xi,j) imes Wi imes Wj$
考虑i与j有贡献则需要i和j中间的所有元素都在i和j之前被删。
根据简单组合计数得到$P(Xi,j)=frac{2}{(j-i+1)(j-i)}$
那么$E(S)=sum {frac{2}{(j-i+1)(j-i)} imes Wi imes Wj}$
2.三个数中间那个最大的概率是$frac{1}{3}$（
3.有n个数，每次随机选两个数合成一个数，收益是两数之和，求期望收益。
解：
令S为最终答案，Xi为i被选的次数。由期望的线性性得$E(S)=sum E(Xi) imes Ai$
考虑第k次操作相当于从n-k+1个团中随机选择两个团。
那么显然在这次操作中i所在的团被选中的概率是$frac{2}{n-k+1}$
所以$E(Xi)=sum_{j=1}^{n-1}{frac{2}{n-j+1}}$
得到$E(S)=sum {Ai imes sum_{j=1}^{n-1}{frac{2}{n-j+1}}}$
4.给出一棵树，每次选一个白点将其子树里所有点染黑，求期望几次染黑整个树。
解：
将问题转化为：每次选一个点，如果它没被标记就标记它的子树并将它删除，否则直接删除，求期望选到几个没被标记的点。（同“经典问题11”）
令S为最终答案，Xi为i是否有贡献。
由期望的线性性得$E(S)=sum E(Xi)=sum P(Xi)$
发现若i有贡献则需要i的祖先都在它后面。
得到$P(Xi)=frac{1}{dep(i)}$，所以$E(S)=sum frac{1}{dep(i)}$
解：
令S为最终答案，Xi表示从第i-1天到第i天的距离。
由期望的线性性得$E(S)=sum E(Xi)$
容易发现第i-1天到第i天的距离期望与：i是否申请，i-1是否申请有关。
于是考虑设$dp(i,j,0/1)$表示前i门课，已经用了j次申请机会，第i门课是否申请的最短期望距离之和。
那么由期望的线性性得
$dp(i,j,0)=min(dp(i-1,j,0)+E(i不申请i-1不申请),dp(i-1,j,1)+E(i-1申请i不申请))$
$dp(i,j,1)=min(dp(i-1,j-1,0)+E(i申请i-1不申请),dp(i-1,j-1,1)+E(i申请i-1申请))$
是否申请的期望分类讨论一下即可。
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #define maxn 2005 #define maxm 505 #define inf 0x7fffffff #define ll long long #define rint register int using namespace std; int N,M,V,E,c[maxn],d[maxn]; double k[maxn],dp[maxn][maxn][2],dis[maxm][maxm]; inline int read(){ rint x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } inline void Floyd(){ for(rint k=1;k<=V;k++) for(rint i=1;i<=V;i++) for(rint j=1;j<=V;j++) if(dis[i][j]>dis[i][k]+dis[k][j]) dis[i][j]=dis[i][k]+dis[k][j]; return; } int main(){ //freopen("testdata.in","r",stdin); //freopen("1.out","w",stdout); N=read(),M=read(),V=read(),E=read(); for(rint i=1;i<=N;i++) c[i]=read(); for(rint i=1;i<=N;i++) d[i]=read(); for(rint i=1;i<=N;i++) scanf("%lf",&k[i]); for(rint i=1;i<=V;i++) for(rint j=1;j<=V;j++) dis[i][j]=1e9; for(rint i=1;i<=V;i++) dis[i][i]=0; for(rint i=1;i<=E;i++){ rint u=read(),v=read(),w=read(); dis[u][v]=min(dis[u][v],(double)w); dis[v][u]=min(dis[v][u],(double)w); } Floyd(); for(rint i=0;i<=N;i++) for(rint j=0;j<=M+3;j++) dp[i][j][0]=dp[i][j][1]=1e9; dp[1][0][0]=dp[1][1][1]=0; for(rint i=2;i<=N;i++) for(rint j=0;j<=M;j++){ dp[i][j][0]=min(dp[i-1][j][0]+dis[c[i-1]][c[i]],dp[i-1][j][1]+k[i-1]*(dis[d[i-1]][c[i]])+(1.0-k[i-1])*dis[c[i-1]][c[i]]); if(j) dp[i][j][1]=min(dp[i-1][j-1][0]+k[i]*dis[c[i-1]][d[i]]+(1.0-k[i])*dis[c[i-1]][c[i]],dp[i-1][j-1][1]+k[i]*k[i-1]*dis[d[i-1]][d[i]]+k[i]*(1.0-k[i-1])*dis[c[i-1]][d[i]]+(1.0-k[i])*k[i-1]*dis[d[i-1]][c[i]]+(1.0-k[i])*(1.0-k[i-1])*dis[c[i-1]][c[i]]); } double ans=1e9; for(rint j=0;j<=M;j++) ans=min(ans,min(dp[N][j][0],dp[N][j][1])); printf("%.2lf ",ans); return 0; }
区间交：定义一种随机生成区间的方法：L=Random(1,N),R=Random(L,N)。现在这样随机出两个区间，求他们相交的概率。
解：
发现相交的概率不是那么的好求，不如求不相交的概率后进行容斥。
设两个区间分别为$[l1,r1]$与$[l2,r2]$，在这里我们强行规定$l1leq l2$
直接计数不太方便，考虑枚举l2，求出有多少r1会出现在l2之前。
设f(r)表示生成一个右端点$leq$ r的区间的概率。
则不相交的概率就为$sum_{i=2}^{N}{frac{f(i-1)}{N}} imes 2$
再设g(r)表示生成一个右端点=r的区间的概率，容易发现$g(r)=frac{sum_{l=1}^{r}{frac{1}{N-l+1}}}{N}$
那么$f(r)=sum_{i=1}^{r}{g(i)}$，所以$ans=1-(sum_{i=2}^{N}{frac{sum_{r=1}^{i-1}{g(r)}}{N}}) imes 2$
Deep Dark Forest：给定一棵树，每条边的长度有$frac{1}{2}$概率是0，$frac{1}{2}$概率是1，求直径长度的期望。
解：
首先考虑一个结论：对于任意的一棵树，从Root开始找距离它的最远点L，再从L开始找距离它的最远点R，则$[L,R]$一定是树的一条直径。
证明的话画个图就差不多清楚了。那么我们令X为这棵树直径的长度。
由期望线性性得$E(X)=sum P(X=i) imes i$
由“常用技巧”中的结论得到$E(X)=sum_{i=1}^{n}{P(X>=i)}=sum_{i=1}^{n}{1-P(X<i)}$
由于直径的lca可能是任一节点，所以考虑树形dp。
设$dp(i,j)$表示在以i为根的子树中，这个子树的深度的长度为j，满足直径<K（K是当前枚举的值）的概率。
若转移顺序不好会增加复杂度，那么考虑设计一个转移顺序。
我们不妨依次考虑u的所有儿子v，那么再枚举处理到v之前的深度j（满足j+k<K）
就可以得到$dp(u,max(j,k))=dp(u,j)+0.5 imes dp(v,k)+0.5 imes dp(v,k-1)$
初始状态为每个叶节点的$dp(u,0)=1$，复杂度$O(n^3)$
球染色：给定初始每个球的颜色c[1]~c[n]，每次操作选取i与j并令c[i]=c[j]，求期望多少步把所有球染成同一种颜色。
解：
考虑一个经典技巧：枚举最后的颜色使得原序列变为一个01串。
令S为最终答案，Xi为把所有球染成颜色ci的步数，由期望的线性性得$E(S)=sum E(Xi)$
一个01串中的操作共有4种：选择00，11，01，10。我们的目标是将原串变为全1。
那么设Yi表示从i-1个1变到i个1的步数。则$E(Xi)=sum E(Yi)$
考虑前两种操作对1的个数没有影响，第三种操作会增加一个1，第四种操作会减少一个1。
那么$E(Y_i)=0.5 imes(1+E(Y_i))+0.25 imes 1+0.25 imes(1+E(Y_{i-1}+E(Y_i)))$，递推即可。
当然还可以设Yi表示从i个1变到n个1的步数。
那么$E(Y_i)=0.5 imes(1+E(Y_i))+0.25 imes (1+E(Y_{i-1}))+0.25 imes(1+E(Y_{i+1}))$，高斯消元即可。
区间反转：01串每次随机一个区间将每个数取反，求m次后1的期望个数。
解：
令S为最终答案，Xi为i最后的值，由期望的线性性得$E(S)=sum E(Xi)=sum P(Xi=1)$
枚举每一位，设$dp(j,0/1)$表示这一位在j次后为0/1的概率。
令pi表示i这一位每次被选中的概率，容易得到$pi=frac{i imes (n-i+1)}{n imes n}$
则$dp(j,0)=dp(j-1,0) imes (1-pi)+dp(j-1,1) imes pi,dp(j,1)=dp(j-1,0) imes pi+dp(j-1,1) imes (1-pi)$
发现每次的转移系数相同，使用矩阵快速幂优化dp即可。
凸包：给n个点，随机选一个点集，求二维凸包的期望点数，保证没有三点共线。
解：
令最终答案为S，Xi,j为i与j的连线是否在凸包上，那么有$S=sum_{i=1}^{n-1}{sum_{j=i+1}^{n}{Xi,j}}$
由期望的线性性得$E(S)=sum_{i=1}^{n-1}{sum_{j=i+1}^{n}{E(Xi,j)}}$
考虑若$Xi,j=1$，则整个点集一定位于平面上直线$(i,j)$的左侧或右侧（上侧或下侧）。
那么设直线$(i,j)$的左边有s0个点，右边有s1个点。
则$E(i,j)=P(i,j)=frac{2^{s0}+2^{s1}}{2^{s0+s1}}=frac{1}{2^{s1}}+frac{1}{2^s0}$
单选错位：有n个选择题，每道有ai个选项，正确选项随机。你做对了这n道题但你把答题卡抄错了一位，求你期望对的题数。
解：
（相当于求期望有多少个选项与它左边的答案相同）
令S为最终答案，Xi为每个选项对不对，由期望的线性性得$E(S)=sum E(Xi)=sum P(Xi=1)$
容易得到$P(X{i}=1)=frac{min(a_{i-1},a_{i})}{a_{i-1} imes a_{i}}$
PKUWC2019拓扑排序：一个n个点的有向图，每条边等概率存在或不存在，求拓扑序列数量的期望$ imes 2^{m}$。$nleq 20$
解：
（在PPt里看到了……然而好像跟期望没什么关系）
签到题。由于期望$ imes 2^{m}$相当于没期望的事，只需要对每种连边方案统计答案。
由于n很小所以考虑用点集的状态统计边集的状态，设$dp(s)$表示点集s的方案数之和。
考虑枚举x作为拓扑排序中第一个点，那么s中其他点一定不能向x连边，而x向s中其他点连边不受约束。
于是得到$dp(s|x)=dp(s) imes 2^{card(s)}$
KILL：一开始有n个人，每次操作选一个还没死的人让他离开，他离开前会向其他所有人开一枪，有p的概率致死，求一个人活着离开且一共被开了k枪的概率。
解：
做法一：设$dp(i,j)$表示第i个人走了，还剩j个人的概率。
考虑枚举这一轮死了l个人，显然有$dp(i+1,j-l-1)+=dp(i,j) imes p^{l} imes (1-p)^{j-l-1}$
最后统计一波答案就好了。
做法二：将问题转化为死人放着，随机到再让他走，那么共进行n轮。
考虑设$dp(i,j)$表示剩下i个人，前面有j个人开了枪的概率。
那么分这次随机到的人是死人还是活人转移即可。
即为$dp(i-1,j)=dp(i,j) imes (1-(1-p)^{j})$，$dp(i-1,j+1)=dp(i,j) imes (1-p)^{j}$