Boule de neige Question FFT

Question

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

Je suis confus quant à la solution à la question de boule de neige. Pour commencer, j'ai deux questions spécifiques:

(1) Chaque paire de $ a_i, b_j $ représentera un terme (et pourquoi un seul terme)? Qu'est-ce que l'on entend par terme ici? Le coefficient, $ C_K $ du polynôme C? Ou peut-être le $ x $ valeur à la ke $ spot $?

(2) Pourquoi est-$ C_K $ le nombre de ces paires?

Answer 1

Voici l'idée de la preuve. Soit $ a_i, b_i $ soit la distance lancée par la $ i $ e mâle / femelle. En utilisant FFT, on calcule $$ \ left (\ x ^ {sum_i a_i} \ right) \ left (\ x ^ {sum_j b_j} \ right) = \ sum_ {i, j} x ^ {a_i + b_j}. $$ Chaque paire i $, j $ $ satisfaction + a_i b_j = k $ cotise un terme $ x ^ k $ au polynôme à droite. D'où le coefficient de $ $ x ^ k est le nombre de paires $ i, j $ tel que $ a_i + b_j = k $.

Si les choses ne sont toujours pas claires, je vous suggère d'essayer quelques exemples.