一、概率

1.1 定义

概率定义：一个事，用 $P$ 表示。

随机变量：表示随机试验各种结果的实值单值函数，其实就是某个事件的所有可能情况的数值表示，一般写作 $P(x = k)$ ，表示随机变量 $x$ 取值为 $k$ 时的概率。

举例：“投一次骰子”这一事件的随机变量：$p(x = 1) = p(x = 2) = p(x = 3) = p(x = 4) = p(x = 5) = p(x = 6) = \frac{1}{6}$。

1.2 性质

设有一个整数随机变量 $x$ ，则：$P(x = k) = P(x\ge k) – P(x>k)$

应用：

求投n次骰子，最小的点数等于2的概率。

计算方法：$P(x = 2) = P(x\ge 2) – P(x > 2) = (\frac{5}{6})^n – (\frac{4}{6})^n$

二、期望

2.1 定义

假设事假A的收益为 $W(A)$,则随机变量 $x$ 的期望 $E(x) = \displaystyle\sum_k P(x = k)k$ ,即随机变量 $x$ 的所有取值和其对应的概率相乘后再相加。

2.2 性质

性质一
期望的线性性：$E[X+Y] = E[X] + E[Y]$，$X = X_1 + X_2，则E[X] = E[X_1] + E[X_2]$。

证明：

设：$E[X] = \displaystyle\sum_{k_1} P(X = k_1)k_1$ , $E[Y] = \displaystyle\sum_{k_2}P(Y = k_2)k_2$。

则：$E(X+Y) = \displaystyle\sum_{k_1} \displaystyle\sum_{k_2}P(X = k_1,Y = k_2)(k_1+k_2)$，将 $(k_1+k_2)$ 拆开，先看前半部分：$\displaystyle\sum_{k_1}\displaystyle\sum_{k_2}P(X = k_1,Y = k_2)k_1$，相当于： $\displaystyle\sum_{k_1}k1\displaystyle\sum_{k_2}P(X = k_1,Y = k_2)$，后半部分$\displaystyle\sum_{k_2}P(X = k_1,Y = k_2)$表示当 $Y$ 取所有值时随机变量X的所有概率相加，其实就等于$P(X = k_1)$，则$\displaystyle\sum_{k_1}k1\displaystyle\sum_{k_2}P(X = k_1,Y = k_2) = E(X)$,同理，$\displaystyle\sum_{k_2}k2\displaystyle\sum_{k_1}P(X = k_1,Y = k_2) = E(Y)$,则$E(X+Y) = E(X) +E(Y)$
性质二

假设 $X$ 是一个随机正整数变量（整数且取值为所有正整数），则：$E(X) = \displaystyle\sum_{i = 1}^{\infty} P(X\ge i)$。

证明：$E(X) = \displaystyle\sum_{k = 1} ^{\infty} P(X = k)k = \displaystyle\sum_{k = 1} ^{\infty}P(X = k) \displaystyle\sum_{i = 1}^{k}1 = \displaystyle\sum_{i = 1}^{\infty}\displaystyle\sum_{k = i}^{\infty}P(X = k) = \displaystyle\sum_{i = 1}^{\infty} P(X\ge i) $

第一步的变换很好理解，就是将 $k$ 表示成 $k$ 个 1 相加，即$\displaystyle\sum_{i = 1}^k1$。

第二步的变换可以用编程中循环的角度去考虑，$ \displaystyle\sum_{k = 1} ^{\infty}P(X = k) \displaystyle\sum_{i = 1}^{k}1 $ 相当于下面的一个二层for循环：
```
for k : 1 -> inf //inf表示无穷大
  for i : 1 -> k
      ans += P(X = k)
```
将两层for循环调换顺序得到等效的循环：
```
for i : 1 -> inf //根据上面的循环可以知道，i的取值最大到inf
  for k = i -> inf// k不能小于i
      ans += P(X = k)
```
上述循环用数学形式表示就是：$\displaystyle\sum_{i = 1}^{\infty}\displaystyle\sum_{k = i}^{\infty}P(X = k)$，其中后边部分就表示$P(X\ge i)$。

2.3 经典例子

