玄学算法/精彩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}$ 时能在一秒内筛完。

$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

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$

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;
        }
}