Пусть нам дан массив `int a[n]` .↵
И требуется найти все коэффициенты многочлена `(x+a[0])*...*(x+a[n-1])`↵
Если считать в лоб, то будет сложность O(n^2).↵
Есть ли способы считать быстрее? Есть ли смысл здесь применять быстрое преобразование Фурье? И есть ли другие хорошие подходы в этом случае.↵
UPD. Как обычно считаю, что все операции производятся по модулю большого числа, если это здесь вдруг имеет значение.
И требуется найти все коэффициенты многочлена `(x+a[0])*...*(x+a[n-1])`↵
Если считать в лоб, то будет сложность O(n^2).↵
Есть ли способы считать быстрее? Есть ли смысл здесь применять быстрое преобразование Фурье? И есть ли другие хорошие подходы в этом случае.↵
UPD. Как обычно считаю, что все операции производятся по модулю большого числа, если это здесь вдруг имеет значение.