例子一：每次随机一个 [1,n] 的数，问期望随机几次能随机出所有数$E(X)$。

思路：对于一个不好计算的期望，可以将其成几个容易计算期望的阶段进行考虑，然后根据期望的线性性将它们相加得到总的期望。
- 我们令 $X_i$ 表示第一次有 $i$ 个不同的数到第一次有 $i+1$ 个不同的数需要的次数，则 $E(X) = E(\displaystyle\sum_{i = 0}^{n-1}X_i) = \displaystyle\sum_{i = 0}^{n-1}E(X_i)$，这里用到了期望的线性性，将求解 $E(X)$, 转变为求解$E(X_i)$ 。
- 根据 $X_i$ 的定义，我们可以求出$P(X_i) = \frac{n-i}{n}$（一共n个数，已经存在 i 个数，剩下 n-i 个数未出现，只要得到 n-i 个数中的一个，就可以从第一次有 i 个数变成第一次有 i+1 个数的状态，而得到 n-i 个数中的一个的概率就是 $\frac{n-i}{n}$）。
- $E(X_i) = \frac{1}{P(X_i)} = \frac{n}{n-i}$，只要 $X_i$ 满足几何分布，此公式就成立（如掷硬币模型）。
证明：以掷硬币模型为例，设正面的概率为 $p$ ，反面的概率为 $1-p$，$E_2(X)$ 表示一直投掷直到出现正面的期望。由于 $X$ 的取值可能为 $\infty$ ，所以可以用 $E_2(X) = \displaystyle\sum_{i = 1}^{\infty} P(X\ge i)$套用，$P(X\ge i) = (1-p)^{i-1}$，则$E_2(X) = \displaystyle\sum_{i = 1}^{\infty}(i-p)^{i-1}$，这就是一个等比数列求和，最终化简可以得到$E_2(X) = \frac{1}{p}$，即期望等于概率的倒数。
- 则$E(X) =\displaystyle\sum_{i = 0}^{n-1}E(X_i) = \displaystyle\sum_{i = 0}^{n-1}\frac{n}{n-i} = \displaystyle\sum_{i = 1}^n\frac{n}{i}$ ，调和级数。
例子二：随机一个长度为n的排列p，p[i] 是 p[1…i] 中最大的概率
令 $X_j=
\begin{cases}
1& \text{p[j] = max(p[1…i])}\\
0& \text{otherwise} \\
\end{cases}$，则$E(X_j) = 1 * P(X_j = 1) + 0 * P(X_j = 0) = P(X_j = 1)$，由于 $X_1,X_2…X_i$同分布，则$E(X_1) = E(X_2) = … = E(X_i)$，且$\displaystyle\sum_{j = 1}^iX_j = 1$，因为前 i 个数中必然有且仅有一个最大值使得$X_j = 1$，求和的值也必定为1。两边同时加上期望得：$E(\displaystyle\sum_{j = 1} ^i X_j) = E(1)$，根据期望的线性性得：$\displaystyle\sum^i_{j = 1}E(X_j) = 1$，由于$E(X_1) = E(X_2) = … = E(X_i)$，则$iE(X_i) = 1$，$E(X_i) = P(X_i = 1)= \frac{1}{i}$。

2.4 例题

首先假设已经确定哪些课程申请换教室，考虑如何计算跑动距离的期望$E(X)$：

令 $E(X_i)$ 表示第 $i$ 节课下课后的跑动距离，则根据线性性： $E(X) = E(\displaystyle\sum_{i = 1}^{n-1}X_i) = \displaystyle\sum_{i = 1}^{n-1}E(X_i)$。

考虑 $E(X_i)$ ，如何计算：

考虑第 i 节课换教室是否申请以及第 i+1 节课换教室是否申请，一共有4种可能的期望值，根据期望的定义可以得到：

如果都不申请：$E_1(X_i) = dis[c[i]][c[i+1]]$。
如果都申请：$E_2(X_i) = k[i] * k[i+1] * dis[d[i]][d[i+1]] + (1-k[i]) * k[i+1] * dis[c[i]][d[i+1]] $ + $ k[i] * (1-k[i+1]) * dis[d[i]][c[i+1]] + (1-k[i]) * (1-k[i+1]) * dis[c[i]][ci+1]$
第i节课申请第i+1节课不申请和第i节课申请第i+1节课不申请的期望同理可得，不重复给出。

