Description

有 $n$ 个结点，每个结点有两种状态：active 和 acquired。

一个 active 结点后面跟着若干 acquired 结点。

对于两个 active 结点 $A,B$，如果 $A$ 收购 $B$，那么所有跟着 $B$ 的结点变为 active，$B$ 变为 acquired 并跟在 $A$ 后面。

每次随机选择两个 active 结点，随机让其中一个收购另一个。

求只剩一个 active 结点的期望步数。

$n\le 500$

Read More

Catalan 数

Catalan 数表示为 $C_n$，有通项 $C_n=\dfrac{\binom{2n}{n}}{n+1}$ 和递推式 $C_n=\sum_{i=1}^nC_{i-1}C_{n-i}$，定义应该使用的是递推式。

Read More