前言
概率的重要性嘛，生活处处皆概率其实是因为经常考
基础
-
$ 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的条件期望)
-
(全期望公式:)
(egin{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_jfrac{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=nsum_{i=1}^nfrac{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] imes g[i]$$
$$f[i]=(1-q[i]) imesPi_{v} [f[v]+(1-f[v]) imes(val[i][v])]$$ 解释：不被子节点充电首先自己不能直接充电，子节点不能充电或者子节点能充电但是导线不导电
设$P$为$i$节点不考虑$v$子树不充电的概率:
$$P= frac{g[i] imes f[i]}{f[v]+(1-f[v]) imes(1-val[i][v])}$$
$$g[v]=P+(1-P) imes(1-val[i][j])$$
解释：$f[i]$中包含了$v$所以要消掉
##[问题四](https://www.luogu.org/problemnew/show/P5249) $f[i][j]$表示$i$个人第$j$个人赢的概率，显然$f[i][j]=p_0 * f[i][j-1]+(1-p_0) * f[n-1][k-1]~~j≥2$ 结合$sumlimits{j=1}{j=i}f[i][j]=1, herefore f[i][1]=(1-p_0) * f[n][n]$，然后列方程暴力拆 ##[问题四](https://www.luogu.org/problemnew/show/P4007) 矩阵加速概率期望 [题意](https://www.luogu.org/problemnew/show/P4007) $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)时直接用这个快速幂，查询的状态是单行的，所以手动向量乘矩阵
问题五
线段树，每次等概率进点，求期望，可区间加
等概率，则答案为(sumlimits_{i={leaf}}sum_{i}×dfrac{1}{2^dep -1})，(sum)为到根路径和
然后约分化简简便运算
问题六
线段树，每次按权值比进点，求期望，可区间加
看似不可做，其实如果把进入次数改成(sumlimits_{i}a[i])，发现每个点进入的次数为(val[i])，总期望(dfrac{sumlimits_{i}{val[i]^2}}{sumlimits_{i}a[i]})
考虑一个点单独加值的贡献：$$(val+sizex)^2=val^2+2valsizex+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)的路径异或和期望，发现每一位是单独求解的
然后高斯消元就行
坑点：
设(f[i])为从(nlongrightarrow i)该位为(1)，特殊情况(f[n]=0)，因为到了(n)后是不能退出的，而(1)还是可以往回走的
所以我们把(f[n]=0)