期望真是个很神奇的东西啊，虽然利用方程移项可以证明，但总感觉很妙
定义设数\(x\)有\(n\)种取值，每种取值\(a_i\)对应概率为\(p_i\)，则\(x\)的数学期望为\(E(x)=\sum a_ip_i\)
比如说抛掷一枚硬币，定义正面为\(1\)，反面为\(0\)，则抛一枚硬币的期望为\(E(x)=0.5\times 1+0.5\times 0=0.5\)
掷骰子的期望为\(\frac 16\times 1+\frac 16\times 2+\cdots+\frac 16\times 6=\frac 16\sum_{i=1}^6i=3.5\)
彩票一张\(1\)元，中奖概率为\(\frac 1{10^6}\)，奖金\(10^5\)，则买一张彩票的收益期望为\(\frac 1{10^6}\times 10^5=0.1\)元
虽然这些期望都是小数，是取不到的值，但期望表示的并不是一个可能发生的情况，而是情况的一个平均，可以形象地理解为当实验进行越来越多的时候，平均情况会趋于接近期望（比如掷骰子\(100\)次的时候，平均情况会接近\(3.5\)，而当掷\(10^6\)次的时候，会更加接近\(3.5\)）
更一般的，若\(x\)的取值并不是离散的，那么可以用积分表达期望 换汤不换药
基础期望一枚硬币，抛到正面的概率为\(p\)，问期望抛几次得到一个正面
先设答案为\(x\)次，根据期望的定义可以列出式子\(x=p\cdot 1+(1-p)(x+1)\)，可以移项得出\(x=\frac 1p\)
解释一下那个式子的右边，考虑掷一次有两种情况：
有\(p\)的概率为正面，这个时候只需要一次操作（即当前这次），取值\(1\)，概率\(p\)，所以第一项为\(p\cdot 1\)；
有\(1-p\)的概率为反面，由于抛到反面即返回最初的情况，所以还需要抛\(x\)次，加上这一次，取值\(x+1\)，概率\(1-p\)，所以第二项为\((1-p)(x+1)\)
列出这个方程可以解出其中某一项，可能这就是期望题目的大致玩法吧
给定一个有\(n\)个面的骰子，问期望多少次能掷出所有面（SPOJ-FAVDICE）
发现这题不能像上一题那样只设一个变量，所以需要利用dp思想，设\(f_i\)表示还剩\(i\)面未被掷到时期望还需多少次完成
利用上一题的思想枚举所有后继情况，假设当前还剩\(i\)面未被掷到
这一次掷到了还未被掷到的面，概率为\(\frac in\)，剩余次数为\(f_{i-1}+1\)
这一次掷到了已经被掷到的面，概率为\(\frac {n-i}n\)，剩余次数为\(f_i\)
而这两个之和为\(f_i\)，即\(f_i=\frac in(f_{i-1}+1)+\frac {n-i}n(f_i+1)\)，移项可得\(f_i=f_{i-1}+\frac ni\)
而\(f_0=0\)，则递推出\(f_n\)即为答案
从这题可以看出一种解题方法，设置状态，列出方程，解出其中某一项，进行dp转移
你有一个战斗力\(v\)，有\(n\)扇门，每天随机抽取一扇门\(i\)，若\(v\leq c_i\)，则会用\(t_i\)天的时间离开，否则\(v\)增加\(c_i\)，求离开天数的期望（ZOJ-3640）
这题也差不多，算是一个小练习，设\(f_i\)表示当战斗力为\(i\)时离开的期望天数
若\(i\leq c_i\)，\(f_i+=\frac 1nf_{i+c_i}\)，否则\(f_i+=\frac 1nt_i\)
综合这最后这两题可以看出，如果用Dp解简单的期望题，状态的设置需要满足可重复利用（比如当战斗力为一个确值\(x\)时，期望天数一定是个定值）
double f(int x){ if(x>max_c)return sum_t/n; if(dp[x]>-0.5)return dp[x]; double res=0; for(int i=1;i<=n;++i) if(x<=c[i])res+=1+f(x+c[i]); else res+=t[i]; return dp[x]=res/n; } 循环转移有些题目是没有像上面题目那样的单项转移的，比如说下面这题
一个\(n\)点\(m\)边无向连通图，在图上进行随机游走，初始时在\(1\)号顶点，每一步以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当到达\(n\)号顶点时游走结束，总分为所有获得的分数之和。 要求对所有边进行编号（\(1\)~\(m\)），使得总分的期望值最小。（HNOI-2013游走）
很明显的贪心思路：求每条边的访问次数期望，按照期望大小次序给定边权，再给边权赋值
但是求边的期望又可以由边两边的点的期望得到，所以这题的主要难度在于求每个点的访问次数期望
用之前的方法进行设置。设\(f_i\)表示走到\(i\)节点的次数期望
由于任意两点间都有可能互相访问，所以对于任意一条边\((u,v)\)，\(f_u+=\frac 1{deg_v}f_v,f_v+=\frac 1{deg_u}f_u\)
发现这里不能像之前几道题来解方程了，因为这里存在循环（\(f_1\)要用\(f_2\)推导，\(f_2\)要用\(f_1\)推导）
可以利用高斯消元求解，时间复杂度\(O(n^3)\)
类似的题还有很多，比如HNOI-2011XOR和路径
循环转移的非高斯消元解法下面介绍两种循环转移的非高斯消元解法（复杂度\(O(n)\)）
线性情况