问题引入
有一个长为 (N) 的数组 (k) 与一个长为 (M) 的数组 (d)，求出 (d) 数组中能被 (le 2) 个 (k) 数组中的数相加表示出来的数有多少个。
本题多组数据。
(1le N,M,k_i,d_ile 2 imes 10^5)。
原题链接：SWERC 2014 C。
Solution
题意即要求出有多少组 (k_i+k_j=d_k)，显然可以考虑 Hash 加暴力枚举，然而毒瘤出题人把 (N) 和 (M) 开到了 (2 imes 10^5)，所以这样没有前途。
考虑优化，端详 (k_i+k_j) 的形式，然而并没有什么卵用。
于是 hht 就教了我一个 trick，异常精妙。
对于 (k_i+k_j)，可改为 (x^{k_i} imes x^{k_j})，那么，我们可以构造一个多项式 (F(x)=1+sum^{N}_{i=1} x^{k_i})。
那么 (F(x)^2) 中的每一项就是可以凑出的所有值，可以直接判断。
由此，我们给出了一个 (O(Nlog N)) 的算法。