由此我们可以知道 $E(X_i)$ 的取值只和 i ，第 i 节课是否申请，第i+1节课是否申请决定，因此可以用dp处理，设$dp[i][j][1/0]$ 表示前i节课，已经申请换了j次，第i节课是否申请（1表示申请，0表示不申请）的距离期望。

写出其中的一种转移：

$dp[i+1][j][0] = min(dp[i][j][0] + dis[c[i]][c[i+1]],dp[i][j][1]+k[i] * dis[d[i]][c[i+1]] +(1-k[i]) * dis[c[i]][c[i+1]])$

上式表示前i+1节课已经申请了j次，且第i+1节课不申请的距离期望可以由前i节课已经申请了j次且第i节课申请或者不申请两种可能取min得到。

对于$dp[i+1][j][1]$ ,需要考虑第 i+1 节课申请是否成功，然后对第i节课是否申请取min进行转移，不再详细给出。

随机游走： 对于一个无向图，每次从一个点等概率地选择与这个点相连的一条边然后移动到另一个点。

第一问求解：

首先运用用到分阶段的思想和期望的线性性，令$E(X_i)$ 表示起点在i，到第一次到达i+1的期望时间，对于一条链从1号点走到n号点的期望时间等于从1号点走到2号点，然后从2号点走到3号点….最后从n-1号点走到n号点的期望和，则$E(X) = \displaystyle\sum_{i = 1} ^ {n-1} E(X_i) $。

计算$E(X_i)$：

从i号点出发走到i+1号点有两种情况：直接一次从i走到i+1，或者走到i-1号点然后再走到i+1号点，于是可得：$E(X_i) = \frac{1}{2} * 1 +\frac{1}{2}(1+E(X_{i-1})+E(X_i))$，化简可得：$E(X_i) = 2 + E(X_{i-1})$,根据等差数列，可知：$E(X_i) = 2 * i-1$。

计算$E(X)$:

$E(X) = \displaystyle\sum_{i = 1} ^ {n-1} E(X_i) = (n-1)^2$

第二问求解：

对于一个完全图，每个点到其他所有点的概率都是相同的，从一个点走到另外一个点的期望时间的随机变量是正整数集合（即可能为无穷大），且每次行为都只有两种情况：走到和未走到，每次行为独立且概率保持不变，此模型类似掷硬币模型，可以直接使用结论：期望就是概率的倒数（证明见上文“经典例子”中例子一的证明过程）。对于此题，从S走到T的概率为$\frac{1}{n-1}$，则$E(X) = n-1$。

题目补充：如果取到的硬币为两端则收益为0。

首先运用用到分阶段的思想和期望的线性性，令 $X_{i,j}=
\begin{cases}
1& \text{第i个硬币和第j个硬币相遇过从而产生收益}\\
0& \text{otherwise}
\end{cases}$，则$X = \displaystyle\sum_{i+1<j} X_{i,j} * W_i * W_j $($i$

和 $j$ 之间能产生收益的前提是 $i$ 和 $j$ 不相邻，中间的硬币被取走，使得 $i$ 和 $j$ 相连产生收益，故 $i+1<j$ )，于是可得：$E(X) = \displaystyle\sum_{i+1<j}E(X_{i,j}) * W_i * W_j$

考虑如何计算$E(X_{i,j})$：

只有 $i$ 和 $j$ 之间的硬币都在 $i$ 和 $j$ 之前都被拿走了，$i$ 和 $j$ 之间才可能产生收益，对于某一种取法其实就是一个排列，对于i到j这几个硬币，一共有 $(j-i+1)!$ 个排列，对于 $i$ 和 $j$ 之间的硬币一共有$(j-i-1)!$个排，则$P(X_{i,j} = 1) = \frac{(j-i-1)! * 2}{(j-i+1)!} = \frac{2}{(j-i+1){(j-i)}}$，$E(X_{i,j}) = 0 * P(X_{i,j} = 0) + 1 * P(X_{i,j} = 1) = \frac{2}{(j-i+1)(j-i)}$。

