数学期望 E=Σ每一种状态*对应的概率。(所有可能次数的加权)
=（总量）/情况数（概率相等的时候）；
借此（+对称性）我们可以先猜出此题的结论（ans=平均数）
1问：
（1）：为什么有放回和无放回的时候期望都是 p*n
前者显然，后者是以为期望的线性和对称性：当第一个没选到时候会影响下一个，但是同时第一个选到的时候也会影响下一个；
（1）扑克牌延申题
预处理出C（n，2）中互质的对数。可能的选择总数是C（n，2）；
期望就是 （cnt）/（C（n，2））*（n/2） ：需要分奇偶
一般来说，初始状态确定时可用顺推，终止状态确定时可用逆推。
（1）
题意：
甩一个n面的骰子，问每一面都被甩到的次数期望是多少。
选择逆推：设dp[i]为以及i面离n面还需要多少次操作
先找出相邻两项的关系 dp[i]=dp[i]*(i/n)+dp[i+1]*((n-i)/n)+1(当前操作次数)
随后解出dp[i]=..
题意：
有n个奖品，m个人排队来选礼物，对于每个人，他打开的盒子，可能有礼物，也有可能已经被之前的人取走了，然后把盒子放回原处。为最后m个人取走礼物的期望。
知道首位，顺序dp：设为i个人拿到的期望
dp[i]=dp[i-1]（继承关系，其实E（x+y）=E(x)+E(y)）+1*(n-dp[i-1])/n;
（2）
根据逻辑递推式子
E(n)=1+求和（E(i-2)+E(n-1-i)）
关键在化简成递推式
对称性化简+调整求和范围
（3）
发现顺序就行，dp表示已经钟了i个的期望次数
dp[i]=(1+dp[i-1])*（p[i-1]）+(1-p[i])*dp[0];//转化为统一式（由线性到树形感悟出）
也可
//加1可以理解为期望的线性性质
dp[i]=dp[i-1]*（p[i]）+(1-p[i-1])*(dp[i]+1+dp[i-1]);//失败后又回来到这
（1）dfs型
从线性到树形循环（后两题循环型）
线性：
师傅被妖怪抓走了。有n个妖怪，每个妖怪有一个固定的战斗力c[]，师傅也有一个初始战斗力f0。
每天，师傅会随机选择一个妖怪决斗，如果打得赢ft>c[]，就可以逃出去,逃出去要t[]天，毕竟超人不会飞；
否则，师傅会不甘心，当天他会拿出秘籍练功，将自己变强,f(t+1)=f(t)+c[]，第二天寻找下一次机会。
问师傅能够逃脱可怕的妖怪，继续追求去印度吃手抓饼的梦想的天数的数学期望day。
（发现只能以f为状态来dp）(注意是逆推的)
对每个状态：设置dp[f]为攻击力为f的时候的用时期望
dp[f]=求和(dp[f+c[i]]+1)/n(要加权) //,F<=c[i]
dp[f]=求和(t[i])/n //F>c[i]
循环型一般和父子互推：这时候要找到递推式，一般是父+dp【0】+常数（待定系数法）
待补
（1）基础矩阵型
你知道，师傅经常被抓，这次又被抓到一个矩阵里面，最开始他在Map[1][1]，出口在Map[n][m]；
每一次他会消耗两颗神丹，然后每一个格子，有一定概率留在原地，有一定概率向下走一格，有一定概率向右走一格。。。求师傅逃出去的神丹消耗期望
逆推：dp[i][j]=(2+dp[i+1][j])*p1+(2+dp[i][j+1]*p2+p3(dp[i][j])+2)
(2)高考数学型
开始有一个吸血鬼，n-1个平民百姓。每天一个百姓被感染的概率可求，问每个人都变成吸血鬼的天数期望
逆推：设dp[n]为n个吸血鬼的期望天数，此时是0
p[]=(n-i)*i/(n*(n-1)/2)*p;(有效/总)
dp[i]=1+dp[i]*(1-p)+dp[i+1]*(p);
(双关联期望)
有一个富豪，他决定每天撒钱，并且抛硬币，第一天1块钱，第二天3块钱，第三天5块，直到他抛到硬币向上的数量为K。
求天数期望和钱期望。
天数很容易求：dp[i]=dp[i]*(1-p)+dp[i-1]*p;
转化马内：第i天是2*i-1
期望其实就是天数：（当天加上前面的天数）
f[i]=p*(f[i-1])+(1-p)*f[i]+dp[i]*2-1
树形dp
（1）
小A发现了很多的蚂蚁，A蚂蚁都跟着它自己前面的那只蚂蚁 （可能有数只蚂蚁跟着同一只蚂蚁），只有最前面的那只蚂蚁在自己向前走。
小A想抓一些蚂蚁，所以他话西引每一只蚂蚁，试着能不能將它们勾引出队伍。如果一只蚂蚁被勾引出了队伍，那么跟在它后面的所有蚂蚁也会跟着走。每一只蚂蚁都有
一定的价值，对于每一只蚂蚁都有一定的概率能勾引成功。
现在小A想知道，他能抓到的蚂蚁价值和的数学期望值是多少。
代码：
dp[u]=p u(勾引成功时的价值)+(1−p u)⋅(不勾引时的子树期望)
（2）给出张 n 个点 m 条边的有向无环图，起点为 1，终点为 n，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。
绿豆蛙从起点出发，走向终点。 到达每一个顶点时，如果该节点有 k 条出边，绿豆蛙可以选择任意一条边离开该点，并且走向每条边的概率为
k
1
。现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？
拓扑+dp+度数
为了方便更新我们建了反图，但是出度以原图为准
（4）组合数学+概率+dp
题意：
一套题，有T个题，M个人应考，已知每个人做来某题的概率。问X的概率。X满足，每个考生至少做来一道题。至少有一人做的题不少于N道。
设置dp[i][j][k] i个人j道题作对k道的概率
转移：dp[i][j][k]=dp[i][j-1][k]*(1-p)+dp[i][j-1][k-1]*p
考生作对至少一题概率是 连乘(1-dp[all][n][0]);
最多n-1: 连乘(1-dp[all][n][n])
最后两者做差....
（5）贡献
一共有n次操作，每次操作只有成功与失败之分，成功对应1，失败对应0，n次操作对应为1个长度为n的01串。在这个串中连续的 X个1可以贡献X^3 的分数，这x个1不能被其他连续的1所包含（也就是极长的一串1，具体见样例解释）
现在给出n，以及每个操作的成功率，请你输出期望分数，输出四舍五入后保留1位小数。
(x+1)^3−x^3 =3x^2 +3x+1
利用线性E=E（x^2）+E(x^2)+1;
思路：此类期望题都是单独算某一位的贡献，假设前一位的连续长度为g[i-1]，那么很明显当前位的期望长度为 g[i]=(g[i-1]+1)*p[i]；
则当前为的贡献是add=g[i]^3-g[i-1]^3=3*g[i]^2-3*g[i]+1。 这三部分分别算期望即可。
第一部分：3*g[i]^2，就是平方的期望（不仅仅是期望的平方那么简单），令期望的平方为数组g2，则3g2[i]=3*(g2[i-1]+2*g[i-1]+1)*p[i];
第二部分：-3*g[i]，其期望=-3*(g[i-1]+1)*p[i]
第三部分: 1，其期望=p[i]
