这是2017-07-05到2017-07-06的做题记录。

涵盖威佐夫博弈、Nim博弈、SG函数及其各种应用。

Möbius 反演

（读这篇文章前，建议先使用容斥原理解决POJ3904）

现在假设我们要得到一种函数$\mu(d)$，这种函数具有以下性质：

$$ \begin{equation}f(n)= \sum_{d|n} \mu(d) = \begin{cases} 1, & n = 1 \\ 0, & n > 1 \end{cases} \end{equation} $$ 例如 $$ \begin{align*} f(1)&=\mu(1)=1\\ f(2)&=\mu(1)+\mu(2)=0\\ f(3)&=\mu(1)+\mu(3)=0\\ f(6)&=\mu(1)+\mu(2)+\mu(3)+\mu(6) =0\\ \end{align*} $$ 我们可以得到这个函数的前12个值：

m	1	2	3	4	5	6	7	8	9	10	11	12
\mu(m)	1	-1	-1	0	-1	1	-1	0	0	1	-1	0

Richard Dedekind 和 Joseph Liouville 发现了一个反演定理： $$ F(n)=\sum _{d|n}f(d)\Longleftrightarrow f(n)=\sum _{d|n}\mu(d)F(\frac{n}{d}) $$ 莫比乌斯函数： $$ \mu(n) = \begin{cases} 1, &n=1 \\ (-1)^k, & {n=p_1p_2...p_k, p_i互不相同} \\ 0, & \text{其它情况} \end{cases} $$

POJ3904 & more

题意

输入n, 输出$\sum_{1\leq i\leq n}gcd(i,n)$。

Input	Output
2	3
6	15

稳定的传送门

来一次真正的户外露营，烧烤之后去爬山，去看南京的万家灯火，一览众山小！
甚至还有露天电影，露天KTV！
以及无限量的烧烤食材和丰富多彩的活动！

本篇又称为《30分钟离散数学从入门到被锁在门里》，《降金忠三十八问》。

The Infinite Staircase

荷兰插画师M.C.Escher有一幅著名的画作，画的是一个封闭循环的楼梯，级级盘旋而上，一周之后又回到起点，被称为不可能的楼梯，也叫《The Infinite Staircase（无尽楼梯）》。

Ramsey定理

定理描述

Ramsey定理要解决的是如下问题：
如何正确剥皮
要找这样一个最小的数n，使得 n 个人中必定有 k 个人相识或 l 个人互不相识。

范围最值查询（RMQ）

RMQ的一般形式表述为：对于长度为n的数列A，查询q(l, r)，返回A[l…r]之间的最大值(最小值等)。

POJ 3368

Portal: http://poj.org/problem?id=3368

题意：

有一个单调不减的序列a[n], 问子序列a[l…r]中，出现次数最多的数的出现次数（好像有点拗口，还是看例子吧）。
比如：序列为 -1 -1 1 1 1 1 3 10 10 10，a[5…10]中，出现次数最多的数是10，它的出现次数是3，所以要输出3。

题意

原题目：http://coursera.cs.princeton.edu/algs4/assignments/percolation.html

percolate 渗透，扩散
给定一个正方形的图，图上每个点(site)的状态初始为非open，即下图中的黑色部分，现在随机逐个打开其中的某些site，使之转变为open状态，判断上下是否联通，即相当于从图上方灌水，问是否能渗透到最底下。

现在把能够渗透的状态称为percolate
若要表示图percolate的概率和单个点open的概率的关系，可以用以下的曲线图表示：

左边的是20x20的图，右边是100x100的矩阵。