2.5 线性性与等价性的应用

如果有n个等价的事件 $X_i$ ，他们是同分布的，即期望相同，且对这n个事件求和可得$\displaystyle\sum_{i = 1}^nX_i = C$ ，那么$E(X_i) = \frac{C}{n}$。

例1：

设 $X_i=
\begin{cases}
1& \text{p[i]是前k大的数}\\
0& \text{otherwise}
\end{cases}$，由于$\displaystyle\sum_{i =1}^nX_i = k$（一共有k个前k大的数，所以共有k个X取值为1），那么$\displaystyle\sum_{i = 1}^{n}E(X_i) = k$,$E(X_i) = \frac{k}{n}$。

例2：

设$X_i=
\begin{cases}
1& \text{i节点已经被染黑}\\
0& \text{otherwise}
\end{cases}$，那么$E(X) = \displaystyle\sum_{i = 1}^nE(X_i)$，问题就转换成求解$E(X_i)$。$E(X_i) = P(X_i = 1)$，即期望等于 $i$ 号点被染成黑色的概率。我们知道，$i$ 号点为白色的前提是它的祖先都没被染色，假设有 $k$ 个点，那么 $i$ 号点被染黑的概率其实就是这 $k+1$ 个点中，$i$ 号点最先被选中的概率，即$P(X_i = 1) = \frac{1}{k+1}$，树中祖先个数等于节点的深度-1，则$E(X) = \displaystyle\sum_{i = 1}^n\frac{1}{dep_i}$。

例3：

设$X_i=
\begin{cases}
1& \text{第i堆石子被扔了}\\
0& \text{otherwise}
\end{cases}$，则$X = \displaystyle\sum_{i = 1}^nX_i$，表示整个事件是由每堆石子是否被扔组成的。则$E(X) = \displaystyle\sum_{i = 1}^nE(X_i)$,由于第一堆石子最终必须被扔，则$E(X_1) = P(X_1) = 1$。对于其余堆的石子，它们能被扔的前提是第 1 堆石子还没有被扔，那么$P(X_i) = \frac{a_i}{a_1+a_i}$，综上可得：$E(X) = 1 + \displaystyle\sum_{i = 2}^{n}\frac{a_i}{a_i+a_1}$。

例4：

设$X_i=
\begin{cases}
i& \text{p[i]>max(p[i-1],p[i+1])}\\
0& \text{otherwise}
\end{cases}$,$E(X) = \displaystyle\sum_{i = 1}^nE(X_i)$,对于 $i = 1或n$，由于只和一个数比较，且是随机排列的，所以有 $\frac{1}{2}$ 的概率使得第 $i$ 个数较大，则$E(X_1) = \frac{1}{2},E(X_n) = \frac n2$,对于其他的数，由于和两个数比较，则概率为 $\frac13$，故$E(X_i) = \frac i 3$,因此$E(X) = \frac12+\frac n 2+ \displaystyle\sum_{i = 2}^{n-1} \frac i3$。

例5：

极长定义是这个子串的左边和右边都不为1。 假设有 $k$ 个极长子串，第 $i$ 个子串的长度为 $len_i$ ,设 $X = \displaystyle\sum_{i=1}^klen_i^2$,即该01串的价值。对于一个长度为 $n$ 的串，它的子串个数为 $\frac{n*(n-1)}{2}$，如果我们定义 $X_{l,r}=
\begin{cases}
1& \text{从l到r全为1}\\
0& \text{otherwise}
\end{cases}$，则$P(X_{l,r}) = (\frac{1}{2})^{r-l+1} = E(X_{l,r})$，因为是等概率随机的01串，所以每个字符为1的概率为 $\frac12$，故总概率为 $(\frac 12)^{r-l+1}$，则$E(\displaystyle\sum_{l\le r} X_{l,r}) = \displaystyle\sum_{l \le r}(\frac 12)^{r-l+1}$。可是$E(\displaystyle\sum_{l\le r} X_{l,r})\neq E(X)$。我们考虑某个极长全1连续子串，其区间为 $[l,r]$ ,长度为 $len$ ,则这个子串对 $X$ 的贡献为$len^2$,但是对 $X_{l,r}$ 的贡献为$\frac{len(len+1)}{2}$,所以我们可以得到：$2X_{l,r} – len = X$，其中 $len$ 表示 1 的个数，也可以表示成$\displaystyle\sum_{i=1}^nX_{i,i}$。于是，$E(X) = E(2X_{l,r} – \displaystyle\sum_{i=1}^nX_{i,i}) = 2\displaystyle\sum_{l \le r}(\frac{1}{2})^{r-l+1} – \frac{n}{2}$。

