Игры (28 мая 2021)

1. Дерево Фенвика (из забытого старого)
   
2. Игры на графах
   1. Определение игры. Выигрышная, проигрышная позиция.
   2. Ацикличный граф. Динамика. Симметричная игра: не храним, кто ходит. Несимметричная - храним.
   3. Графы с циклами, ничейная позиция, примеры.
   4. Ретроанализ
      1. Наивный алгоритм (начальное состояние: какие-то вершины проигрышные, какие-то выигрышные)
      2. Реализация за O(E)
      3. Длина игры
   
   
3. Функция Гранди
   1. Определение. Подсчёт динамикой.
   2. mex за O(deg), функция Гранди за O(E)
   3. G[v] == 0 ⇔ LOSE[v]
   4. Определение: прямая сумма игр
   5. Теорема Гранди: G[v,u] = G₁[v] xor G₂[u]
   6. Игра Ним. Функция Гранди для Нима.

1. Доказательство теоремы
   1. Пример для Нима с табличкой
   2. Доказательство по индукции