スノーボール質問FFT

Question

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

雪だるまの質問に対する解決策について混乱しています。まず、2つの具体的な質問があります。

（1）各ペア$ a_i、b_j $は、1つの用語（およびなぜ1つの用語）を占めますか？ここでの用語とはどういう意味ですか？係数、多項式cの$ c_k $？それとも、$ kth $のスポットでの$ x $ value？

（2）なぜ$ c_k $はそのようなペアの数ですか？

Answer 1

これが証拠のアイデアです。 $ a_i、b_i $を、$ i $ th mal/雌によって投げられる距離とします。 fftを使用して、$$ left（ sum_i x^{a_i} right） left（ sum_j x^{b_j} right）= sum_ {i、j} x^{a_i+b_j}を計算します。 $$各ペア$ i、j $満たす$ a_i + b_j = k $は、右側の多項式に1つの用語$ x^k $を寄付します。したがって、$ x^k $の係数は、$ a_i + b_j = k $のペア$ i、j $の数です。

物事がまだ明確でない場合は、いくつかの例を試すことをお勧めします。