玄学算法/精彩DS总结 Ludi

2019-04-12 12:33:57


$58.Polynomial\ Multipoint\ Evaluation\&Faster\ Interpolation$

本来这个内容是应该在总结 $slide$ 里的,但因为太麻烦了所以暂时先放这儿。如果我大学搞 $ACM$ 了就把它放到 $slide$ 里吧。

$1.$ 多点求值

多项式多点求值就是给定你多项式 $F$ 和 $x_1,\cdots,x_n$ ,求出它们的值。这里的算法是 $O(n\log^2n)$ 的。
我们考虑直接计算的时间复杂度显然是 $O(ndeg(F))$ 的,所以无论如何我们计算的时候要减少 $deg$ 。
那么我们进行分治,假设现在的多项式是 $F_0$ ,考虑把点集划分为 $[x_l,x_{mid}],[x_{mid+1},x_r]$ 两个部分,然后我们需要减少多项式的度数,最好能减少到 $\frac{deg(F_0)}2$ 。
我们可以构造 $$P_l=\sum_{i=l}^{mid}(x-x_i),P_r=\sum_{i=mid+1}^r(x-x_i)$$ ,这样我们可以发现,当 $x\in[l,mid]$ 里的 $x$ 时, $P_l=0$ ,右边同理 $P_r=0$ 。
那样也就是说 $$F_l\equiv F_0\pmod{P_l},F_r\equiv F_0\pmod{P_r}$$
于是我们可以直接对 $F_0$ 取模,就得到了两个部分。
然后当 $l=r$ 的时候,多项式就只有常数项了,那就是这个点的值。
显然每次我们会让度数 $\div 2$ ,时间复杂度 $T(n)=2T(\frac n2)+O(n\log n)=O(n\log^2 n)$ (此处我们默认 $n,deg$ 同阶)。

$2.$ 快速插值

其实我一直很想吐槽这个名字,插值就插值你还要加个快速,仿佛就是为了与多点求值对称一样。
我们考虑拉格朗日插值的过程 $$F(x)=\sum_{i=1}^ny_i\frac{\prod_{j\neq i}(x-x_j)}{\prod_{j\neq i}(x_i-x_j)}$$ $$=\sum_{i=1}^n\frac{y_i}{\prod_{j\neq i}(x_i-x_j)}\prod_{j\neq i}(x-x_j)$$ 我们先考虑左边那一块的计算。
由于 $y_i$ 是常数,我们只需要计算分母。我们可以搞一个多项式 $$G(x)=\prod_{j=1}^n(x-x_j)$$ ,然后分母就是 $\frac{G(x_i)}{x-x_i}$ 。
根据洛必达法则,这个东西 $=G'(x_i)$ 。我们对 $G$ 求导后,多点求值即可。
接下来我们考虑我们已经求得了 $[l,mid],[mid+1,r]$ 的多项式 $F_l,F_r$ ,怎么求 $F$ 。
$$\begin{aligned}F(x)&=\sum_{i=1}^n\frac{y_i}{\prod_{j\neq i}(x_i-x_j)}\prod_{j\neq i}(x-x_j)\\&=\sum_{i=l}^{mid}\frac{y_i}{G'(x_i)}\prod_{j\neq i}(x-x_j)+\sum_{i=mid+1}^r\frac{y_i}{G'(x_i)}\prod_{j\neq i}(x-x_j)\\&=\sum_{i=l}^{mid}\frac{y_i}{G'(x_i)}\prod_{j=l,j\neq i}^{mid}(x-x_j)\prod_{j=mid+1}^r(x-x_j)+\sum_{i=mid+1}^r\frac{y_i}{G'(x_i)}\prod_{j=mid+1,j\neq i}^{r}(x-x_j)\prod_{j=l}^{mid}(x-x_j)\\&=F_l\prod_{j=mid+1}^r(x-x_j)+F_r\prod_{j=l}^{mid}(x-x_j)\end{aligned}$$ 连续乘积显然可以分治 $FFT$ 预处理出来,于是就做完了。
时间复杂度是 $O(n\log^2n)$ 的,但我觉得它的常数不比线性递推小 $\cdots\cdots$

$59?.Min\_26\ Sieve$

在讲 $Min\_26$ 筛之前,我们先搞明白 $Min\_25$ 筛的本质是什么。
首先,狭义的 $Min\_25$ 筛指的是在之前已经提到过的过程,而广义的 $Min\_25$ 筛实际上是指的两步过程:第一步先把所有质数部分的贡献算出来,第二步计算对于每一个 $\lfloor\frac ni\rfloor$ 位置的真正前缀和,这一部分需要用到之前的质数贡献,通过枚举当前质因子的次数进行筛除。一般情况下,它的时间复杂度为 $O(\frac{n^\frac34}{\log n}+n^{1-\epsilon})$ ,大约在 $n=10^11$ 时能在一秒内筛完。