2020-2021:teams:legal_string:王智彪:缓冲区
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:王智彪:缓冲区 [2021/08/13 18:42] 王智彪 创建 |
2020-2021:teams:legal_string:王智彪:缓冲区 [2021/08/17 11:38] (当前版本) 王智彪 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | 注意到 F(n) 是积性函数，所以可以拆开计算 | + | 给一个凸多边形，和凸多边形外侧若干个点，每个点作为一盏灯，向四面八方发出光线，让用最少的点照亮平面除凸包内部外所有区域，如果不存在方案输出 $-1$ 。 |
| - | 考虑生成函数$G_p(x)=F(p^0)+F(p^1)x+...$ | ||
| - | |||
| - | 那么$G_p(x)=(\phi(p^0)+\phi(p^1)+...)^m=(\frac{1-x}{1-px})^m$ | ||
| - | |||
| - | 最终 $G$ 的生成函数就是 $\prod_iG_{p_i}(x)$ | ||
| - | |||
| - | $G$ 的形式是分式，可以写成线性递推，我们可以在 $O(tm\log t\log N)$ 求出这个线性递推的第 $N$ 项。 | ||
| - | |||
| - | 由于质数个数不多，所以可以通过。 | ||
| + | 我们注意到，一个点能照亮的最大区域是这个点对于这个凸包求左右两条切线，然后点亮所有区域的等价条件是所有边都被一个点的两条切线夹起来过。然后这个问题就转化为环形结构内给若干个线段（可以跨过原点），求最少的线段的数量，覆盖 $1$ 到 $n$ 的所有点。 | ||
2020-2021/teams/legal_string/王智彪/缓冲区.1628851322.txt.gz · 最后更改: 2021/08/13 18:42 由 王智彪
