Snowball Domanda FFT

Question

http://courses.csail.mit. edu / 6,046 / spring04 / dispense / Prac-quiz2-sol.pdf

Sono confuso per quanto riguarda la soluzione per la questione palla di neve. Per cominciare, ho due domande specifiche:

(1) Ogni coppia $ A_i, b_j $ rappresenteranno un termine (e perché un termine)? Cosa si intende con termine qui? Il coefficiente, $ C_K $ del polinomio C? O forse il $ x $ valore nel punto $ KTH $?

(2) Perché è $ C_K $ il numero di tali coppie?

Answer 1

Ecco l'idea della dimostrazione. Sia $ A_i, b_i $ sia la distanza lanciata dal $ i $ esimo maschio femmina /. Utilizzando FFT, calcoliamo $$ \ left (\ sum_i x ^ {A_i} \ right) \ left (\ sum_j x ^ {b_j} \ right) = \ sum_ {i, j} x ^ {A_i + b_j}. $$ Ogni coppia $ i, j $ soddisfacendo $ A_i + b_j = k $ contribuisce un termine $ x ^ k $ per il polinomio a destra. Quindi il coefficiente di $ x ^ k $ è il numero di coppie $ i, j $ tale che $ a_i + b_j = k $.

Se le cose non sono ancora chiare, vi consiglio di provare alcuni esempi.