的确存在这样的问题。我也不知道为什么，可能跟浮点数的存储方式有关
by totorato @ 2019-03-01 18:52:47
# $M_0$ **不应该**根据 **mod** 来设置，
而是根据系数的最大可能范围和多项式长度来设置的。
本题，系数 `ai <= 1e9`，多项式长度 `1e5`，
那么卷积之后结果（称`result`），
`result[i] <= 1e9*1e9*1e5 = 1e23`，`double`以及`long double`精度存不下，
那么拆系数后
$$A(x)=K_A(x)M_0+R_A(x)$$
$$B(x)=K_B(x)M_0+R_B(x)$$
其中
$$K_A[j]=\lfloor\frac{A[j]}{M}\rfloor$$
$$R_A[j]=A[j] \% M$$
也就是 $A[j]=K_A[j] × M_0+R_A[j]$
$B(x)$同理，那么
$$A(x)B(x) = M_0^2K_A(x)K_B(x)+M_0[(K_A(x)R_B(x) + K_B(x)R_A(x)] + R_A(x)R_B(x)$$
为了不让FFT在计算这4个分解出来的多项式乘积时爆掉，长度没变，所以尽可能降低它们系数范围，
由于 `A[j]、B[j]` 范围是`1e9`，所以 $M_0$取1e4~1e5之间的数比较好（尽量接近 sqrt(1e9) 约为31623）。而 `1<<15 = 32768`符合要求。
by AN94 @ 2019-07-26 21:28:11
读入的时候直接系数对$p$取模。
这样的话你的$M_0$设为$\sqrt p$是最优的，和长度没半毛钱关系。
当然取$2^{15}$加快取模也行。
by EMT__Mashiro @ 2019-12-27 14:25:28