最近做的两道题。

感觉很囧啊，数学全忘了啊。

Google-Codejam-Round3-D

果然 GCJ 滚粗是必然的。

考虑一个事实：在 \(i\) 到 \(j\) 这一段的一个位置 \(k\) ，如果 \(k\) 是 . ，那么 \(i\) 到 \(k\) 和 \(k+1\) 到 \(j\) 是独立的，即，如果某次一个人进入摩天轮时，他遇到的第一个格子在 \(i\) 到 \(k\) 之间，那么他最后占领的格子一定会在 \(i\) 到 \(k\) 中而不会在 \(k+1\) 到 \(j\) 中。

于是就倒着来思考。首先明显的在最后只剩下一个空的时候，期望是固定的，为 \(\frac{n - 1}{2}\) 。

所以我们枚举最后一个空的位置，然后转为序列上的问题。

序列上的问题有明显的子结构：令 \(f_{i, j}\) 表示原序列的 \(i\) 到 \(j\) 这一段，经过若干次操作后，除位置 \(j\) 为 . 以外，其余的元素均为 X 的期望代价， \(p_{i, j}\) 表示概率。令 \(P(i, j, k)\) 表示 \(i\) 到 \(j\) 这一段， \(j\) 一直是 . 的，最后一个转为 X 的 . 的位置为 \(k\) ，其余的都是 . 的概率。

\[P(i, j, k) = \binom{Lk + kR}{Lk} (\frac{k+1-i}{j+1-i})^{Lk+1} (\frac{j-k}{j+1-i})^{kR} p_{i, k} p_{k+1,j}\]

其中 \(Lk\) 表示初始状态中 \([i, k - 1]\) 中 . 的个数， \(kR\) 表示 \([k+1, j-1]\) 中 . 的个数。由于最后一个转为 X 的 . 为 \(k\) ，所以我们要考虑到前 \(Lk + kR\) 次 X 变 . 的顺序，所以要乘以一个二项式。再乘以有 \(Lk + 1\) 个落在 \([i, k]\) 的概率，以及又 \(kR\) 个落在 \([k+1,j]\) 的概率，最后乘以合法的概率 \(p_{i, k} p_{k+1,j}\) 。

所以得到 \(f\) 和 \(p\) 的转移如下：

\[ \begin{array}{rcl} p_{i, j} & = & \sum_{k = i}^{j - 1} P(i, j, k) \\ f_{i, j} & = & \frac{1}{P_{i, j}}\sum_{k = i}^{j - 1} P(i, j, k) (f_{L, k} + f_{k+1, R} + n - \frac{k-i}{2}) \\ \end{array} \]

注意 dp 时的 \(i\) 可能大于 \(j\) ，因为这是环状，所有计算长度的公式都需要进行一定的修正。

TopcoderOpen-Round3-Level3

