Почему функция Шпрага-Гранди для суммы игр — ксор функций этих игр? Тут мне не понятен один момент — если первый игрок походил в первой игре, не факт, что и второй походит в первой, т.е. не всегда поочередность ходов в каждой отдельной игре сохраняется.
Заранее спасибо. P.S также не совсем понятно, как реализовывать — буду очень благодарен, если предоставите код или приведете пример реализации.
Автокомментарий: текст был обновлен пользователем Lokeo (предыдущая версия, новая версия, сравнить).
Игры, рассматривавшиеся шпрагом и гранди, — равноправны
Спасибо!
1.) Если игра S у нас может быть представлена как ациклический граф состояний, при этом терминальные состояния (те, из которых мы не можем сделать ход) являются проигрышными, то каждой такой игре мы можем сопоставить по Шпага-Гранди число g(S), которое эквивалентно игре ним с кучкой размера g(S).
2.) Можно доказать, что игра ним с кучками $$$a_1, a_2, ..., a_n$$$ выигрышная тогда и только тогда, когда $$$a_1 \oplus a_2 \oplus ... \oplus a_n$$$ не равно 0, и проигрышная иначе.
Поэтому если есть несколько игр, то функция Шпрага-Гранди для суммы этих игр — xor их функций Шпрага-Гранди.
И то, что вы говорите "поочередность ходов в каждой отдельной игре не всегда сохраняется", т.е. что мы можем выбирать рандомную игру, где будем ходить как раз таки эквивалентно тому, что мы можем брать камни из рандомных кучек в ниме.
Спасибо!
Поочередность ходов действительно не всегда сохраняется. Поэтому эта теория хорошо и просто применИма только к беспристрастным играм, т.е. тем, где набор ходов из позиции не_зависит от того, чей сейчас ход (нету ни ситуаций в стиле "белые двигают только фигуры белых, черные только фигуры черных", ни ситуаций в стиле "белый игрок может забирать 1 или 3 или 5 палочек, а черный или 2 или 4 или 8 или 16").
Как реализовывать -- ну, какие-то переходы от позиции к позиции, напоминающие ДП (динамическое программирование), и тоже в принципе могут реализовываться итеративно от меньших к бОльшим, а могут рекурсивно с запоминанями, чтоб решение для бОльшей подзадачи вызывало решения для меньших подзадач.
Спасибо!
Моя реализация: https://pastebin.com/5DPdv0Fq Задача: https://mirror.codeforces.com/gym/102059/problem/I
Спасибо! Крутая задача и код)
Кстати, mex можно не вычислять честно, достаточно проверить, что среди возможных переходов есть 0. Если есть 0, то текущее значение Гранди устанавливаем 1, иначе 0. upd. Нельзя
В этой задаче — да, но, как я понял, это не всегда правильно. Поправьте, если я неправ :)