概率相关知识点

1、 $P(X=K)=P(X>=K)-P(X>K)$

2、 $E[x]=\sum_1^\infty P(X\ge i)$

3、 $P(A)=P$ ，则一直随机直到发生事件A的期望次数为 $\frac{1}{P}$

每次随机一个[1…n]的数，期望随机几次能随机出全部的数

$T_i:$ 当前有i个数，第一次随机到新的数
$E[x]=\sum_0^{n-1}E[T_i]$
$P(T_i)=\frac{n-i}{n}$
$E[T_i]=\frac{1}{P(T_i)}=\frac{n}{n-i}$
$E[x]=\sum_0^{n-1}\frac{n}{n-i}=\sum_1^n\frac{n}{i}$

随机一个长度为n的序列p， $p[i]$ 是 $p[1..i]$ 中最大的概率

设随机变量 $x_j$ ，当 $p[j]$ 是 $p[1..i]$ 中最大值时为1，否则为0
则 $\sum_1^iX_j=1$
因为随机序列，则 $E(X_1)=E(X_2)=E(X_3)=...$
$E(X_i)=\frac{1}{i}$

随机游走：

一个n个点的完全图，求从s走到t的期望时间

从一个点走到任意另一个点的概率: $\frac{1}{n - 1}$ ,则次数的期望为 $n-1$

一条长度为n的链，从一端走到另一端的期望时间

