算导思考题 \(30-5\)
引理 \(1\)
\[A(x)\bmod{(x-z)}=A(z)
\]
令 \(A(x)=\prod_{i=0}^{n-1}(x-x_i)\)，有
\[(x-x_i)\bmod{(x-z)}=z-x_i
\]
所以
\[\begin{aligned}A(x)\bmod{(x-z)}&=\prod_{i=0}^{n-1}(x-x_i)\bmod{(x-z)}\\
&=\prod_{i=0}^{n-1}(z-x_i)\\
&=A(z)
\end{aligned}\]
引理 \(2\)
\[\Big(A(x)\bmod{B(x)C(x)}\Big)\bmod B(x)=A(x)\bmod B(x)
\]
根据多项式取模的定义写开左右两边，右边是 \(R(x)\) 满足
\[A(x)=D(x)B(x)+R(x),\ \deg(A)=\deg(B)+\deg(D),\deg(R)<\deg(B)
\]
左边是 \(R_2(x)\) 满足
\[A(x)=D_1(x)B(x)C(x)+R_1(x),\ \deg(A)=\deg(B)+\deg(C)+\deg(D_1),\ \deg(R_1)<\deg(B)+\deg(C)
\]
\[R_1(x)=D_2(x)B(x)+R_2(x),\ \deg(R_1)=\deg(D_2)+\deg(B), \deg(R_2)<\deg(B)
\]
即
\[\begin{aligned}
A(x)&=D_1(x)B(x)C(x)+D_2(x)B(x)+R_2(x)\\
&=B(x)\Big(D_1(x)C(x)+D_2(x)\Big)+R_2(x)
\end{aligned}\]
其中 \(\deg(D_1(x)C(x)+D_2(x))=\deg(B)-\deg(A)\)，故满足 \(\deg(A)=\deg(B)+\deg(D_1(x)C(x)+D_2(x))\)，所以实际上 \(D_1(x)C(x)+D_2(x)=D(x)\)，得到 \(R(x)=R_2(x)\)。
\(O(n\log^2n)\) 的多项式多点求值
已知可以 \(O(n\log n)\) 实现多项式取模。
根据引理 \(1\)，如果只有一个点 \(z\) 需要求值，我们可以直接求 \(A(x)\bmod{(x-z)}\)。
对于 \(m\) 个待求值的点 \(z_1,z_2,\cdots,z_m\)，构造多项式 \(\prod_{i=1}^m(x-z_i)\)，