Contest Info

date: 2017.11.15 13:30-18:30

practice link - 1491

Solutions

A. The Catcher in the Rye

题目大意：给你一个被竖直线分成三部分的矩形，高度给定，每一部分给出宽度和速度。要求你从左下角走到右上角，问最短所需时间。

题解：显然按照光的折射的路径是最快的。所以我们可以二分出射角，判断能否到达矩形的右上角即可。

G. Grasshoppers

题目大意：圆 \(O\) 上有 \(m\) 个均匀分布的点，依次标号为 \(1,\cdots,m\)。 \(n\) 只草蜢分布在这些点上，初始位置为 \(A_{1},\cdots,A_{n}\)，每一秒钟它们会按照如下的规则移动：\(A_{1},\cdots,A_{n-1}\) 分别移动到它们关于直线 \(OA_{2},\cdots,OA_{n}\) 的对称点，\(A_{n}\) 移动到它关于直线 \(OA_{1}\) 的对称点，这些移动是同时发生的。现在问你 \(t\) 秒后这些草蜢的位置。

题解：首先将点和草蜢的编号都减去 \(1\) ，然后分别在模 \(m\) 和 \(n\) 的剩余系下讨论，接下来的讨论省略取模操作。

显然每一秒的位置变换是 \(A_{i}'=2A_{i+1}-A_{i}\)，因此 \(\text{ans}_{i}=\sum_{j=0}^{n-1}c_{j}A_{i+j}\)，其中 \(c_{j}\) 是 \((2x-1)^{t}\) 中所有“次数模 \(n\) 余 \(j\) 的项”的系数之和。这显然是一个循环卷积的形式，我们只要用 FFT 就可以做了，最后倒着输出即可。考虑如何求出多项式 \((2x-1)^t\) 的 \(c_{0},\cdots,c_{n-1}\) 的值。

对于一个固定的 \(n\) ，我们定义一种多项式的关系运算 \(\sim\) ，它等价于两个多项式的 \(c_{0},\cdots,c_{n-1}\) 分别相等。容易证明，\(\sim\) 对多项式加法和乘法均保持性质。所以我们可以用类似快速幂的方法，每次进行多项式乘法后，把次数大于等于 \(n\) 的所有项分别加到它的次数减 \(n\) 的那一项上，显然这样操作的多项式 \(\sim\) 原来的多项式，且保持次数界为 \(n\) 。于是复杂度为 \(\mathcal{O}(n\log n\log t)\) 。

coldwater’ comment

\(c_j\) 的意义可以简单示意一下：

\[\begin{aligned} A_i'&=2A_{i+1}-A_i\\ A_i''&=2A_{i+1}'-A_i'\\ &=2(2A_{i+2}-A_{i+1})-(2A_{i+1}-A_i)\\ &=2(2x^2-x)-(2x-1)\\ &=(2x-1)^2 \end{aligned} \]

I. A Really Odd Sequence

签到题。

Replay and Summary

Summary

物理题给 W 做，并且整理 2015 集训队论文中的物理公式，验证并打印。

不要卡题太久，如果过的人实在很多，换一个人推倒重写。

正确使用 memset。构造题猜结论一定要画图，多画不同的图，题目条件一定要读对。