Pregunta de bola de nieve FFT

Question

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

Estoy confundido en cuanto a la solución a la pregunta de la bola de nieve.Para empezar, tengo dos preguntas específicas:

(1) Cada par $a_i,b_j$ representará un término (y ¿por qué UN término)?¿Qué se entiende aquí por término?¿El coeficiente $c_k$ del polinomio C?¿O tal vez el valor de $x$ en el punto $kth$?

(2) ¿Por qué $c_k$ es el número de esos pares?

Answer 1

Aquí está la idea de la prueba. Deje que $ a_i, b_i $ sea la distancia arrojada por $ i $ th hombre/mujer. Usando FFT, calculamos $$ Left ( sum_i x^{a_i} right) izquierda ( sum_j x^{b_j} right) = sum_ {i, j} x^{a_i+b_j}. $$ cada par $ i, j $ satisfacer $ a_i + b_j = k $ contribuye un término $ x^k $ al polinomio a la derecha. Por lo tanto, el coeficiente de $ x^k $ es el número de pares $ i, j $ tal que $ a_i + b_j = k $.

Si las cosas aún no están claras, le sugiero que pruebe algunos ejemplos.