Олимпиадная математика для информатиков

Программа курса

1. 1 Теория чисел: делимость и разложение

   1. Делимость, простые числа и основная теорема арифметики

      Делимость и её свойства, деление с остатком в Python, проверка простоты за O(√n), основная теорема арифметики и факторизация за O(√n).

   2. Решето Эратосфена и линейное решето

      Решето Эратосфена за O(n log log n), оптимизации, массив наименьших простых делителей для факторизации за O(log n) и линейное решето за O(n).

   3. Делители, НОД, НОК и алгоритм Евклида

      Число и сумма делителей через разложение, алгоритм Евклида за O(log n), НОК через НОД, расширенный Евклид и коэффициенты Безу.

2. 2 Модулярная арифметика

   1. Арифметика по модулю: сложение, вычитание, умножение

      Сравнения по модулю, совместимость операций с остатком, безопасное вычитание, накопление произведения по модулю и почему деление требует обратного элемента.

   2. Быстрое возведение в степень по модулю

      Бинарное возведение в степень за O(log b), модульная версия, встроенная pow(a,b,m), связь с обратным элементом по малой теореме Ферма.

   3. Обратный элемент, деление по модулю и КТО

      Обратный элемент по модулю двумя способами (Ферма и расширенный Евклид), деление по модулю и дроби, китайская теорема об остатках с конструкцией.

3. 3 Комбинаторика

   1. Правила счёта, перестановки, размещения, сочетания

      Правила суммы и произведения, перестановки n!, размещения A(n,k), сочетания C(n,k), связь и симметрия, разбор задачи о маршрутах в сетке.

   2. Биномиальные коэффициенты и C(n, k) по модулю

      Треугольник Паскаля и тождество, сочетания по простому модулю через факториалы и обратные факториалы за O(1), сочетания с повторениями методом звёзд и перегородок.

   3. Включения-исключения и принцип Дирихле

      Принцип включения-исключения с примерами, формула беспорядков и её связь с 1/e, принцип Дирихле для доказательства существования совпадений.

4. 4 Вероятность и математическое ожидание

   1. Вероятность, независимость, условная вероятность

      Классическая вероятность, аксиомы и включение-исключение, независимость и условная вероятность, точные дроби через Fraction и проверка гипотез методом Монте-Карло.

   2. Математическое ожидание и линейность ожидания

      Математическое ожидание дискретной величины, линейность ожидания и индикаторы, ожидаемое число шагов до успеха, задача о собирателе купонов с проверкой Монте-Карло.

   3. Случайные блуждания и ожидаемое время

      Случайные блуждания и марковские цепи, система уравнений на ожидаемое время до поглощения, формула i·(N−i) для отрезка, общий граф состояний и проверка симуляцией.

5. 5 Теория игр

   1. Выигрышные и проигрышные позиции

      Беспристрастные игры с полной информацией, разметка позиций на выигрышные и проигрышные по индукции, доказательство корректности и поиск периода проигрышных позиций.

   2. Ним и ним-сумма

      Игра ним, теорема Бутона: проигрыш тогда и только тогда, когда XOR куч равен нулю, доказательство через старший бит и поиск выигрышного хода.

   3. Функция Шпрага–Гранди

      Функция mex и значения Гранди позиции, почему Гранди кучи нима равен её размеру, теорема Шпрага–Гранди и XOR значений Гранди для суммы независимых игр.

6. 6 Битовые приёмы и двоичная математика

   1. Двоичное представление и побитовые операции

      Двоичная запись чисел, операции AND, OR, XOR, NOT и сдвиги, особые свойства XOR (a^a=0) и поиск непарного элемента за O(n) и O(1) памяти.

   2. Приёмы работы с битами

      Проверка, установка, снятие и переключение бита через маску 1<<i, выделение младшего бита x&(-x), снятие x&(x-1), подсчёт битов и битмаска как набор флагов.

   3. Битовые маски, подмножества и XOR-трюки

      Перебор всех подмножеств масками, перебор подмасок через (sub-1)&mask, XOR-трюк для двух непарных чисел и идея динамики по подмножествам.

7. 7 Алгебра и быстрые приёмы

   1. Матрицы и быстрое возведение в степень

      Умножение матриц, переход линейной рекурренты как умножение на матрицу, числа Фибоначчи за O(log n) и по модулю, обобщение на любую линейную рекурренту.

   2. Прогрессии и суммы

      Арифметическая и геометрическая прогрессии и их суммы, геометрическая сумма по модулю через обратный элемент, формулы сумм квадратов и кубов за O(1).

   3. Многочлены, Горнер и генерирующие функции

      Схема Горнера для вычисления многочлена и полиномиального хеша, генерирующие функции как кодирование последовательностей, произведение рядов как свёртка.

8. 8 Геометрия: основы для олимпиад

   1. Точки, векторы и произведения

      Точки и векторы, квадрат расстояния, скалярное произведение для углов и псевдоскалярное (косое) для площади и ориентации, определение ориентации трёх точек целочисленно.

   2. Площадь треугольника и многоугольника

      Удвоенная площадь треугольника через косое произведение, формула шнурков для простого многоугольника, теорема Пика и связь площади с целыми точками.

   3. Ориентация и пересечение отрезков

      Определение стороны точки относительно прямой, попадание точки на отрезок, устойчивый целочисленный тест пересечения двух отрезков через ориентацию без float.