一、开头

（ WC2019 神犇协会）
undefeatedKO ： NOI2017 的题大家都 AK 了吗？
All ： AK 了！
ION ：我们穿越到 2019 年的 WC 怎么样？
olis ：好啊！听说一个弱鸡 xyz32768 要来 WC ，我们一到就把他 D 一遍，这样他 WC2019 不爆零才怪呢！
（ WC2019 ）
VFN ：我们刚刚 A 掉了分身术这题。考虑到你比较菜，我就不用这道题考你了，我换成 Day1 T3 的泳池，如果你做不出来，你就肯定会在 WC2019 我们精心出的试题面前爆零！
xyz32768 ：什么？？？？？？
NFV ：哈哈，没想到你这么菜呀，那我再降低下要求：我告诉你这道题的算法是：常系数线性递推。
xyz32768 ：什么？矩乘快速幂？？？？？？
phantom ： 你这个弱鸡居然连多项式整除和取模都不会，明天你爆零定了！再见！
xyz32768 ： 算了，爆零就爆零吧，反正我永远都学不会任何多项式算法。
pool ： 没想到 xyz32768 你菜得超出我的眼界了，再见，爆零蒟蒻！

二、前置芝士：多项式求逆

多项式求逆

三、多项式的整除与取模

一个 $n$ 次多项式 $F(x)$ 和 $m$ 次多项式 $G(x)$ ，求多项式 $Q(x)$ 和 $R(x)$ ，满足：
（1） $Q(x)$ 次数为 $n-m$ ， $R(x)$ 次数为 $m-1$ 。
（2） $F(x)=Q(x)G(x)+R(x)$
这就是求 $Q(x)$ 为 $F(x)$ 与 $G(x)$ 整除得到的多项式，且 $R(x)=F(x)mod G(x)$ 。
下面进入推式子环节。
$F(frac 1x)=Q(frac 1x)G(frac 1x)+R(frac 1x)$
两边同乘 $x^n$ ：
$F_R(x)=Q_R(x)G_R(x)+R_R(x)x^{n-m+1}$
其中 $F_R(x)$ 表示 $F(x)$ 的系数翻转，即 $F_R(x)$ 的 $i$ 次项系数为 $F(x)$ 的 $n-i$ 次项系数。
$F_R(x)equiv Q_R(x)G_R(x)(mod x^{n-m+1})$
$Q_R(x)equiv F_R(x) imes G^{-1}_R(x)(mod x^{n-m+1})$
需要求 $G_R(x)$ 模 $n-m+1$ 的逆。
至此，我们得到了整除的结果。
取模则更简单：
$R(x)=F(x)-Q(x)G(x)$
多项式取模的重要应用：如果在一定的条件下 $G(x)$ 为 $0$ ，那么将计算 $F(x)$ 改为计算 $F(x)mod G(x)$ 有时可以有效地降低复杂度。

四、应用：多项式多点求值

给定一个 $n$ 次多项式 $F(x)$ 和 $m$ 个值 $x_1,x_2,dots,x_m$ ，求出 $F(x_1)$ ， $F(x_2)$ ，$dots$ ， $F(x_m)$ 。
采用分治的算法。取 $mid=lfloorfrac m2 floor$ 。
先计算 $G_1(x)=prod_{i=1}^{mid}(x-x_i)$ ， $G_2(x)=prod_{i=mid+1}^m(x-x_i)$ 。
那么：
（1）对于任意的 $1le kle mid$ ：
$G_1(x_k)=(x_k-x_k)prod_{i=1,i e k}^{mid}(x_k-x_i)=0$