雪球问题FFT

Question

http://courses.csail.mit.edu/6.046/spring04/handouts/prac-quiz2-sol.pdf

我对雪球问题的解决方案感到困惑。首先，我有两个具体的问题：

（1）每对$ a_i，b_j $将考虑一个学期（以及为什么一个学期）？在这里，这是什么意思？系数，$ c_k $的多项式C？还是$ kth $ spot的$ x $值？

（2）为什么$ c_k $此类对的数量？

Answer 1

这是证明的想法。令$ a_i，b_i $为$ i $ th男女的距离。使用FFT，我们计算$$ left（ sum_i x^{a_i} right） left（ sum_j x^x^{b_j} right）= sum_ {i，j} x^x^{a_i+b_j}。 $$每对$ i，j $满足$ a_i + b_j = k $在右边为多项式贡献了一个项$ x^k $。因此，$ x^k $的系数是对$ i，j $的数量，因此$ a_i + b_j = k $。

如果事情仍然不清楚，我建议您尝试一些例子。