多项式多点求值
传统做法，原理是：
所以对于要求值的多项式 (F(x)) 和给定的点 (x_1,x_2,dots x_m) ，我们就相当于求 (F(x)mod (x-x_1),dots,F(x)mod (x-x_m)) 。
直接求当然不行，但是如果我们求 (F(x)mod (x-a)) ，我们先将 (F(x)) 模上一个包含 ((x-a)) 因式的多项式 (P(x)) ，则 ((F(x)mod P(x))equiv F(x)pmod {x-a}) 。
这提示我们可以逐步降低 (F) 的次数来优化复杂度。采用分治策略，记 (P_{l,r}(x)=prod_{i=l}^r(x-x_i)) ，且 (M=lfloorfrac{l+r}2 floor) 。如果我们得到了 (F(x)mod P_{l,r}(x)) ，我们可以让余式分别模 (P_{l,M}) 和 (P_{M+1,r}) ，从而可以继续递归。
(P) 需要最初分治求并且存下来。
可以得到时间复杂度为 (O(mlog_2^2m)) ，由于频繁使用多项式取模，该算法拥有较大的常数。
船新做法：[1]
普通的和卷积为 (h_k=sum_{i+j=k}f_ig_j) ，我们用 (H=Fcdot G) 或 (H(x)=F(x)cdot G(x)) 来表示。
现在我们定义差卷积为 (h_k=sum_{i-j=k}f_ig_j) ，我们用 (H=F imes G) 或 (H(x)=F(x) imes G(x)) 来表示[2]。
这个做法的原理是：
自行展开即可得知。
除此之外，差卷积还有重要的性质：
按照定义展开并整理即可得证。
因此，我们就相当于求 ([x^0]F(x) imes frac{1}{1-x_1x},dots,[x^0]F(x) imes frac{1}{1-x_mx}) 。
同样采取分治策略。记 (Q_{l,r}(x)=prod_{i=l}^r(1-x_ix)) ，且 (M=lfloorfrac{l+r}2 floor) 。如果我们得到了 (F(x) imes frac{1}{Q_{l,r}(x)}) ，我们就乘上 (Q_{M+1,r}(x)) 并进入左子区间递归；右子区间类似。
由于我们最终只需要常数项的值，因此我们可以控制多项式长度为区间长度，这样就保证了时间复杂度。
(Q) 同样需要最初分治求并且存下来。递归根部的 (F(x) imes frac{1}{Q_{1,m}(x)}) 需要求逆。
那么时间复杂度为 (O(mlog_2^2m)) ，不过常数会小一些，并且也会好写一些。
多项式快速插值
传统做法，原理是拉格朗日插值：
我们只需要快速展开它即可。
将式子变形：
首先处理 (prod_{j ot=i}(x_i-x_j)) 。设 (g(x)=prod_{i=1}^n(x-x_i)) ，则它相当于 (h_i(x)=frac{g(x)}{x-x_i}) 在 (x_i) 处的值。
可以发现 (h_i(x)) 在 (x_i) 有定义，而 (frac{g(x_i)}{x-x_i}) 却没有定义。这就意味着后者的极限即为所需：
所以我们可以分治求出 (g(x)) 然后多点求值得到 (prod_{j ot=i}(x_i-x_j)) 。
接下来求解 (f(x)) 继续采用分治。设 (f_{l,r}(x)) 为 ([l,r]) 的结果：
设分治的划分点为 (M) ，那么可以得到：
边界为 (f_{i,i}(x)=frac{y_i}{prod_{j ot=i}(x_i-x_j)}) 。
这个做法的复杂度是 (O(nlog_2^2n)) ，常数也就见仁见智吧。
船新做法：还没有出现
常系数齐次线性递推
传统做法：
我们可以很容易地构造出转移矩阵 (T) 。
设初值的向量为 (old{A}) ，我们可以知道有：
根据递推式，当整数 (nge k) 时有：
尝试将 (()_0) 去掉，也就是要说明对于整数 (min[0,k)) 都有：
显然有：
所以可以得到：
考虑 (old A) 不为 0 向量的时候，所以：
这是一个关于 (T) 的等式，也告诉我们 (T^n) 可以被表示为较低次项的多项式。所以我们可以对其最高次项频繁进行展开，直到多项式次数降为 (k-1) ；这个过程相当于是进行多项式取模：
因此，如果我们得到取模的系数，我们就可以将初值带入得到 (a_n) 的值。
所以我们需要对多项式做快速幂，模式就为 (T^k-sum_{i=0}^{k-1}f_{k-i}T^i) 。
时间复杂度是 (O(klog_2nlog_2k)) 。
背后的严格证明就略过吧
船新做法：[3]
常系数齐次线性递推有其一般形式。设 (A(x)) 为数列 ({a_n}) 的生成函数，则：
其中 (Q(x)) 与递推式 ({f_k}) 的生成函数 (F(x)) 相关，即 (Q(x)=1-F(x)) ； (P(x)) 与 (A(x),Q(x)) 均相关。
来源：
将 (a_n) 的递推式改一改得到生成函数形式：
[egin{aligned} a_nx^n&=sum_{i=1}^kf_ix^icdot a_{n-i}x^{n-i}\ Rightarrow A(x)&=F(x)A(x) end{aligned} ]但是这里的结果并不完整，因为当 (nge k) 的时候递推式才是有效的，当 (n<k) 的时候，需要进行一些修补。
怎么修？很好办，减去不对的再加回对的就可以了，所以有：
[P(x)equiv (1-F(x))A(x)pmod{x^{k}} ]
根据这个形式我们可以得到什么？
进行一些充满想象力的变换：
设 (V(x)=Q(x)Q(-x)) 。注意到 (V(x)=V(-x)) ，所以 (V(x)) 没有奇数次项。
这意味着我们进行更深入的变化。设 (U(x^2)=V(x)) ，那么有：
其中 (G_0(x^2)) 为 (P(x)Q(-x)) 的偶数次项对应的多项式， (xG_1(x^2)) 为 (P(x)Q(-x)) 的奇数次项对应的多项式。
由于我们只需要求 ([x^n]A(x)) ，所以我们可以舍弃一半的多项式，也就相当于是多项式长度不变，次数减半。最终我们只需要求某个分式的 ([x^0]) ，就可以直接计算了。
这个算法的复杂度也是 (O(klog_2nlog_2k)) ，但是显然它会好写一些，常数也会小一些。
据测试，除开各种复杂的优化，朴素的该算法的常数也仅有传统做法的 (frac 1 3) 左右。