$X_i:$ 第一次走到 $i$ 到第一次走到 $i+1$ 用的次数
$E(x)=\sum_0^{n-1}E(X_i)$
$E(X_i)=\frac{1}{2}+\frac{1}{2}(1+E(X_{i-1})+E(X_i)$ （ $\frac{1}{2}$ 概率直接从 $i$ 走到 $i+1$ ， $\frac{1}{2}$ 的概率从 $i$ 走到 $i-1$ ，此时期望为一次加 $i-1$ 走到 $i$ 的期望和 $i$ 走到 $i+1$ 的期望
由上式可得 $E(X_i)=2+E(X_{i-1})$

给定 $n$ 个硬币，第 $i$ 个硬币的价值是 $w_i$ ，每次随机取走一个硬币，获得收益是左右两个硬币的价值的乘积，求期望总价值

$X_{ij}:$ 第 $i$ 个硬币和第 $j$ 个硬币相邻的期望
$E(x)=\sum_{ij}w_i*w_j*E(X_{ij})$
$E(X_{ij})$ 为从 $i$ 到 $j$ 中取硬币，全部取完且最后两个是 $ij$ 的概率，所以是 $i$ 到 $j$ 所有数-2的全排列除以 $i$ 到 $j$ 所有数的全排列乘以2
$E(X_{ij})=\frac{2*(j-i-1)!}{(j-i+1)!}=\frac{2}{(j-i+1)*(j-i)}$

线性性与等价性的应用

随机一个 $1...n$ 的排列 $p$ ， $p[i]$ 是 $p[1...n]$ 中前 $k$ 大的概率

$x_i$ 为1则 $p[i]$ 为前k大，否则为0
$E(x)=\sum E(x_i)=k$
$E(x_i)=\frac{k}{n}$

给定一棵n个点的有根树，一开始每个点都是白色，每次等概率随机选择一个白点，将整个子树都染成黑色，问期望随机几次能把整棵树染黑

设 $X_i$ ，当 $i$ 被选中的时候为1，否则为0，则 $E(X)=\sum_{1}^{n}E(X_i)$
对于 $E(X_i)$ ，由于i点和其祖先节点在不被选中的时候其他点可以任意选择，故仅需考虑i点和其祖先节点
仅考虑i点和其祖先节点时（共有x个祖先节点），需要i点第一个被选中，则概率为 $\frac{1}{x+1}$
则 $E(X_i)=\frac{1}{dep_i+1}$

有n堆石头，每堆个数为a[i]，现在每次等概率随机选一个石头，然后将那个石头所在的那堆石头全扔了，直到第一堆石头被扔掉，问期望扔几次

设 $x_i$ ，当 $i$ 被扔的时候为1，否则为0， $E(x)=\sum_1^nE(x_i)$
对于 $E(x_i)$ ，第 $i$ 堆被扔当且仅当第 $1$ 堆在第 $i$ 堆之后扔
故 $E(x_i)=\frac{a_i}{a_1+a_i}$

对于一个1…n的排列p，定义他的价值为：所有满足 $p[i]>max(p[i-1],p[i+1])$ 的 $i$ 的和。现在随机一个排列p，求价值的期望

设 $x_i$ ，当 $p[i]>max(p[i-1],p[i+1])$ 时为 $i$ ，否则为 $0$ ， $E(x)=\sum_1^nE(x_i)$
当 $i=1$ or $i=n$ 时， $p[i]$ 满足条件的概率为 $\frac{1}{2}$ ，则期望分别为 $E(x_1)=\frac{1}{2}$ 和 $E(x_n)=\frac{n}{2}$
当 $1<i<n$ 时，考虑相邻三个数 $p[i-1],p[i],p[i+1]$ ， $p[i]$ 为三个数中最大的数的概率为 $\frac{1}{3}$ ，所以 $E(x_i)=\frac{i}{3}$

等概率随机一个长度为n的01串，定义01串的价值为：所有全1连续子串的长度的平方和，求价值的期望

对于一个含有全1子串长度为 $len_1,len_2,...,len_k$ 的01串， $X=\sum len_i^2$
对于一个长度为n的全1串，其包含子串个数为 $\frac{n(n+1)}{2}=\frac{1}{2}(n^2+n)$
将以上问题转化为对01串全部子区间的和问题，则 $X=\sum每个区间是否全1$
设 $x_{ij}$ ，当区间 $i...j$ 中全部为1时， $x_{ij}=1$ ，否则为0
对于一个长度为n的全1子串，由于其子串数量为 $\frac{1}{2}(n^2+n)$ 。所以对于一个全1串来说会被统计 $\frac{1}{2}(n^2+n)$ 次，则此时对于这个全1串来说，他的权值是 $\frac{1}{2}(n^2+n)$
题目求的价值为所有全1连续子串的长度的平方和，所以对上述每一个全1串权值进行变换即可得到最终答案
设第i个全1子串的价值为 $X_i$ ，则该子串的在当前问题下的实际价值为 $2*X_i-n$
则 $X=2*\sum_{i\le j}x_{ij}-\sum_{i=1}^{n}x_{ii}$
则 $E(X)=2*\sum_{i\le j}E(x_{ij})-\sum_{i=1}^{n}E(x_{ii})$
$E(x_{ij})=(\frac{1}{2})^{j-i+1}$ ， $E(x_{ii})=\frac{1}{2}$ ，带入求和即可

上面题的另一个版本做法（可能会较上一个版本难理解）：

设两个随机变量 $X_i,Y_i$ 。 $X_i$ 表示的是在添加第 $i+1$ 个字符的时候答案的增量， $Y_i$ 表示的是前 $i$ 个字符后缀1的长度。
当末尾添加字符为1时， $X_i=(E(Y_i)+1)^2-E(Y_i)^2=2E(Y_i)+1$ 。当末尾添加字符为0时， $X_i=0$
当末尾添加字符为1时， $Y_i=Y_{i-1}+1$ ，当末尾添加字符为0时， $Y_i=0$
则 $E(X_i)=\frac{1}{2}*0+\frac{1}{2}(2E(Y_i)+1)$ ， $E(Y_i)=\frac{1}{2}*0+\frac{1}{2}(E(Y_{i-1})+1)$
由于 $X_i$ 表示的是答案的增量，故答案 $X=\sum_0^{n-1} E(X_i)$

等概率随机一个排列 $p[1...n]$ ，定义 $f(p)$ 为有多少个 $i$ 满足 $p[i]$ 是 $p[1...i]$ 的最大值，求 $f(p)$ ， $f(p)^2$ 的期望

设 $x_i$ ， $p[i]$ 为 $p[1...i]$ 最大值时为1，否则为0
设 $X=f(p)$ ，则 $E(X)=\sum_1^nE(x_i)=\sum_1^n\frac{1}{i}$
$X^2=(\sum_1^nx_i)^2=\sum_{i\ne j}x_ix_j+\sum_1^nx_i^2$ ，其中 $x_i= \begin{cases}1 \\0 \end{cases}$ ，故 $x_i^2=x_i$ ，则原式 $=\sum_{i\ne j}x_ix_j+\sum_1^nx_i$
由上式可得 $E(X^2)=\sum_{i\ne j}E(x_ix_j)+\sum_1^nE(x_i)$
考虑 $i<j$ 时， $p[j]$ 是 $p[1...j]$ 的最大值的概率为 $\frac{1}{j}$ ，则去掉 $p[j]$ 后，前 $j-1$ 个数字是完全随机的，则 $p[i]$ 是 $p[1...i]$ 中最大的数的概率为 $\frac{1}{i}$ ，则 $p[j]$ 是 $p[1...j]$ 的最大值且 $p[i]$ 是 $p[1...i]$ 的最大值的概率为 $\frac{1}{ij}$ ，则 $E(x_ix_j)=P(x_ix_j)=\frac{1}{ij}$
综上 $E(X^2)=\sum_{i\ne j}\frac{1}{ij}+\sum_{i=1}^n\frac{1}{i}$

给定一个字符串T，和一个字符串序列S[1…n]

选择k次来构造一个字符串，每次随机从S[1…n]中随机选一个字符串拼接到已构造的串后面

求T在构造的串中的期望出现次数

$|T|\le50,n\le50,|S[i]|<=50,k<=10^{12}$

首先考虑 $k\le50$ 的情况。此时可以通过dp暴力算出答案
令 $dp[i][j]$ 表示加入第 $i$ 个串后kmp指针指在 $j$ 时的状态
对于每个 $i,j$ ，枚举每个字符串，算出当前 $i$ 个字符串kmp指针指在 $j$ 时，加入字符串 $s[i]$ 后T出现的次数 $x$ ，以及kmp指针指向的位置 $j'$ ，得到转移方程 $dp[i+1][j']=dp[i][j]+x$ 。最后枚举 $dp[k][j]$ ，算出所有情况的出现次数除以 $k!$ 即可。
再考虑 $k>50$ 的情况。考虑极限情况，当加入一个新的字符串的时候， $T$ 的出现次数最多会与前 $50$ 个串有关系（ $s[i]=1$ 的时候）
令 $f[k]$ 表示拼接 $k$ 次后的期望次数，则可以推出结论当 $k>|T|$ 时有 $f[k+1]-f[k]=f[k+2]-f[k+1]$ ，即 $k>|T|$ 时期望增量相等。
由上述结论，多算一次dp算出增量乘起来就可以了。

