Вступление

Недавно мне рассказали про некое «преобразование Монтгомери», которое якобы сводит вычисления по произвольному модулю к вычислениям по модулю 2^k. Звучит интересно: во всяких вычислениях по простому модулю самое долгое место — как раз взятие по модулю после каждой операции. Но как именно преобразование работает, не рассказали. Повезло, что я живу в эпоху интернета и любую интересующую меня тему могу с тем или иным успехом загуглить.

Коварные стрелочки

Типичный посетитель сайта codeforces.com, наверное, знает, как искать минимальное (или даже максимальное) остовное дерево (а то и остовный лес). Умеет писать алгоритм Прима, алгоритм Крускала. Кое-кто может быть даже в курсе, что всё это частные случаи алгоритма Борувки, который в 1926-м году рассказывал, как оптимально электрифицировать Моравию (регион Чехии). Вот только правильно работают эти алгоритмы исключительно для неориентированных графов

Привет

Некоторое время назад я наткнулся на персистентные структуры данных и, в частности, на описание персистентной очереди на вики-конспектах ИТМО. Всё бы хорошо, только как-то сложновато: чтобы реализовать одну маленькую очередь используется пять (в другом варианте — шесть) стеков.

Кратно напомню историю проблемы, уложусь всего в четыре стека и заодно немного расскажу про персистентность вообще