Всем привет!

На следующей неделе начнётся Moscow International Workshop ACM ICPC. Я буду вести на этих сборах лекцию по быстрому преобразованию Фурье, в связи с чем я подготовил конспект, в котором описал большую часть того, что нужно знать про него для использования в контестах. Даже если вы считаете, что знаете FFT, советую посмотреть, там всё ещё могут быть новые идеи для вас. Ближе к лекции также будет английский вариант :)

P.S. Пользуясь случаем, напоминаю о том, что я сейчас веду паблик вконтакте, в который выкладываю какие-то интересные и новые для меня идеи. Наиболее важные я дублирую в постах здесь, но всякая другая мелочь, не всегда связанная со спортивным программированием, остаётся именно на страницах паблика. В частности, часть конспекта сделана на основе материала, который я раньше выкладывал в него. В планах есть некоторое расширение, как перевод на английский и открытие канала в telegram.

UPD: Добавлена английская версия. Также в русской версии добавлен параграф про вычисление последовательностей методом разделяй и властвуй.