D. Jellyfish and Miku

从 $0$ 到 $n$ 的期望步数可以拆成从 $i$ 到 $i+1$，也即通过每条道路所需的期望步数之和。

Read More

偏导数

偏导数用于描述一个多元函数在某个维度的变化率。

Read More

CF838C Future Failure

这个游戏性质非常好，因为两个操作其实是独立的，无论进行哪种操作都不会使游戏局面发生太大的变动。

Read More

Erdos-Ginzburg-Ziv Theorem

对任意 $2n-1$ 个整数，可以从中选出 $n$ 个使得这 $n$ 个数的和是 $n$ 的倍数。

形式化的，对任意 $a_1,\dots,a_{2n-1}\in \mathbb Z$，存在两两不同的 $i_1,\dots,i_n$ 使得：
$$
a_{i_1}+\dots+ a_{i_n}\equiv 0\pmod n
$$

Read More

Description

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

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

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

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

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

$n\le 500$

Read More