例6：

设$X_i=
\begin{cases}
1& \text{p[i]为p[1…i]的最大值}\\
0& \text{otherwise}
\end{cases}$,我们已知$E(X_i) = \frac1i$(见前文”经典例题”的例子一),$X = \displaystyle\sum_{i = 1}^nX_i$，那么$E(f(p)) = \displaystyle\sum_{i = 1}^nE(X_i) = \displaystyle\sum_{i = 1}^n\frac1i$。下面求解$f(p)^2$的期望，即$E(X^2)$, 由于$(\displaystyle\sum_{i = 1}^nX_i)^2= \displaystyle\sum_{i = 1}^n\displaystyle\sum_{j=1}^nX_iX_j = \displaystyle\sum_{i\neq j}^NX_iX_j+\displaystyle\sum_{i=1}^nX_i^2$，由于 $X_i$ 取值为 0 或 1，所以$X_i^2 = X_i$，则$E(X^2) = E(\displaystyle\sum_{i\neq j}^nX_iX_j)+E(\displaystyle\sum_{i=1}^nX_i)$,$E(\displaystyle\sum_{i=1}^nX_i) = \displaystyle\sum_{i = 1}^n\frac1i$。$E(\displaystyle\sum_{i\neq j}^nX_iX_j) = \displaystyle\sum_{i\neq j}^n \frac{1}{i * j}$，我们假设$i<j$，那么就是要同时满足 $p[i]为p[1…i]的最大值和p[j]为p[1…j]的最大值$。由于是随机排列，所以这两个条件互不影响，概率分别为$\frac 1i和\frac1j$，则同时满足的概率为$P(X_iX_j) = \frac1{i * j} = E(X_iX_j)$。综上：$E(X^2) = \displaystyle\sum_{i\neq j}^n\frac1{ij}+\displaystyle\sum_{i=1}^n\frac1i$。

例6：

先考虑 $k\le 50$的情况：

我们令 $dp[i][j]$ 表示已经拼接了 $i$ 个串，且经过kmp完成匹配查找后T串中的指针指向 $j$ 位置，复杂度为 $O(n^3)$，伪代码如下：

int kmp(char *s, char *t,&pos)//返回成功匹配的次数，&pos用于返回匹配结束时j指针在T串中的位置
for i : 1 -> k //枚举拼接次数
    for j : 1 -> len //len表示T串长度，枚举匹配后指向T串的可能位置
        for kk = 1 -> n //枚举所有可能拼接的字符串
            cnt = kmp(s[k],T,pos);
            dp[i+1][pos] = dp[i][j] + cnt*1.0/n;//匹配的次数为cnt次，选中i串的概率为1/n，期望为cnt/n

再考虑 $k\leq 10^{12}$的情况：

有一个性质：设 $f[i]$ 表示已经拼接 $i$ 次后的期望次数，当 $i > |T|$ 时，可得 $f[i+1]-f[i] = f[i+2] – f[i+1]$。

因为 $T$ 串的长度为 $|T| = 50$ ，那么对于一个在 $S$ 上新拼接的字符串，要产生一个新的 $T$ 串，只可能和原$S$串的前50个字符有关系，所以每次拼接可以产生的新 $T$ 串的个数最多只和最近的50次拼接有关，当拼接次数大于50时，由于是随机拼接，所以期望的增量是不变的，所以当 $k>50$ 时可以 $O(1)$ 算出。

三、计数问题

3.1 拓扑序

