为啥高中同学个个都会多项式？恶补多项式……
多项式单点求值
对于 $f(x)=\sum\limits_{i=0}^na_ix^i$，求 $f(k)$。
朴素算法
正常计算是 $\Theta(n^2)$ 的，非常慢。
简单优化
我们发现主要是 $x^i$ 部分被重复求值了，可以事先 $\Theta(n)$ 递推求完所有的 $x^i$，再计算，时间复杂度 $\Theta(n)$，额外空间复杂度 $\Theta(n)$。
秦九韶算法
注意到 $ax^2+bx+c=(ax+b)x+c$，容易推广，于是有递推式：
$F0=a_nx,F_i=F{i-1}x+a_{n-i}$，而 $F_n$ 即为所求。时间复杂度 $\Theta(n)$，额外空间复杂度 $O(1)$。