Фурье (4 апреля 2014)

1. Ускоряем Фурье
1. a * b * c : 3 Фурье + O(n) + 1 обратное Фурье
2. Два вещественных в одном: z_i = x_i + iy_i, fx_i = (fz_i + fz_n-i)/2
3. Для длинных чисел выбираем систему счисления
1. base * len² < 10¹⁸, len = 2²⁰ > 10⁶ ⇒ base < 10⁶ &rArr base = 10⁴ или 10⁵
2. Поскольку все равно длина округляется до степени двойки, то base = 10⁴ и 2²⁰ ⇒ 2¹⁸
4. Итого: для подсчета a * b * c чисел длины до 2²⁰/3 в десятичной системе счисления
1. Раньше нужно было 2 * 3 Фурье над числами длины 2²⁰ (т.к. длина произведения двух длины 2²⁰/3, округленная вверх до степени двойки = 2²⁰)
2. Теперь нужно 2 + 1 Фурье над многочленом длины 2¹⁸ (в 2 раза меньше преобразований над числами длины в 4 раза меньше)
3. Т.е. быстрее стало в 2 * 4 = 8 раз. При этом код собственно преобразования Фурье мы не трогали.
2. Длинная арифметика
1. Если есть умножение, и деление и извлечение корня проще всего написать через бинпоиск.
2. Веществвенное число = челое + храним сдвиг (сколько знаков после запятой).
3. Деление многочленов за O(nlog²n) через разделяй и властвуй
4. Деление длинных чисел за O(nlogn) с помощью метода Ньютона
5. Извлечение корня из длинного числа за O(nlogn) с помощью метода Ньютона
3. Задачи на Фурье
1. Посчитать скалярный сдвиг, минимизирующий скалярное произведение
2. Поиск циклического сдвига, максимизирующего количество совпавших символов (алфавит = ACGT)
3. Поиск подстроки в строке, если в обоих есть "?" -- символ, равный любому
4. Поиск подматрицы в матрице, минимизируюем среднеквадратичное отклонение
5. Динамика
1. В дереве найти количество поддеревьев размера s
2. В дереве найти количество независимых множеств размера s