玄学算法/精彩DS总结 Ludi
teafrogsf
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}$时能在一秒内筛完。
## $60..vimrc$
~~的确有两个点。~~
前面部分压行之后应该一共9行。
```
set nocp
set go=
syntax on
set ruler
set guifont=Consolas:h16
set guioptions+=b
set guioptions+=r
color molokai
set nu
set mouse=a
set backspace=eol,indent,start
set tabstop=4
set shiftwidth=4
set softtabstop=4
set cindent
set autoindent
set smartindent
set autoread autowrite autochdir
set cursorline
set cursorcolumn
set clipboard=unnamed
set fileencodings=utf-8,ucs-bom,gb18030,gbk,gb2312,cp936
set termencoding=utf-8
set encoding=utf-8
map<F6> :!python %<CR>
map<F7> :27vsp %<.in<CR>:sp %<.out<CR>
map<F9> :!g++ % -o %< -lm -std=c++11 -Wl,-stack=1000000000 -Wshadow -Wextra -Wall -O2 && %< <CR>
map<F8> :!g++ % -o %< -lm -std=c++11 && %< <CR>
map<F1> :call libcallnr("vimtweak.dll","SetAlpha",180)<CR>
map<F2> :call libcallnr("vimtweak.dll","SetAlpha",0)<CR>
map<F3> :call libcallnr("vimtweak.dll","SetAlpha",88)<CR>
map<F4> :call libcallnr("vimtweak.dll","SetAlpha",255)<CR>
map<F5> :call libcallnr("vimtweak.dll","SetAlpha",1)<CR>
source $VIMRUNTIME/vimrc_example.vim
source $VIMRUNTIME/mswin.vim
behave mswin
set diffexpr=MyDiff()
function MyDiff()
let opt = '-a --binary '
if &diffopt =~ 'icase' | let opt = opt . '-i ' | endif
if &diffopt =~ 'iwhite' | let opt = opt . '-b ' | endif
let arg1 = v:fname_in
if arg1 =~ ' ' | let arg1 = '"' . arg1 . '"' | endif
let arg2 = v:fname_new
if arg2 =~ ' ' | let arg2 = '"' . arg2 . '"' | endif
let arg3 = v:fname_out
if arg3 =~ ' ' | let arg3 = '"' . arg3 . '"' | endif
if $VIMRUNTIME =~ ' '
if &sh =~ '\<cmd'
if empty(&shellxquote)
let l:shxq_sav = ''
set shellxquote&
endif
let cmd = '"' . $VIMRUNTIME . '\diff"'
else
let cmd = substitute($VIMRUNTIME, ' ', '" ', '') . '\diff"'
endif
else
let cmd = $VIMRUNTIME . '\diff'
endif
silent execute '!' . cmd . ' ' . opt . arg1 . ' ' . arg2 . ' > ' . arg3
if exists('l:shxq_sav')
let &shellxquote=l:shxq_sav
endif
endfunction
```
## $61.IO$
```cpp
namespace IO
{
const unsigned int bufsize=1<<16,outsize=1<<24;
static char ch[bufsize],*S=ch,*T=ch;
inline char getc()
{return ((S==T)&&(T=(S=ch)+fread(ch,1,bufsize,stdin),S==T)?0:*S++);}
static char Out[outsize],*nowp=Out;
inline void flush(){fwrite(Out,1,nowp-Out,stdout);nowp=Out;}
template<typename T>
void read(T &x)
{
char c=getc();x=0;
for(;!isdigit(c);c=getc());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^'0'),c=getc());
}
template<typename T>
void write(T x,char c='\n')
{
if(!x)*nowp++='0';
if(x<0)*nowp++='-',x=-x;
static unsigned int stk[50],tp=0;
for(;x;x/=10)stk[++tp]=x%10;
for(;tp;*nowp++=stk[tp--]^'0');*nowp++=c;
}
}
```