|
Никаких деревьев не нужно рассчитывать.
Все что вам тут нужно знать - гранди-функцию G(n) игры в которой изначально есть только одна единственная кучка из n фишек.
Есть у вас изначально несколько таких кучек, с k, n, m фишками, то у вас получается то, что называется "суммой игр". Гранди функция суммы игр есть xor гранди-функции каждой игры по отдельности (теорема Шпрага-Гранди).
Т.е. G(k,n,m) = G(k) ^ G(n) ^ G(m).
G(n) по ее определению, а также еще раз используя т. Шпрага-Гранди, можно вычислить так:
G(1) = 0,
G(n) = mex { G(1)^G(n-1), G(2)^G(n-2), ..., G(n-1)^G(1) }.
где mex S = наименьшее неотрицательное целое, не входящее в множество S, а ^ -- операция xor.
|
. реализация у меня будет на С.
Линейный вид
