Функция Шпрага-Гранди
Сведение любой игры к ниму :
Пусть есть Ациклический ориентированный граф и игра на нем вида можно перейти по ребру, последний сделавший ход - выиграл, сведем ее к ниму :
Пусть f(u)
- функция, сопоставляющая вершине u ним размера f(u)
Сопоставим листьям ним размера 0, так как и ним размера 0 и листья - проигрышные позиции.
Для каждого не листа рассмотрим список его сыновей, пусть в этом списке есть все числа от 0 до x−1 (возможно не один раз) и что-то еще(числа >x ), но при этом нет x , тогда это значит, что мы стоим в позиции из которой можно перейти в ним размера от 0 до x−1 , а это значит, что мы стоим в ниме размера x . Данная операция(нахождение минимального неотрицательного числа, которого нет в массиве) называется mex(minimal excluding).
И в самом деле такое сведение верное, так как из проигрышной вершины(в которой стоит не 0) нет перехода в проигрышную вершину(иначе mex был бы не 0). Из выигрышной вершины всегда же есть переход в проигрышную(так как в сыновьях есть 0).
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin