План лекций

Вводная задача.

DP на дереве.

Найти число способов выбрать в дереве K вершин так, чтобы никакие две не были смежны.
Решение за O(N³). Сведение произвольного дерева к бинарному.
Решение за O(N²logN) = быстрое перемножение многочленов.

Дискретное Преобразование Фурье (ДПФ, БПФ)

БПФ в комплексных числах

Умножеие = экстерполяция + умножение за O(n) + интерполяция
Длинное целое число можно рассматривать, как многочлен Z[x], x from R,C,Z/pZ
Экстерполяция: посчитать значения многочлена в точках A0,A1,A2,...,A[2^k-1]. Интерполяция: по значениям в точках восстановить многочлен.
Фокус БПФ в том, чтобы экстерполяция и интерполяция работали за ONlogN). Точки должны образовывать циклическую группу по умножению порядка 2^k.
Рекурсивная процедура (псевдокод).

Обратное БПФ в комплексных числах

1 + a + a² + ... + aⁿ = 0
Записываем уравнения, видим значения нового многочлена в точках.

Быстрая реализация БПФ в комплексных числах

Рекурсия - не самый тонкий момент (поэтому нерекурсивную реализацию не трогаем, как не нужную).
Все корни из 1 должны быть предодсчитаны. Их всего N штук, на их вычисление уходит O(N) комплексных умножений или O(N) sin и cos.
Внутренний цикл должен быть длины не N, а N/2
База для N=2 (не 1), при желании можно даже для 4-х.

БПФ для Z/pZ

p = p0*2^k + 1, например 3*2¹⁸ + 1
Ищем образующую группы (после этого можно вбить ее в константы и не считать каждый раз).
N = p - 1, a - образующая, (a²)^N/2 = 1

Not read Задачи на БПФ

Not read Выбрать циклический сдвиг A[] : (A[],B[]) = min (SRM 1000, 2009)
Not read Найти подматрицу в матрице с min квадратичным откланением (Всесиб-2009)
Not read В массиве C[]. Посчитать число троек x,x-a,x+a: С[x] == 1 && C[x-a] == 1 && C[x+a] == 1 (PTZ-Summer-2010)
Not read В матрице NxN найти матожидание периметра треугольника. Решение за O(N³). (PTZ-Summer-2010)

Другие методы умножения чисел

Not read Карацуба

Not read Метод 3 умножения вместо 4-х. Оценка времени N^log_23
Not read Метод 6 умножений вместо 9-и. Получается хуже...
Not read Реализация. N <= 16. Аккуратное выделение памяти. На Си. На Джаве.

Not read Смешной метод с интерполяцией и экстерполяцией за O(N^1+eps)
Not read Метод If-а. Если числа не более 2³⁰? А если 2⁶⁰? А если 2¹⁰⁰?

Not read Пример задачи. В каждой строке файла посчитать сумму чисел. Числа до 10¹⁸.
Not read Пример кода. if ((a0 += b) >= BASE) a0 -= BASE, a1++;

Not read Сравнение длинных чисел.

Not read Пример задачи: найти min число c данным числом делителей.
Not read Логарифмируем.

Деление и извлечение корня

Метод Ньютона

Кастельные. x -= f(x) / f'(x).
Обоснование скорости сходимости loglogEps.

Деление

Почему деление нельзя сделать так же, как умножение (экстерполяция + деление за O(n) + интерполяция)?
Деление бинпоиском за O(N³)
Not read Деление за O(N²log)
Not read Деление за O(N²) : первую цифру можем вычислять за O(1).
Деление за o(N²) : видимо, можно вычислять даже не 1, а 10 цифр :)
Деление за O(NlogN). Применяем метод Ньютона. a=1/x

Not read Корень квадратный обыкновенный.

Not read Корень бинпоиском за O(N³).
Not read O(N²logN) = Вычсиляем очередную цифру бинпоиском за O(NlogN)
Not read Метод за O(Nsqrt(N)) с вычислением сразу многих цифр.
Not read Применяем Ньютона и вновь O(NlogN). a=1/(x²)

Кое-что из теории чисел.

Not read Как найти все простые числа от 1 до 10⁹ за O(N)
Not read Как для всех чисел от 1 до N создать список делителей за O(NlogN).

Решение систем линейных уравнений.

Not read Слуйчай поля. Метод Гаусса.
Not read Система, в которой каждое уравнение дано по своему модулю.

Not read Решение для p^k. Сведедние через LCM.
Not read К.Т.О. поможет.

Not read Система по не простому модулю M.

Not read Подсчет определителя. Приведение матрицы к диагонально-трапецивидному виду.
Not read Сравнения по модулю, получение решения, если нет свободных переменных.
Not read Базис пространства решений. Подъем базиса.
Not read Сведение исходной системы к уравнениям над коеффицентами при свободных переменных.