Длинка. Идея 4 русских (16 декабря 2024)

  1. Быстрая длинная арифметика: деление
    1. Деление чисел за O((n/k)2)
    2. Деление за O(nlog2n) через FFT
    3. Выбор системы счисления 232. Перевод между системами счисления за O(nlog2n).

  2. Умножение матриц
    1. Умножение матриц быстрее n3
    2. а) min sum для ZxZ за n3/logn
    3. б) F2xF2 за n3/w, F2xR за n3/logn, F2xF2 за n3/(w*logn)

  3. Приеняем идею
    1. НОП за n2/log2n
    2. Левенштейн за n2/log2n

  4. Оптимизация задач
    1. Дана таблица значений булевой функции, построить схему размера 2n/n (2nn → 2n → 2n/n), которая задаёт эту функцию.
    2. Максимальная клика. Оптимизация перебора 4-мя русскими.
    3. Воспоминания из прошлого: Фарах-Колтон-Бендер для RMQ±1