$\displaystyle\sum f(E) = \displaystyle\sum_{E\in T}\displaystyle\sum_{p \in P}G(E,p)$,表示先枚举所有的边集，然后再枚举此边集的所有排列，$G(E,p)$ 表示如果对于边集 $E$ ，排列 $p$ 满足拓扑序，则$G(E,p) = 1$，否则为 0 。我们可以调换求和的顺序得到 $\displaystyle\sum f(E) = \displaystyle\sum_{p \in P}\displaystyle\sum_{E\in T}G(E,p)$,这样就变成了先找到所有可能的排列（拓扑序，然后对于每个排列，看有几个边集满足此拓扑序。一个边集如果满足拓扑序，需要满足 $\forall E(a,b)\in T,p[a]<p[b]$，即对于任意的边(a,b)，都要满足a在排列中的位置要在b之前。那么可以得到，如果一共有 $k$ 条边满足 $p[a]<p[b]$ ，那么满足排列p为一个拓扑序的边集个数为 $2^k$（k个边随意取的方案数）。

下面用状压dp来求解k，我们可以设$dp[s]$，表示排列的方案为s(状态压缩的十进制表示)时，满足的边集的子集数量，转移的伪代码如下：

for i 1 -> (1>>20)
    遍历找到所有的1，放入点集D
    枚举每一个0，设这个点为b，统计有多少条边[a,b],其中a∈D,将统计值记录到cnt中
    dp[s'] += cnt//s'表示加入一个0点后的十进制数

3.2 位运算相关的计数问题

位运算性质：1.独立性（一般每一位互不影响）；2.高位优先。

XOR之和

设$bit(x,i)=
\begin{cases}
1& \text{x的第i位为1}\\
0& \text{otherwise}
\end{cases}$，那么 $a \ xor\ b = \displaystyle\sum_{i=0}^{29} 2^i * (bit(a,i)\neq bit(b,i))$，$ans = \displaystyle\sum_{i<j}^na[i]\ xor \ a[j] = \displaystyle\sum_{i<j}^n\displaystyle\sum_{k=0}^{29}2^k * (bit(a,i)\neq bit(b,i)) = \displaystyle\sum_{k=0}^{29}2^k\displaystyle\sum_{i<j}^n(bit(a,i)\neq bit(b,i))$ ,对于后半段，其实就是看一下所有数字的第k位有几个0和几个1，分别记为 $num_0 \ 和 \ num_1 $，则 $ans = \displaystyle\sum_{k=0}^{29}2^knum_0 * num_1$。

异或排序

如图所示，对于两个数如果按位比较大小，遵循高位优先原则，比较形式肯定是二进制表示的前一部分都相同然后出现一个不同。同时可以知道，如果a[i]^s的前半部分和a[i+1]^s的前半部分相同，那么a[i]和a[i+1]的前半部分肯定也相同，设不同的位置为i。则若$a[i] = 1,a[i+1] = 0$，则$S[i] = 1$时才能满足大小关系，同理$a[i] = 0,$a[i+1] = 1$时，$s[i] = 0$。由于一共有n个数，则有n-1个大小关系，共n-1个限制条件，找出满足n-1个限制条件的所有S即可。

和的XOR

第一问：

考虑对于第 $i$ 位，计算有多少 $a[x]+a[y]$ 的第 $i $ 位为1，如果是奇数个则最终答案的第i位也为1。如果$a[x]+a[y]$ 的第 $i$ 位为1，则$(a[x]+a[y])\ mod\ 2^{i+1} \ge 2^i$。所以如果$(a[x]\ mod\ 2^{i+1}) + (a[y]\ mod\ 2^{i+1})$ 第 $i$ 位为1，只可能在$[2^i,2^{i+1}-1]或[2^i+2^{i+1},2^{i+2}-1]$中,将所有的a取模后排序，然后用双指针，L指向最小的，R指向最大的 $O(n)$ 扫描一遍就能求出第i位有几个满足的，处理完每位就能得到最终答案。

第二问：

对于所有的$i\neq j$，$a[i]+a[j]$ 会被统计两次，那么两个相同的数异或起来为0，所以都相互抵消了，只需要把 $2 * a[i]$ 异或起来就行。