Skip to content →

Grundy数

それぞれ \(a, b, c\) 個の石からなる山が三つあります。各操作では、2つの山から同数の好きな個数の石を \(x\) 個取り、もう一つの山に \(x\) 個の石を加えます。操作できなくなった方が負けです。

グランディー数は \(\frac{1}{2}(a+b+c-a \oplus b \oplus c)\) となります。code, 証明

それぞれ \(a_1, a_2, \ldots, a_N\) 個の石からなる山があります。各操作では、1つの山から好きな個数の石を取り除くか、合計で \(1\) 個以上 \(h\) 個未満の石を複数の山から取り除くことができます。操作できなくなった方が負けです。

グランディー数は \(h \left(\frac{a_1}{h} \oplus \frac{a_2}{h} \oplus \dots \frac{a_N}{h} \right) + \left(\left(\sum a_i\right) \mod h\right)\) となります。 code, 証明

未整理
https://hos-lyric.hatenablog.com/entry/2021/01/14/201120

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA