期望真是个很神奇的东西啊，虽然利用方程移项可以证明，但总感觉很妙 定义 设数有种取值，每种取值对应概率为，则的数学期望为 比如说抛掷一枚硬币，定义正面为，反面为，则抛一枚硬币的期望为 掷骰子的期望为 彩票一张元，中奖概率为，奖金，则买一张彩票的收益期望为元 虽然这些期望都是小数，是取不到的值，但期望表示的并不是一个可能发生的情况，而是情况的一个平均，可以形象地理解为当实验进行越来越多的时候，平均情况会趋于接近期望（比如掷骰子次的时候，平均情况会接近，而当掷次的时候，会更加接近） 更一般的，若的取值并不是离散的，那么可以用积分表达期望 换汤不换药 基础期望 一枚硬币，抛到正面的概率为，问期望抛几次得到一个正面 先设答案为次，根据期望的定义可以列出式子，可以移项得出 解释一下那个式子的右边，考虑掷一次有两种情况： 有的概率为正面，这个时候只需要一次操作（即当前这次），取值，概率，所以第一项为； 有的概率为反面，由于抛到反面即返回最初的情况，所以还需要抛次，加上这一次，取值，概率，所以第二项为 列出这个方程可以解出其中某一项，可能这就是期望题目的大致玩法吧 给定一个有个面的骰子，问期望多少次能掷出所有面（SPOJ-FAVDICE） 发现这题不能像上一题那样只设一个变量，所以需要利用dp思想，设表示还剩面未被掷到时期望还需多少次完成 利用上一题的思想枚举所有后继情况，假设当前还剩面未被掷到 这一次掷到了还未被掷到的面，概率为，剩余次数为 这一次掷到了已经被掷到的面，概率为，剩余次数为 而这两个之和为，即，移项可得 而，则递推出即为答案 从这题可以看出一种解题方法，设置状态，列出方程，解出其中某一项，进行dp转移 你有一个战斗力，有扇门，每天随机抽取一扇门，若，则会用天的时间离开，否则增加，求离开天数的期望（ZOJ-3640） 这题也差不多，算是一个小练习，设表示当战斗力为时离开的期望天数 若，，否则 综合这最后这两题可以看出，如果用Dp解简单的期望题，状态的设置需要满足可重复利用（比如当战斗力为一个确值时，期望天数一定是个定值） 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; } 循环转移 有些题目是没有像上面题目那样的单项转移的，比如说下面这题 一个点边无向连通图，在图上进行随机游走，初始时在号顶点，每一步以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当到达号顶点时游走结束，总分为所有获得的分数之和。 要求对所有边进行编号（~），使得总分的期望值最小。（HNOI-2013游走） 很明显的贪心思路：求每条边的访问次数期望，按照期望大小次序给定边权，再给边权赋值 但是求边的期望又可以由边两边的点的期望得到，所以这题的主要难度在于求每个点的访问次数期望 用之前的方法进行设置。设表示走到节点的次数期望 由于任意两点间都有可能互相访问，所以对于任意一条边， 发现这里不能像之前几道题来解方程了，因为这里存在循环（要用推导，要用推导） 可以利用高斯消元求解，时间复杂度 类似的题还有很多，比如HNOI-2011XOR和路径 循环转移的非高斯消元解法 下面介绍两种循环转移的非高斯消元解法（复杂度） 线性情况 有三个骰子，分别有面，每次同时投掷得，分数增加，若三者的值分别为，则分数清零，若分数大于，则结束操作。求期望多少次投掷后结束操作（zoj-3329） 尝试用上一题的做法来解，设表示当前分数为时的期望还要进行多少次，令表示三个骰子分数和为的概率 则可以列出方程： 将提出来，把单独提出来，得到 舍弃之前说的高斯消元做法，介绍一种更优秀的做法 由于所有式子都要用到，所以不妨假设 然后将套到之前的式子里去，得到 对比式子：，发现两个式子结构相同，可得： 由于，而上面的式子中所有量是可以递推而得，没有循环转移关系的，所以可以递推得到 将代入，得到，即，得解 树上情况 一棵 个结点的树，从点 出发，每次等概率随机选择一条与所在点相邻的边走过去。 次询问，每次询问给定一个集合 ，求如果从 出发一直随机游走，直到点集 中所有点都至少经过一次的话，期望游走几步。（pkuwc2018随机游走） 这题之前就写过题解，在这，可以看看中间如何将树上情况的循环转移优化成递推 基本思路也是设每个节点从父亲转移，递推求得系数，这样是的 分层图情况&一般图情况 这个待填坑吧，分层图好像可以玩，听说去年pkuwc上有人想出了一个在一般图上高斯消元的高效算法https://www.cnblogs.com/penth/p/10218441.html