本文共 382 字，大约阅读时间需要 1 分钟。

一、题目

二、解法

多项式取模真的很妙啊，通常是找到一个什么东西为 \(0\) 就可以取模了。

考虑现在有的点集是 \(X=\{x_1,x_2...x_n\}\)，那么我们使用分治分成两部分 \(X_0=\{x_1,x_2...x_{n/2}\},X_1=\{x_{n/2}...x_n\}\)

考虑构造一个多项式：

那么 \(\forall x\in X_0:g_0(x)=0\)

所以这时候就可以把 \(f(x)\) 取模 \(g_0(x)\) 得到 \(f_0(x)\)，\(X_1\) 的那部分同理，然后我们递归下去即可。

需要预处理每一层的 \(g_0(x),g_1(x)\)，可以一开始 \(O(n\log^2n)\) 处理出来，那么总时间复杂度 \(O(n\log^2n)\)