（非讨论区题解）

目前个人想到的是，将题意转化为求 $\prod_{i=1}^n(x^{a_i}+x^{-a_i}) \bmod(x^k-1) \ \ (1)$ 的常数项是否大于零，也即 $\prod_{i=1}^{k-1}(x^i+x^{-i})^{c_i} \bmod (x^k-1) \ \ (2)$ 的常数项是否大于零，其中 $c_i$ 为 $\{ a_n\}$ 中有多少个数和 $i$ 在 $\bmod \ k$ 下同余。

通过处理循环节，可以 $\Theta(k)$ 的时间复杂度处理出 (2) 式乘积中的每一项是否大于零，然后 fft 暴力卷积起来，总时间复杂度就是 $\Theta(k^2\log k)$ 的。

但是这样的结果显然不让人满意，不知道各位有没有高论可以优化一下。