置换期望环数
wr /bx /bx /bx
求 \(n\) 元置换环的期望数量，答案是 \(\sum _{i = 1} ^n \dfrac{1}{i} = \mathcal{O(\ln n)}\) 的。
考虑归纳：\(n = 1\) 成立。
如果 \(n\) 元置换的期望环数量是 \(1 + \dfrac{1}{2} + \dfrac{1}{3} + \dfrac{1}{4} + \cdots + \dfrac{1}{n}\)，下面证明 \(n + 1\) 元置换的期望环数量是 \(1 + \dfrac{1}{2} + \dfrac{1}{3} + \dfrac{1}{4} + \cdots + \dfrac{1}{n} + \dfrac{1}{n + 1}\)。
首先有 \(\dfrac{1}{n + 1}\) 的概率出现自环，剩余的情况 \(p(n + 1) \in [1, n]\) ，设原来 \(p(j) = p(n + 1)\)，那么这个“置换”内就有两个点指向 \(p(n + 1)\) 了，所以直接构造新置换使得 \(p(j) = n + 1\) 就好，发现这是不重不漏的，所以期望环数量是 \(1 + \dfrac{1}{2} + \dfrac{1}{3} + \dfrac{1}{4} + \cdots + \dfrac{1}{n} + \dfrac{1}{n + 1}\)。
弧上长度最大值
有一段弧 \(AB\)，要在弧 \(AB\) 上找一个点 \(P\) 使得 \(AP+BP\) 取得最大值。
设这段弧角度 \(\alpha\)，半径 \(r\)，而所选的点 \(P\) 满足 \(\angle AOP = x\)，那么 \(AP + BP = 2r\sin x + 2r\sin (\alpha - x)\)。
化简得 \(f(x) = 2r[\sin x + \sin (\alpha - x)]\)。
导数 \(f'(x) = \cos x - \cos (\alpha - x) = 0\)，此时 \(x = \alpha - x\)，\(x = \dfrac{\alpha}{2}\)，所以 \(P\) 取在圆弧中间就对了。
简单博弈 1
现在有一个排列 \(1, 2, 3, \cdots, 60\)，Alice 和 Bob 要在 \(59\) 个间隔中依次放入 \(+,-,\times\)，最后如果 \(\bmod 3 = 0\) 先手就赢了。
首先可以转化为循环序列 \(1, 2, 3, \cdots, 1, 2, 3\)。先手在 \(30\) 号正中间的间隔放一个 \(+\)，后手在 \(i\) 位置放先手就在 \(i + 30\) 或 \(i - 30\) 位置放就行了。
最后对称。
拆分数
给定一数 \(m\)，构造序列 \(\{a\}_n\)，使得 \(\sum a = m\)，\(V = n\sum_{i = 1} ^n a_i^2\)，求 \(V_{\min}\) 和 \(V_{\max}\)。