質問

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 $はそのようなペアの数ですか?

役に立ちましたか?

解決

これが証拠のアイデアです。 $ 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 $の数です。

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

ライセンス: CC-BY-SA帰属
所属していません cs.stackexchange
scroll top