拓扑序

给定一张 $n$ 个点的有向图， $f(E)$ 表示边集E的拓扑序个数，令 $E$ 取遍该图的边集的所有子集，求 $f(E)$ 的和( $n\le20$ )

设 $T$ 为图的边集， $E$ 为边集 $T$ 的一个子集， $P$ 为子集中点的选取顺序的一个排列， $g(E,P)=\begin{cases} 1&P为合法拓扑序\\0&P不是合法拓扑序\end{cases}$
则 $\sum f(E)=\sum_{E\subseteq T}\sum_{PisPer}g(E,P)$ ，即对于边集的每个子集合的所有选取顺序是合法拓扑序的数量。
交换上述式子内外循环，则 $\sum f(E)=\sum_{PisPer}\sum_{E\subseteq T}g(E,P)$ ，即对于每个点的选取顺序中，边的子集使得点的选取顺序是合法拓扑序的数量。
拓扑序合法，即对于边集中的每条边 $(a,b)$ ，若都有 $p[a]>p[b]$ ，则拓扑序合法
对于访问序列 $p$ ，令 $D(p)=有几条边(a,b)\subseteq T使p[a]>p[b]$ ，则上述式子可以转成 $\sum_{PisPer}2^{D(p)}$ ，即对于当前访问顺序，合法的每一条边都可以任意选择加入边的子集与否，即 $2^{D(p)}$
考虑 $dp[S]$ 。当前加入的点为 $S$ 的二进制中为1的位编号，按照 $p[i]$ 的大小，从大到小加点。则考虑新加入的点X（二进制表示），由于加入顺序为从大到小，若 $Y\subseteq S$ ，则 $p[X]<p[Y]$ ，所以这时只需统计 $(X,Y),Y\subseteq S$ 的数量即可。
综上转移方程为 $dp[S]=dp[S+X]*2^k$ 。其中 $k$ 为上述边的数量。