\(\newcommand{\stirone}[2]{\left\{ { #1 } \atop { #2} \right\} }\) \(\newcommand{\stirtwo}[2]{\left[ { #1} \atop { #2} \right] }\) jzp 的神题，我表示被吓傻了……

我还是直接上 传送门 吧……我就写写我的感觉 →_→

主要思想

感觉非常牛逼啊。

1. 用容斥写出答案的表达式
2. 观察这个表达式和 \(\Delta^n f(x)\) 很像，于是用 \((-1)^n \Delta^n f(x)\) 来求答案
3. 具体化 \(f(x)\) 。如何求 \(\Delta^n f(0)\) ？考虑写成 \[f(x) = \sum a_i x^i = \sum b_i \binom{x}{i}\]
4. 可以得到 \[\Delta^n f(0) = b_n\] 所以求 \(b_n\) 就好了……

一些细节

考虑如何求 \(b_n\) ？利用 \[x^n = \sum_{k=0}^n k!\stirone{n}{k} \binom{x}{k}\] 可以得到 \[b_n = n! \sum_{k = n} \stirone{k}{n} a_k\]

于是我们只要求 \(a\) 就好了。利用 \[\binom{n}{k} = \sum_k \stirtwo{n}{k} (-1)^{n-k} x^k\] 可以拆开一个 \(n\) 中含有未知数的二项式。

如何求两类 stirling 数？题目中说了 \(m - n \leq 10^3\) ，于是我们要在 \(m - n\) 相关的的时间内求出所有涉及到的 stirling 数。假如我们要求 \(\stirone{n}{m}\) ，当 \(n - m\) 特别小时，考虑 \(\stirone{n}{m}\) 的实际意义，表示将 \(n\) 个数分成 \(m\) 个环的方案数，至多有 \(n - m\) 个环的大小不为 1 ，这些环的大小之和至多是 \(2(n - m)\) ，于是考虑 \(f(i, j)\) 表示 \(j\) 个大小大于 2 的环的总大小为 \(i\) 的方案数，可以得到一个和 stirling 数类似的递推。

从 xiaodao 空间上看到的……

感觉蛮好玩的于是就试了试。xiaodao 最后的那个连乘真的没有想到，我只会暴力积分……

Problem

\(d\) 维单位球体中随机选 \(n\) 个点，到球心 \(k\) 远点距离球心的期望是多少？

Solution

\(n\) 个点，随机选一个为 \(k\) 远点，再选 \(k - 1\) 个点为前 \(k - 1\) 远点，方案数为 \(\binom{n}{1, k - 1}\) 。

（维基百科） \(d\) 维单位球体的体积是 \[V_d(R) = \frac{\pi^{\frac{d}{2}}R^d}{\Gamma(\frac{d}{2}+1)} = C_d R^d\] 其中 \(C_d\) 为与 \(d\) 相关的常数。

根据“维”的定义，我们有距离为 \(r\) 的点的密度为 \[\rho(r) = \frac{V'_d(r)}{V_d(1)} = d r^{d - 1}\]

于是 \(k\) 远点的期望是： \[\begin{array}{rl} & \binom{n}{1, k - 1} \int_0^1 r \rho(r) (r^d)^{k-1} (1 - r^d)^{n-k} \mathrm{d} r \\ = & d \binom{n}{1, k - 1} \int_0^1 r^{kd} (1 - r^d)^{n-k} \mathrm{d} r \\ = & nd \binom{n - 1}{k - 1} \int_0^1 r^{kd} \sum_{i=0}^{n-k} \binom{n-k}{i} (-r^d)^i \mathrm{d} r \\ = & nd \binom{n - 1}{k - 1} \sum_{i=0}^{n-k} \binom{n-k}{i} (-1)^i \int_0^1 r^{kd+id} \mathrm{d} r \\ = & nd \binom{n - 1}{k - 1} \sum_{i=0}^{n-k} \frac{\binom{n-k}{i} (-1)^i}{kd+id+1} \\ \end{array} \]

这样做的值应该是没错的，但是精度误差特别大 >__<

于是我们还需要继续化简……

我对如何操作二项式已经忘得差不多了，于是无意间拿起 CM 居然看到了这货：

对于函数 \(f(x)\) ，定义 \(\Delta^{(0)} f(x) = f(x)\) 。然后可以定义 \(\Delta^{(n)} f(x) = \Delta^{(n - 1)} f(x + 1) - \Delta^{(n - 1)} f(x)\) ，然后可以得到： \[\Delta^{(n)} f(x) = \sum_{k} \binom{n}{k} (-1)^{n-k} f(x+k)\]

注意到 \(\Delta^{(n)}f(x)\) 的表达式与要化简的那个式子中的比较像，考虑令 \(f(x) = \frac{1}{x}\) ， 用 \((-1)^{n-k} \Delta^{(n - k)} f(x)\) 来代替 \(\sum\) 。

\[\begin{array}{rl} & nd \binom{n - 1}{k - 1} \sum_{i=0}^{n-k} \frac{\binom{n-k}{i} (-1)^i}{kd+id+1} \\ = & n \binom{n - 1}{k - 1} (-1)^{n-k} \sum_{i=0}^{n-k} \frac{\binom{n-k}{i} (-1)^{n-k-i}}{k+i+\frac{1}{d}} \\ = & n \binom{n - 1}{k - 1} \Delta^{(n - k)} f(k+\frac{1}{d}) (-1)^{n-k} \\ \end{array}\]

由于 \(f(x) = \frac{1}{x}\) ，我们又有： \[\begin{array}{rcl} \Delta^{(1)} f(x) & = & \frac{-1}{x^{\bar{2}}} \\ \Delta^{(2)} f(x) & = & \frac{2}{x^{\bar{3}}} \\ \Delta^{(3)} f(x) & = & \frac{-6}{x^{\bar{4}}} \\ \end{array}\]

其中 \(x^{\bar{k}} = \prod_{i = 0}^{k - 1} (x+i)\)

可以找出规律（然后归纳法）\[\Delta^{(n)} f(x) = \frac{(-1)^n n!}{x^{\bar{n+1}}}\]

继续代入： \[\begin{array}{rl} & n \binom{n - 1}{k - 1} \Delta^{(n - k)} f(k+\frac{1}{d}) (-1)^{n-k} \\ = & n \binom{n - 1}{k - 1} \frac{(-1)^{n-k} (n-k)!}{(k+\frac{1}{d})^{\bar{n-k+1}}} (-1)^{n-k} \\ = & \frac{n!}{(k-1)! (k+\frac{1}{d})^{\bar{n-k+1}}} \\ = & \frac{n!}{(k-1)! \prod_{i=0}^{n-k} (k+i+\frac{1}{d})} \\ = & \frac{\prod_{i=0}^{n-k}(n-i)}{\prod_{i=0}^{n-k} (k+i+\frac{1}{d})} \\ = & \prod_{i=0}^{n-k} \frac{(n-i)}{k+i+\frac{1}{d}} \\ = & \prod_{i=k}^{n} \frac{i}{i+\frac{1}{d}} \\ = & \prod_{i=k}^{n} \frac{di}{di+1} \\ \end{array}\]

这样化简的结果和 xiaodao 的方法是一样的……真是太开心了 @_@ ……

Epilogue

这推导真是恶心死我了……

学的东西都忘光了怎么破……

写的公式太多了感觉会跪？ @dyh 求查错……

Markdown 里的替换

大概是为了防止 TeX 里面的 _ 和 ^ 被转义而写的。由于要改多次……还是先记下来吧。

\([^\]\)^ -> \1\^
\([^\]\)_ -> \1\_

好久没做题了，前一段时间旅游了一小会儿然后趁着 **USC 的机会溜回家开始了长达七天的暑假生活。

闲着无聊做了一下 PE-432 ……

Problem

令 \[S(n, m) = \sum_{i=1}^{m} \phi(n \times i)\] 求 \(S(510510, 10^{11})\)

Solution

令 \(n = pq\) ，且 \(p\) 为质数，有 \[ S(n, m) = (p - 1) S(q, m) + S(n, \lfloor \frac{m}{p} \rfloor)\]

于是我们只要计算 \[S(1, m) = \sum_{i = 1}^m \phi(i)\] 即可。

线性筛法可以去死了。我们可以采用 @dyh 的理性愉悦 \(O(n^{\frac{2}{3}})\) 的方法：

令 \(S_f\) 表示函数 \(f\) 的前缀和函数，即 \[S_f(n) = \sum_{i = 1}^n f(i)\] 。我们要求 \(S_{\phi} (n)\) 。

令 \(g_n = \sum_{d|n} f_n\) 于是有 \[S_g(n) = \sum_{i = 1}^n \sum_{d|i} f(d) = \sum_{i=1}^n S_f(\lfloor \frac{n}{i} \rfloor)\] 这个等式只要注意到每个 \(f(i)\) 被加的次数都是 \(\lfloor\frac{n}{i}\rfloor\) 就好了。

如果我们能够快速计算 \(S_g(n)\) ，就可以利用 \[S_f(n) = S_g(n) - \sum_{i = 2}^n S_f(\lfloor \frac{n}{i} \rfloor)\] 来计算 \(S_f(n)\) 了。

当 \(f(n) = \phi(n)\) 时， \(g(n) = \sum_{d|n} f_n = n\) ，\(S_g(n) = \frac{1}{2} n(n+1)\) 。我们用筛法算出 \(i \leq n^{\frac{2}{3}}\) 时的 \(S_f(i)\) ，其余的暴力记忆化递归做下去，复杂度是 \(O(n^{\frac{2}{3}})\) 。

我一开始把 \(m\) 看成了 \(10^{14}\) 跑了 20min 才跑出来， \(m = 10^{11}\) 时只要 3s 就可以了……

这几天都忙着高考送考（以及考后狂欢）去了。一年毕业季，一年别离时。

（祝在高考这天生日的同学年年有今日，岁岁有今朝 23333）

IPSC 2013

IPSC 的题感觉蛮好玩的，但是非常难……

我一开始还没组队，然后 dyh 拉我组了一队，然后我就把 xlk 拉了进去。事实证明把 xlk 拉进去是个非常正确的决定。

practice

P

easy：不说了 - -

hard：看了 solution 才发现坑爹啊……居然连 l33t 语都出现了……我还是不吐槽了 >__<

Q

easy： 显然很水 - -

然后我就不会 hard 了 - -

hard：显然平均数是可以被忽略的。我们要构造的是方差，也就是找到一组 \(a_{1, \dots, n}\) 使得 \(\sum a_i = 0\) 且 \(\sum a^2_i = nv\) 。

考虑如下构造：序列长度为 \(2n\) ，且 \(a_{2k - 1} = -a_{2k}\) ，那么第一个限制显然就满足了，第二个限制直接贪心就好。

R

easy 也不难，(a-z)*25+a 就可以了。

然后 YY 了好久的 hard 没想法。于是我把很小的 n 的解的长度打出来放到 OEIS 上搜，发现了 这个序列 。OEIS 上还顺便提了一下某种较优解的构造方法，然后就没有然后了。

题解也是用的这种构造……

formal contest

完全不会啊亲……

所以你是来看题解的话是找不到任何东西的哈哈哈哈。

待我先去研究一番题解……

A

其实我没看题 2333

B

看了一眼后发现……这不是某个经典结论吗亲……

这个题我曾经 YY 过一个证明方法：令一个数 \(n\) 的势能 \(\phi(n) = \frac{n^2}{2}\) 。那么将 \(n\) 分成 \(x + y = n\) 两份时，释放的能量为 \(\phi(n) - \phi(x) - \phi(y) = xy\) ，这表示将 \(n\) 分成若干个数，释放的能量与具体分法是无关的。那么将 \(n\) 分成若干个 1 ，无论怎么分，释放的能量总为 \(\phi(n) - n \phi(1) = \frac{n(n - 1)}{2}\) 。

我以前一位同学 YY 出另外一个证法：考虑图 \(K_n\) ，把 \(n\) 分成 \(x+y = n\) 对应着图上选择两个点集，大小分别为 \(x, y\) ，并将这两个点集之间的 \(xy\) 条边的删掉。那么初始的时候有 \(\frac{n(n-1)}{2}\) 条边，结束的时候没有边（ \(n\) 个孤立的点），所以一共删了 \(\frac{n(n - 1)}{2}\) 条边。

C

easy ：你把函数 t 的值打出来，可以发现 \(t(n) = \phi(n) + 1\) ， \(\phi\) 为欧拉函数。

然后就可以直接跑了。这样会输出一个指令，然后照着这个指令依次做下去就好了。

为啥我和 dyh 都跑不出指令，就 xlk 可以？

hard ：可以得到当 \(b > 500\) 时， \(g(b)\) 一定是 1 。然后每次求 \(g\) 就可以 \(O(1)\) 求，然后会输出一堆点的坐标。然后就不会了……

题解如是说：把这些点的坐标全部画出来，然后可以得到一个二维码，用手机扫描可以得到一句话：88767->7123398 ，然后就是 easy 的节奏了。

D

easy： 就是昨天 R 的 checker 。首先我们想怎样检验一个排列是否出现过？肯定是每次选择最近的一个下一个字母。所以这样就可以 dp 了。 \(f_S\) 表示集合 \(S\) 中的所有元素按照一定顺序全部出现，所有的顺序中，最后一个字母出现的位置最靠后的一个位置是什么。转移的话枚举下一个字母就好了。

我写的比较渣，跑了 10min 才跑出来 >__<

hard：如果继续按照这个思路去做的话， \(f_{S, t}\) 表示集合 \(S\) 的排列中，最后一个元素出现的位置是 \(t\) 的方案数，内存会受不了 >__< 然后我也不会了...

E

居然没人出。。。

F

首先注意到，每次查询有 50+% 的正确率。

easy：三分。我们将序列分成 LMR 三段，每次查询 25 次 L 和 M 的关系，25 次 M 和 R 的关系，然后就可以确定在 \(L, R, M\) 中的哪一个，4 次就可以找到了。

hard：不会……

题解：我的理解是每次随机比较任意 83 枚与 83 枚，最后枚举那个是答案，用概率最大的？ @dyh 你怎么看……我都不好说什么了。

G

参见 Keshavarz-Kohjerdi, Fatemeh, Alireza Bagheri, and Asghar Asgharian-Sardroud. ”A linear-time algorithm for the longest path problem in rectangular grid graphs.” Discrete Applied Mathematics 160.3 (2012): 210-217.

呵呵呵呵呵呵

H

看了半天的 pdf 没找到答案啊……

easy：看网页源代码去 - -

hard：看 response header. 随便设置个包含 chocolate 的 cookie 发送过去，然后就会有一个问题，然后再发送一个 request ，修改 request header 使之包含答案，然后 response 里面就有答案了。

I

。。。

J

easy：xlk 如是说：由于 NAND gate 是 unversal unary gates ，J1。。随便取两个变量 与非 或者是 或非 ，然后就有六种了。然后看xy一不一样，如果一样返回xz的与非，否则随便返回一个。

hard：我想了一下，似乎可以直接爆搜所有函数？想起来都觉得好麻烦啊 >__<

题解如是说：不满足以下五个条件中的任意一个的函数就是 universal 的：

1. 如果输入全是 1 那么输出 1
2. 如果输入全是 0 那么输出 0
3. 如果把某个输入的 0 改为 1 ，则输出的结果不会由 1 变为 0
4. 如果把所有输入取反，那么结果也会取反
5. 每个输入要么总与输出相关，要么总与输出无关

K

easy：分开计算，直接乘起来。

hard：直接考虑下来的一步，如果这一步有 1 个格子，则上去有 1 种方案；有两个格子，则上去有 2 种方案；etc。然后还是递推一下就好。

L

easy：手玩吧哈哈哈哈

hard：不会……

我居然没去看看 hard 的形状，罪过罪过。

这就是个 3-SAT 问题啊……然后自己写个程序爆搜或者直接找第三方程序吧。

我以前一直很喜欢玩这种东西的啊，居然没发现 >__<

M

不会

problem 在此

根据 \(E(\sum X_i) = \sum E(X_i)\) 可以知道答案就是每个格子为白色格子的期望和。

对于第 \(1 \leq i \leq n\) 个格子，我们知道某次被翻转的几率是 \[p = \frac{2 i (n + 1 - i) - 1}{n^2}\]

令 \(f_k\) 表示 \(k\) 次翻转后仍然是白色的概率，可以得到 \[f_0 = 0, f_{k+1} = (1 - p) f_k + p (1- f_k)\] 可以化出 \[f_{k+1}- \frac{1}{2} = (1 - 2p) (f_k - \frac{1}{2})\] 于是有 \[f_k = \frac{1}{2}(1 + (1 - 2p)^k)\]

如果暴力做的复杂度是 \(O(10^{10} \log 4000)\) 。然后一个很小的优化是如果 \(1 - 2p \leq 0.99\) ，那么 \((1 - 2p)^k \leq 10^{-18}\) ，直接忽略不计了……

然后要跑 3min 才跑得出来。

如果有更好的做法求告诉我 >__<

（版面不够了于是只好用 display equation 来充版面么 LOL）

说好的 AFK 呢，还是忍不住参加了。

Solution

250 pts

慢慢码代码。不多说。

500 pts

考虑一条边 Ai-Bj 对答案的贡献。显然它一定会在一个环上，而且环的形状一定是 Ai --- At - Bs --- Bj ，可以得到 |Ai --- At| + |Bs --- Bj| = K - 2 。

然后枚举 \(i\) ，枚举 \(j\) ，统计所有到 \(i\) 距离为 \(a\) 的点数目为 \(cnt1_a\) ，统计所有到 j 距离为 b 的点数目为 \(cnt2_b\) 。那么 Ai - bj 对答案的贡献为 \(\sum_{a+b = K-2} cnt1_a cnt2_b\) 。

注意到一个环被算两次，除个 2 就好。

900 pts

由于每一列至多只能进行一种操作，所以我们 \(2^m\) 枚举每一列只允许哪一种操作。

假如我们知道了第一行的每个操作，那么我们可以依次推出剩下的每个格子的操作，因为第二行的操作要满足第一行的结果为 B ，所以第一行的操作也确定了，依次递推下去，可以知道后面每行的操作。我们只需要验证最后一行是否仍然满足要求即可。

所以在 \(2^m\) 枚举每一列允许哪种操作后，再枚举第一行每个操作。如果这里再 \(O(2^m)\) 枚举显然会 T 。考虑到这些操作应该是同一种操作，所以进行操作的若干个格子一定是进行同一种操作的若干个格子，我们只需要枚举两个集合的子集就好了。

总时间复杂度为 \(O(nm 3^m)\) 。

nonsense

一进来看到一个 ID 为 just.for.fun 。一看是 NFLS 的，但是不知道是谁。看命名风格有点像 blue.boy ，最后发现果然是 JZP 。亚历山大 >_<

最后 room #2, #1 显然是 just.for.fun 。

Division #33 涨了 rating 。这真是极好的。

GCJ 应该是可以骗到一件衣服的 - -

POJ 的奖品居然没骗到 >__< 做到一半机房断网了于是 #11 真是不能更爽

Google Codejam Round 2

A

一开始看错题了……

显然最后每个人的路线是不相交的，允许包含。于是上车点与下车点构成了括号序列。

然后用栈处理一下就好。

B

假设第一步是二分吧（感觉有不用二分的方法），那么我们的问题就是判定一个人最好/最坏排名是多少。

共有 \(T\) 个人，令 \(f(x, T)\) 表示能力排名为 \(0 \leq x < T\) 的人最差排名是多少。考虑 \(x = 0\) 的情况，易得 \(f(x, T) = T - 1\) 。否则，最差情况下， \(x\) 会被打败，而且下一轮中 \(x\) 的能力值排名是所有可能的值中最大的。 \(x\) 之前有 \(x\) 个人比他强，进入败者组的人至多有 \(\lfloor\frac{x - 1}{2}\rfloor\) 个人，所以有 \(f(x, T) = \frac{T}{2} + f(\lfloor\frac{x - 1}{2}\rfloor, \frac{T}{2})\) 。

最好情况类似，令 \(g(x, T)\) 表示 \(x\) 最好可以打败多少人，可以得到当 \(x = T - 1\) 时有 \(g(x, T) = 0\) ，否则有 \(g(x, T) = \frac{T}{2} + g(\lfloor\frac{x + 1}{2}\rfloor, \frac{T}{2})\) 。

python 真是极好的。

C

根据 LIS 和 LDS 序列可以构出一个拓扑图，一条有向边 \(s \to t\) 表示 \(x_s < x_t\) 。我们要求这个拓扑图的一个拓扑序列，满足 1 出现的位置尽量靠前，在此基础上， 2 出现的位置尽量靠前 etc 。

直接上伪代码吧 = =||

def dfs(x) : # 要使得 x 尽量先出来
    if x 已经在拓扑序中 :
        return
    ys <- 所有要使得 x 出来必须出来但是还未出来的点
    sort ys increasingly
    for y in ys :
        dfs(y)
    Q += [x]

Q = []
for i from 1 to n :
    dfs(i)
# 然后 Q 就是要求的拓扑序

这样做显然是 \(O(n^2)\) 的。

其实有个更好写的 \(O(n \log n)\) 的方法。反向建图，每次选择标号最大的点出来，相当于求出逆拓扑序。

D

计算几何，哈哈哈哈。

POJ Challenge Beta 1

有中文题面，这真是极好的。

A

由 \(a(a + b) = c^2\) 可得 \(a = \frac{\sqrt{b^2 + 4c^2} - b}{2}\) ，可以发现只要 \(\sqrt{b^2 + 4c^2}\) 为整数即可，奇偶性可以保证。

令 \(b^2 + 4c^2 = d^2\) 得 \(b^2 = (d - 2c)(d + 2c)\) 。易知 \(d - 2c \leq 4\) ，所以枚举 \(d - 2c\) ，看看是否存在整数 \(c\) ，如果存在 \(c\) 就可以直接求 \(d\) 然后求 \(a\) 了。

为啥 \(d - 2c \leq 4\) ？当 \(b\) 为奇数时显然 \(d - 2c = 1\) ，当 \(b\) 为偶数时 \(d - 2c = 2, d + 2c = \frac{b^2}{2}\) 和 \(d - 2c = 4, d + 2c = \frac{b^2}{4}\) 中至少有一组可行解。（其实继续分析下去可以直接找到规律，只不过这样已经很好写了于是就直接写了。）

B

一个 \(O(n^3)\) 的 dp 是显然的， \(f_{i, j}\) 表示区间 \([i, j]\) 的最优解，枚举根进行转移。

然后我就不会了 = =

不过我是怎么在 20min 过的呢……因为我看到有人（wkn ？）在 15min 过了，于是觉得这个题应该是可做的，于是猜了个结论： \(f_{i, j}\) 的根只可能是 \(i\) 或 \(j\) 。随机生成了几组极限数据试试发现是对的……然后就没有然后了……

感觉如果按照 dp 的一般优化思路去想的话应该也是可做的。

C

如果一个数同时出现在两组限制中，那么这两组限制必定是连续的，也就是最后的限制就是若干条链，每条链分别搞搞就好了。

感觉好多细节啊不想写啊。你要牛逼就写 PQ 树去吧哈哈哈哈。

D

std 的想法大概是 dp 吧， \(f_{i, j}\) 表示最后一条线段是 \(i \to j\) ，转移的话利用极角序优化一下就好了。

我写的另外一种方法，但是 WA 了。

考虑枚举最低点。两边点到这个点的斜率递增，求出斜率后直接 LIS 。为啥我会错……难道老了连 LIS 都不会了么 T_T

E

果的数据结构题。

依次 dfs 每个点。对于 \((a, b)\) ，我们要求所有的 \((c, d)\) 数目使得 \((c, d)\) 能够覆盖 \((a, b)\) ，我们在 dfs c 的时候在 d 点放个标记，那么在 dfs a 的时候就相当于查询 b 到根的路径上有多少个标记。显然 dfs 序 + 树状数组。

F

显然是原题。

半平面交是 \(O(n^2 \log n)\) 的吧。似乎我估错复杂度以为是 \(O(n^3 \log n)\) 的就没写了 →_→

模拟退火 balabala 不知道怎么样。你要牛逼就写 Voronoi 图去吧哈哈哈哈。

似乎这几天刷水刷的比较多 >_<

似乎最近卖萌比较多 >__<

Problem

在一个单位圆上随机取点，期望要取几个点，才能使这若干个点的凸包包含圆心？

一来就发现 roosaphu #1 。

然后 cp12321 #2 。

然后 kAc #5 。

其中必有引擎。我就呵呵不说话。

（这场 CF 真心是给国人做的）

（我不知道我对 unrated 是该高兴还是该悲伤）

Solution

B

原题可以抽象出这么个模型：给定 \(m\) 个数，要求分成 \(p\) 组，最后每个元素对答案的贡献为它所在组的最大值，求答案的最小值。

排序是显然的。然后序列上 dp ： \(f_{i, j}\) 表示前 \(i\) 个数分成 \(j\) 组，最小的总贡献是多少。转移考虑转入，枚举第 \(j\) 组的元素个数。

\[f_{i, j} = \min_{k < i} (f_{k, j - 1} + (i - k) x_i) = i x_i + \min_{k < i} (f_{k, j - 1} - k x_i)\]

然后就可以斜率优化了。考虑两个决策 \(p < q < i\) ， \(q\) 比 \(p\) 优的充要条件是 \(f_{p, j - 1} - p x_i > f_{q, j - 1} - q x_i\) 也就是 \[x_i > \frac{f_{q, j - 1} - f_{p, j - 1}}{q - p}\] 。

我相信只要你看了 杨哲 《凸完全单调性的一个加强与应用》，你就一定会做这个题。

C

我相信只要你看了 周奕超 《墨墨的等式》 出题报告，你就一定会做这个题。

一眼题不多说。

D

问题主要就出在那个啥三次方上吧。

你有没有感到很奇怪，为啥会给一个奇怪的数 95542721，还特意说明这是个素数？

其中必有隐情。

疑心重重， \(\phi(95542721) = 95542720\) ，这个数与 3 是互质的。

于是我们试着在 \(\mod{95542720}\) 的意义下求 3 的幂。

于是乎，你会发现 \(3^{48} \equiv 1 \mod{95542720}\) 。

剩下的就不用我多说了。用线段树维护 0 到 47 次立方后的结果。

E

我相信只要你做了 Topcoder SRM 558 Div1 1000pts SurroudingBoard ，或者听懂了 曹钦翔 《线性规划与网络流》 ，你就一定会做这个题。

首先那个啥 friend 是用来搞笑的。

每个变量可以取 0 或 1 ，有些取 0 需要代价，有些取 1 需要代价。有种网络流的既视感……

剩下的就是那个特殊的获利的方法：当若干个变量全 0 或全 1 的时候，可以获得一定利润。

如果你突然有了 IDEA ，可以直接构出图：先把利润全部加入答案，然后对于每种获利方式建立一个节点。考虑啥时候需要这利润从答案里扣除。不妨设此时的限制为某些变量全 1 就得到利润吧，那么必定是这些变量中的一些为 0 那么就得扣除利润。某些变量为 0 的话，网络流中的表示为与 T 连通，我们直接把 S 连向利润这个点，容量为利润，再把利润这个点连向与其相关的那些变量，容量无穷大。这样的话一旦有个变量为 0 （图上对应的就是与 T 连通），那么利润这个点必定与 T 连通（无穷大的边你割不去），所以必定要割掉 S 与利润这个点的连边，相当于减去了利润。这就是个最小割模型。

当然你要是牛逼，直接上 cqx 的线性规划也是可以的。我试了一下，发现 SurroudingGame 和这个题都可以用线性规划建模的方法通杀，无比炫酷。

nonsense

节操掉尽，请勿再念。

@xiaodao 关于 #183 D 的 solution …… 我只能说 what the heck 当初觉得很明显的一步我居然不会证 →_→ 于是剩下的就坑了。

首先要证明数的大小一定是 \(\frac{1}{n+1}\) ，然后就好证明了。（这一步怎么证明……我只能说 wiki 上有一句原话）

对于 \(kx = \frac{k}{n+1} = b^p x - q\) ，我们有 \(k = b^p - q(n+1)\) ，在 \(\mod{n+1}\) 意义下有 \(k=b^p \mod{n+1}\) 。由于对于每个 \(k\) 都存在这么一个 \(p\) ，所以容易知道 \(n+1\) 一定为质数，且 \(b\) 是 \(n+1\) 的一个原根。

这次 CF 被拉过去当 Tester ，就写了 BCDE 的没写 A ，结果 A 的 checker 就挂了，真是不能更逗。不得不说他们几个（@lyd, @wqs, @zgx）还是很认真的

近期做的两道题。

Problem

ProjetEuler-429

定义 \(d\) 是 \(n\) 的单位因子，当且仅当 \(gcd(d, \frac{n}{d}) = 1\) 。

令 \(f(n)\) 表示 \(n\) 的所有单位因子的平方和。例如 \(f(24) = 1^2 + 3^2 + 8^2 + 24^2 = 650\)

求 \(f(10^8 !)\)

湖大 ACM 区域赛 A

求 \(\lceil (a + \sqrt{b})^n \rceil \mod{m}\) 。

\(b, n \leq 2^{30}, a, m \leq 2^{15}\)

保证 \((a - 1)^2 < b < a^2\) 。