Вопрос-снежок БПФ

Question

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

Я не понимаю решения вопроса о снежном коме.Для начала у меня два конкретных вопроса:

(1) На каждую пару $a_i,b_j$ будет приходиться один терм (и почему ОДИН терм)?Что здесь подразумевается под термином?Коэффициент $c_k$ многочлена C?Или, может быть, значение $x$ в точке $kth$?

(2) Почему $c_k$ такое количество пар?

Answer 1

Вот идея доказательства.Пусть $a_i,b_i$ — расстояние, пройденное $i$м мужчиной/женщиной.Используя 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 $, вносит один термин $ x^k $ в полиноме справа.Следовательно, коэффициент при $x^k$ — это количество пар $i,j$ таких, что $a_i + b_j = k$.

Если что-то еще не ясно, я предлагаю вам попробовать несколько примеров.