位运算

给定数组a[1…n]，求 $\sum_{1\le i<j\le n}a[i]\,xor\,a[j]$ ， $1\le n\le 10^5, 0\le a[i]<2^{30}$ 

定义 $bit(x,i)=\begin{cases}1:&x的第i位为1\\0:&x的第i位为0\end{cases}$ ，则 $a\,xor\,b=\sum_{i=0}^{29}2^i(bit(a,i)\ne bit(b,i))$
则原式： $\sum_{i=1}^n\sum_{j=i+1}^n\sum_{k=0}^{29}2^k(bit(a[i],k)\ne bit(a[j],k))$
更换前后顺序，则原式: $\sum_{k=0}^{29}\sum_{i=1}^n\sum_{j=i+1}^n2^k(bit(a[i],k)\ne bit(a[j],k))$
设数组 $b[i]=bit(a[i],k)$ ，则原式： $\sum_{k=0}^{29}\sum_{i=1}^n\sum_{j=i+1}^nb[i]\ne b[j]$
由于 $b[i]$ 取值为0或1，设b数组中1的个数为x，0的个数为y，则 $\sum_{i=1}^n\sum_{j=i+1}^nb[i]\ne b[j]=x*y$

异或排序

给定一个长度为 $n$ 的非负整数序列 $A[1..n]$ ，求有多少个不同的整数 $S$ 满足以下条件：

1、 $0\le S<2^{60}$

2、对于所有 $[1,n-1]$ 中的 $i$ ，有 $A[i]\ xor\ S\le(A[i+1]\ xor\ S)$

$1\le n\le 20,\ 0\le A[i]<2^{60}$

首先对于 $A[i]\ xor\ S \le A[i + 1]\ xor\ S$ ，可以发现当且仅当 $A[i]=A[i+1]$ 时 $A[i]\ xor\ S = A[i + 1]\ xor\ S$ ，故原式= $A[i]\ xor\ S < A[i + 1]\ xor\ S$
对于 $A[i]$ 和 $A[i+1]$ ，及 $A[i]\ xor\ S$ 和 $A[i + 1]\ xor\ S$ 比较大小。从高位到低位比较大小，相同继续，直到不同的第k位。
对不同的一位进行分析。由于需要使 $A[i]<A[i+1]$ ，则 $bit(A[i]\ xor\ S,k)<bit(A[i+1]\ xor\ S,k)$ .
若 $bit(A[i],k)>bit(A[i+1],k)$ ，则 $bit(S,k)=1$ ；若 $bit(A[i],k)<bit(A[i+1],k)$ ，则 $bit(S,k)=0$
遍历数组，求出队 $S$ 的 $n$ 个限制。若限制有矛盾，则无解。否则，若S没有限制的位数为k，则答案为 $2^k$

和的XOR

给定数组 $a[1..n]$ ，求所有的 $a[i]+a[j]$ xor起来的值，其中 $1\le i<j\le n$ 

对与 $1\le i<j\le n$ 的所有数的第 $b$ 位，结果相当于算 $bit(a[i]+a[j],b)$ 为1的数量，是奇数则第 $b$ 位为1，是偶数则第 $b$ 位为0
考虑第b位为1的情况，此时 $x\%2^{b+1}\ge 2^b$ 。故上面的式子等于统计 $(a[i]+a[j])\%2^{b+1}\ge2^b$ 的数量
令 $c[i]=a[i]\%2^{b+1}$ ，则 $c[i]\in[0,2^{b+1})$ ， $c[i]+c[j]\in[0,2^{b+2}-1)$
$(c[i]+c[j])\%2^{b+1}\ge2^b$ 当且仅当 $\begin{cases}c[i]+c[j]\in[2^b,2^{b+1})\\c[i]+c[j]\in[2^b+2^{b+1},2^{b+2})\end{cases}$ 时满足条件
对c数组排序，枚举每个左端点 $i$ ，二分找到满足区间要求的 $l,r$ ，则满足条件的数量+=(r-l+1)