2019-04-12 12:33:57

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

### $2.$ 快速插值

\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$ 预处理出来，于是就做完了。

## $60..vimrc$

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 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()
static char Out[outsize],*nowp=Out;
inline void flush(){fwrite(Out,1,nowp-Out,stdout);nowp=Out;}
template<typename T>
{
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;
}
}
• star
首页