给jcvb、ydc、Picks跪烂了……

我来讲点低端的。

首先还是选个素数在模意义下 $O(n)$ 求解。不过好像有点卡常数？

没关系！我们可以选一个好取模的素数比如$2^{31} - 1 = 2147483647$。

由于 $a \cdot 2^{31} + b \equiv a + b \pmod{2^{31} - 1}$，所以 x 与 (x & 0x7fffffff) + (x >> 31) 是同余的！

于是：

register unsigned long long y = 0;
for (int i = n; i >= 0; i--)
{
    y = y * x + a[i];
    y = (y & 0x7fffffff) + (y >> 31);
}
y %= 0x7fffffff;

当当当当！这样就跑得快了三倍了！（从$1.2\texttt{s}$变成了$0.4\texttt{s}$）

在此基础上再多加几个奇怪的素数模一模判一判就好了。只要不是零多项式那么至多只有$n$个根，所以后面不加什么常数优化也没关系。