О быстром преобразовании Фурье

Revision ru2, by adamant, 2017-11-10 16:48:03

Всем привет!

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

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

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

Tags fft, lecture, tutorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English adamant 2017-11-10 16:51:58 629 Initial revision for English translation
ru2 Russian adamant 2017-11-10 16:48:03 309
ru1 Russian adamant 2017-11-04 04:10:48 1045 Первая редакция (опубликовано)