概率的重要性嘛，生活处处皆概率其实是因为经常考
$ P(A):表示事件A发生的概率\ E(A):表示事件A发生的期望$
\(对于事件A,E(A)=\frac{1}{P(A)}(A是否发生对B是否发生没有影响)\)
\(对于两个相互独立事件A和B\\E(A+B)=E(A)+E(B)\\E(AB)=E(A)E(B)\\E(A/B)=E(A)/E(B)\)
$ 全概率公式:P(A)=\sum_{i}P(A|B_i)P(B_i)_{(P(A|B):B发生后发生A的概率)}$
多个条件下的概率已知\(\overset{全概率公式}{\longrightarrow}求事件发生概率\)
\(E(A|B=b_i)表示B=b_i时A的条件期望\)
\(全期望公式:\)
\(\begin{eqnarray*}E(E(A|B))&=&\sum_{i}P(B=b_i)E(A|B=b_i)\\&=&\sum_{i}P(B=b_i)\sum_{j}a_j\frac{P(B=b_i且A=a_j)}{P(B=b_i)}\\&=&\sum_{i}\sum_{j}a_jP(B=b_i且A=a_j)\\&=&E(A)\end{eqnarray*}\)
\(由此我们得到E(A)=\sum_{i}P(B=b_i)E(A|B=b_i)\)
\(n\)种物品，每次都会随机买到一种，求全部买到的期望次数
考虑买了\(k\)种物品，买到\(k+1\)种物品的期望次数，\(P(k+1)=\dfrac{n-k}{n}，E(k+1)=\dfrac{1}{P(k+1)}=\dfrac{n}{n-k}\)
所以\(ans=n\sum_{i=1}^n\frac{1}{n}\)
\(n\)种物品，每次都会随机买到一种，第\(i\)次买需要花费\(i\)，求全部买到的期望花费
\(f[i]\)为还剩\(i\)种没买的期望次数，\(g[i]\)为花费
\(f[i]=f[i+1]+\dfrac{n}{n-i}\)
两种不同的情况：\[g[i]=\frac{i}{n}*(g[i]+f[i]+1)+\frac{n-i}{n}*(g[i+1]+f[i+1]+1)\]
看上去和求极有关，其实移项就可以了(雾
$f[i]$: $i$不被这个点所在的子树中的点充电的概率
$g[i]$: $i$不被自己的父亲节点充电的概率
$p[i]$: $i$被充电的概率
$q[i]$:$i$被直接充电的概率
$val[i][j]$:$i,j$导线导电的概率
$$p[i]=1-f[i]\times g[i]$$
$$f[i]=(1-q[i])\times\Pi_{v} [f[v]+(1-f[v])\times(val[i][v])]$$ 解释：不被子节点充电首先自己不能直接充电，子节点不能充电或者子节点能充电但是导线不导电
设$P$为$i$节点不考虑$v$子树不充电的概率:
$$P= \frac{g[i]\times f[i]}{f[v]+(1-f[v])\times(1-val[i][v])}$$
$$g[v]=P+(1-P)\times(1-val[i][j])$$
解释：$f[i]$中包含了$v$所以要消掉
\(f[i][j]\)表示\(i\)个人第\(j\)个人赢的概率，显然\(f[i][j]=p_0 * f[i][j-1]+(1-p_0) * f[n-1][k-1]~~j≥2\)
结合\(\sum\limits{j=1}{j=i}f[i][j]=1,\therefore f[i][1]=(1-p_0) * f[n][n]\)，然后列方程暴力拆
矩阵加速概率期望
题意
\(dp[i][a][b][c]\)为第\(i\)次攻击时\(1\)血剩\(a\)个，\(2\)血剩\(b\)个，\(3\)血剩\(c\)个，状态数相当于把\(k\)个物品分配到\(m\)个集合中
状态方程比较好想，就不赘述了
由于式子是线性的，考虑矩阵优化：\(p[i][j]\)为状态\(i\)转移到状态\(j\)的概率，最后再加一列将概率转期望就好了
多次查询+状态数繁多，肯定\(T\)，将\(p\)多开一维倍增\(p[w][i][j]\)，查询\(n\)时直接用这个快速幂，查询的状态是单行的，所以手动向量乘矩阵
线段树，每次等概率进点，求期望，可区间加
等概率，则答案为\(\sum\limits_{i=\{leaf\}}sum_{i}×\dfrac{1}{2^dep -1}\)，\(sum\)为到根路径和
然后约分化简简便运算
线段树，每次按权值比进点，求期望，可区间加
看似不可做，其实如果把进入次数改成\(\sum\limits_{i}a[i]\)，发现每个点进入的次数为\(val[i]\)，总期望\(\dfrac{\sum\limits_{i}{val[i]^2}}{\sum\limits_{i}a[i]}\)
考虑一个点单独加值的贡献：\[(val+size*x)^2=val^2+2*val*size*x+size^2*x^2\]
我们维护\(val\)，\(val*size\)，\(size^2\)
生成树期望路径和
尝试转换问题：经典边权贡献问题
我们考虑\(i\)的子树有\(K\)个点的方案，单独\(K\)个点确定根的构树方案为\(K!\)，靠补度可以简单证明
子树内生成方案：\(K!C_{n-u}^{K-1}\)
子树外的生成方案依然可以靠补度计算，第一个点有\(u\)个度可以选择，知道第\(n-u-(K-1)\)个点有\(u+(n-u-(K-1))-1\)个度可以选择
\(u\)到根的生成：\(u!\)
\(n^2\)枚举子树大小就好了
这是一类典型的期望/概率问题，或许你不能(或者很复杂)之间求出答案
但通过题意我们能得到一组方程等式
至此，通过高斯消元得出解，甚至有时是可以手动消元的
从\(1\)到\(n\)的路径异或和期望，发现每一位是单独求解的
\[\begin{aligned}\f[u]=\dfrac{1}{deg[u]}(\sum\limits_{w(u,v)\in E_0}f[v]+\sum\limits_{w(u,v)\in E_1}(1-f[v]))\deg[u]f[u]=\sum\limits_{w(u,v)\in E_0}f[v]+\sum\limits_{w(u,v)\in E_1}(1-f[v])\deg[u]f[u]+\sum\limits_{w(u,v)\in E_1}f[v]-\sum\limits_{w(u,v)\in E_0}f[v]=\sum\limits_{w(u,v)\in E_1}1\\end{aligned}\]
然后高斯消元就行
坑点：
设\(f[i]\)为从\(n\longrightarrow i\)该位为\(1\)，特殊情况\(f[n]=0\)，因为到了\(n\)后是不能退出的，而\(1\)还是可以往回走的
所以我们把\(f[n]=0\)
原文：https://www.cnblogs.com/y2823774827y/p/10505803.html