概率

在这里放一些常见的概率模型.

1. 如果某件事情发生的概率是p,那么期望进行多少次试验才能让p发生的次数是1/p.

2. 你有7种物品,每种物品有ai个,你可以随意排列这7种物品,问序列中连续7个物品都不一样的期望次数.
   你会发现从每个位置随机排列,7个连续都不一样的概率是相等的.
   设7个连续相等的概率为P,那么答案就是(n-6)P,有这么多位置,每位都相等.
   P也好求:每个位置选一个,最后让这7种随机排列即可,为

   $$(7!)\frac{a1}{n}\times \frac{a2}{n-1}\times ...\frac{a7}{n-6}$$

   乘起来即可.

模式匹配问题

猴子每次会在键盘上随机敲击一个字母,请问出现指定字符串s的期望敲击次数是多少?

结论:期望次数是

$$\sum V^l$$

其中V表示值域大小(所有字母的集合大小),l表示字符串所有前缀等于后缀的长度.
如 ABRACADABRA ,答案是 $26^{11}+26^{4}+26$ ,因为前缀A和后缀A匹配,前缀ABRA和后缀ABRA匹配,整个字符串是前后缀匹配的.

(引用)这个结论乍一看违反直观，为什么首次出现正正和正反的期望次数不相同？这是因为，模式等待中途失败时，模式的头部和尾部重合越多，就越容易从头再来；而重合的越少，就越容易从中间继续。在得到正面的情况下，接下来等待正正失败（出现反），就要从头再来等两个正面；而等待正反失败（出现正），则还是得到正面，仍只需等一个反面。

势能法

看这个
看这个

1. CF1025G 有n个公司可能是自由的或者被合并的,每次会随机选出ab两个自由公司,然后等概率让a合并b或b合并a,被合并的公司的所有子公司都会变成自由状态,求第一次所有公司被一家公司合并的期望次数.

   势能法 :设S是当前局面,F(S)是当前局面势能,F(N)是结束局面的势能,令F(N)-F(S)是期望次数.将局面势能落到具体每个节点的势能: $F(S)=\sum f(a_i)$ ,其中 $a_i$ 是每个节点的势能,只和这颗”树”的大小有关.

   随机两个数ab,模拟合并的过程:

   $$f(a)+f(b)+1=\frac{af(0)+bf(0)+f(a+1)+b(b+1)}{2}$$

   前面是ab的势能和, $+1$ 是因为发生一次合并之后势能总要往高走(不然怎么算期望),然后根据轮换对称性可以直接把ab独立出来:

   $$f(a)+\frac12=\frac{af(0)+f(a+1)}{2}$$

   由于势能是一个相对的概念,f(0)可以随便取,取0得到

   $$f(a)=2^a-1$$

   加起来减一下即可.

停时定理

这一部分的题很难,cf几乎都在2800-3500左右.

随机游走(简单版)

o-o-o-o-o
q1^     q2
 now

你在一条链上.你有 $\frac12$ 的概率往左走一格, $\frac12$ 的概率往右走一格.走到最左端(0)有 $q_1$ 的概率赢,走到最右端有 $q_2$ 的概率赢.求你最终赢的概率.

结论:在距离0 $x$ 点位置的概率是 $\frac{x}{n+1}q_1+\frac{n+1-x}{n+1}q_2$ ,直观理解就是调和一下.