[置顶] 2023 笔记
Catalan 数
Catalan 数表示为 $C_n$，有通项 $C_n=\dfrac{\binom{2n}{n}}{n+1}$ 和递推式 $C_n=\sum_{i=1}^nC_{i-1}C_{n-i}$，定义应该使用的是递推式。
做题笔记 2023.2
CF808G Anthem of Berland
数据范围明示 dp。首先在模式串上跑 kmp，预处理失配指针，dp 时遇到问号就暴力枚举字符集中每个字母，复杂度为 $O(|\Sigma|\cdot|S|\cdot|T|)$，可以卡过。
Solution. CF1025G Company Acquisitions
Description
有 $n$ 个结点，每个结点有两种状态：active 和 acquired。
一个 active 结点后面跟着若干 acquired 结点。
对于两个 active 结点 $A,B$，如果 $A$ 收购 $B$，那么所有跟着 $B$ 的结点变为 active，$B$ 变为 acquired 并跟在 $A$ 后面。
每次随机选择两个 active 结点，随机让其中一个收购另一个。
求只剩一个 active 结点的期望步数。
$n\le 500$