D

dfs一棵树,访问子节点顺序随机
求到达每个节点的时刻的期望

概率DP

$d_v = \frac{sum - sum_v}{2}d_u + 1$

sum 为u的所有子树的节点和

u的其余子节点在v之前被访问的概率为0.5

复杂度 $O(n)$

E

有三个杯子,中间的杯子有球,每次将中间杯子随机与两边的一个互换位置
求n次互换后中间杯子有球的概率,用分数表示

数学 通项公式

$p_1 = 0$
$p_i = (1-p_{i-1})/2$

通过观察发现分子为$2^{n-1}$,分母可以通过矩阵快速幂求解(oeis…)

或者用数列求通项的技巧求得
formula

只需要用快速幂求$2^{n-1}$就行了…

复杂度 $O(logn)$

F

给定n个串以及它们的价值
现在求一个长度为l的串,给定串每出现一次边加上相应价值
求最大的价值

AC自动机 矩阵快速幂(floyd倍增)

先将模板串构建AC自动机,然后形成了一张图,每个结点有对应价值

对于一次,我们可以floyd跑最长路
而对于l次我们就可以用矩阵快速幂倍增