Длинка. Идея 4 русских (16 декабря 2024)
- Быстрая длинная арифметика: деление
- Деление чисел за O((n/k)2)
- Деление за O(nlog2n) через FFT
- Выбор системы счисления 232. Перевод между системами счисления за O(nlog2n).
- Умножение матриц
- Умножение матриц быстрее n3
- а) min sum для ZxZ за n3/logn
- б) F2xF2 за n3/w, F2xR за n3/logn, F2xF2 за n3/(w*logn)
- Приеняем идею
- НОП за n2/log2n
- Левенштейн за n2/log2n
- Оптимизация задач
- Дана таблица значений булевой функции, построить схему размера 2n/n (2nn → 2n → 2n/n), которая задаёт эту функцию.
- Максимальная клика. Оптимизация перебора 4-мя русскими.
- Воспоминания из прошлого: Фарах-Колтон-Бендер для RMQ±1