Schneeballfrage FFT

Question

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

Ich bin verwirrt über die Lösung der Schneeballfrage.Zunächst habe ich zwei konkrete Fragen:

(1) Jedes Paar $a_i,b_j$ wird einen Term ausmachen (und warum EINEN Term)?Was ist hier mit Begriff gemeint?Der Koeffizient $c_k$ des Polynoms C?Oder vielleicht der $x$-Wert an der $k-ten$-Stelle?

(2) Warum ist $c_k$ die Anzahl solcher Paare?

Answer 1

Hier ist die Idee des Beweises.Sei $a_i,b_i$ die vom $i$ten Mann/Frau geworfene Distanz.Mit FFT berechnen wir $$ links ( sum_i x^{a_i} rechts) links ( sum_j x^{b_j} rechts) = sum_ {i, j} x^{a_i+b_j}.$$ Jedes Paar $i,j$, das $a_i + b_j = k$ erfüllt, trägt einen Term $x^k$ zum Polynom auf der rechten Seite bei.Daher ist der Koeffizient von $x^k$ die Anzahl der Paare $i,j$, so dass $a_i + b_j = k$.

Wenn die Dinge immer noch nicht klar sind, empfehle ich Ihnen, einige Beispiele auszuprobieren.