Cпасибо за конструктивную критику! Да, на e-maxx довольно доступное объяснение, но примеров там тоже нет.
Я не стал рассматривать в приведенных примерах функции mex и xor, потому что большую часть ним-подобных игр можно решить и без них.
Но можно рассмотреть и для mex с xor:
Пусть у нас есть 3 кучки из произвольного числа камней. Ход состоит в разбиении произвольной кучки на две в любом соотношении. Проигрывает тот, кто не может сделать ход, т.е. остались только кучки по 1 камню. Попробуем определить возможность выигрышной стратегии для игрока, делающего ход вторым.
Для трех кучек G(a, b, c) = G(a) xor G(b) xor G(с).
Если это выражение равно нулю, то второй игрок выигрывает, а иначе — проигрывает.
G(n) можно вычислить так:
G(1) = 0,
G(n) = mex { G(1)^G(n-1), G(2)^G(n-2), ..., G(n-1)^G(1) }
Таким образом, в зависимости от количества камней в кучках, находим «сумму игры», воспользовавшись mex и xor.
Я не стал рассматривать в приведенных примерах функции mex и xor, потому что большую часть ним-подобных игр можно решить и без них.
Но можно рассмотреть и для mex с xor:
Пусть у нас есть 3 кучки из произвольного числа камней. Ход состоит в разбиении произвольной кучки на две в любом соотношении. Проигрывает тот, кто не может сделать ход, т.е. остались только кучки по 1 камню. Попробуем определить возможность выигрышной стратегии для игрока, делающего ход вторым.
Для трех кучек G(a, b, c) = G(a) xor G(b) xor G(с).
Если это выражение равно нулю, то второй игрок выигрывает, а иначе — проигрывает.
G(n) можно вычислить так:
G(1) = 0,
G(n) = mex { G(1)^G(n-1), G(2)^G(n-2), ..., G(n-1)^G(1) }
Таким образом, в зависимости от количества камней в кучках, находим «сумму игры», воспользовавшись mex и xor.