莫队算法 (咕咕咕)

普通莫队

对于一个离线问题,假如当前已知 `f(x,y)`

并且能 `\mathcal{O}(1)` 的求出 `f(x+1,y),f(x-1,y),f(x,y+1),f(x,y-1)`

就可以考虑使用莫队


拉格朗日插值法

给定`n`个点`(x_i,y_i)`来确定一个多项式并将`k`代入求值

对于这个问题我们可以用高斯消元法以`\mathcal{O}(n^3)`的时间复杂度进行求解

但是有一种`\mathcal{O}(n^2)`的方法,名为拉格朗日插值法

$$ f(x)=\sum_{i=1}^{n}y_i\prod_{i \ne j}{\frac{x-x_j}{x_i-x_j}} $$

这东西就跟FFT一样烦,DP转移式推着推着发现需要用到拉格朗日插值法


Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×