Day 116-Q5 — Nim積（Nimber Multiplication・mexによる再帰定義・複合ゲームのGrundy値合成）

2026-08-08 赤色 Master / Phase 8+ ★★★★★★★★★ 組合せゲーム理論・Nimberの体構造・mexの二重帰納

問題

2つの非負整数$a,b$（$0\le a,b<32$）が与えられる。組合せゲーム理論における「Nim積（nimber multiplication）」$a\otimes b$を求めよ。

Nim積は通常の掛け算とは異なる特殊な演算で、次のように再帰的に定義される（$\mathrm{mex}$は「集合に含まれない最小の非負整数」、$\oplus$はXOR＝Nim和）。

$$a \otimes b = \mathrm{mex}\{\, (a' \otimes b) \oplus (a \otimes b') \oplus (a' \otimes b') \;:\; 0 \le a' < a,\ 0 \le b' < b \,\}$$

ただし$a=0$または$b=0$のとき$a\otimes b=0$とする。

入力形式

a b

制約

$0 \le a, b < 32$

入出力例

入力例1

2 2

出力例1

3

入力例2

3 3

出力例2

2

Nimber $\{0,1,2,3\}$は体$\mathrm{GF}(4)$と同型で、$2\otimes2=3$、$3\otimes3=2$。通常の掛け算の答え（$4$や$9$）にはならない。

概念図: 2⊗2 を求める依存関係

2⊗2 = mex{ (a'⊗2)⊕(2⊗b')⊕(a'⊗b') : a',b' ∈ {0,1} } 2⊗2 0⊗2=0 1⊗2=2 1⊗1=1 2⊗1=2 (0,0)→0, (0,1)→2, (1,0)→2, (1,1)→2⊕2⊕1=1 集合 {0,1,2} の mex = 3 → 2⊗2 = 3

ヒント（段階的開示）

ヒント1: 方向性
XOR（Nim和）は複数ゲームの「直和（disjunctive sum）」に対応する演算だが、通常の整数の掛け算はゲームの合成に対応する演算にはならない。ゲームを組み合わせる別の演算として、独自の掛け算（Nim積）が定義される。
ヒント2: アプローチ
Nim積は「両方の引数について、より小さい値からの帰納法」で定義される二重再帰の関数である。$a\otimes b$を求めるには、$a$未満の全ての$a'$と$b$未満の全ての$b'$の組み合わせについて$(a'\otimes b)\oplus(a\otimes b')\oplus(a'\otimes b')$を計算し、その集合の$\mathrm{mex}$を取る。値が小さいうちはメモ化すれば十分高速に計算できる。
ヒント3: 誘導（コード骨格） 
memo = {}
def nim_mul(x, y):
    if x > y:
        x, y = y, x
    if x == 0:
        return 0
    if (x, y) in memo:
        return memo[(x, y)]
    s = set()
    for x2 in range(x):
        for y2 in range(y):
            s.add(nim_mul(x2, y) ^ nim_mul(x, y2) ^ nim_mul(x2, y2))
    m = 0
    while m in s:
        m += 1
    memo[(x, y)] = m
    return m

模範解答 (Python)

import sys


def solve():
    a, b = map(int, sys.stdin.read().split())
    sys.setrecursionlimit(10000)
    memo = {}

    def nim_mul(x, y):
        if x > y:
            x, y = y, x
        if x == 0:
            return 0
        if (x, y) in memo:
            return memo[(x, y)]
        s = set()
        for x2 in range(x):
            for y2 in range(y):
                s.add(nim_mul(x2, y) ^ nim_mul(x, y2) ^ nim_mul(x2, y2))
        m = 0
        while m in s:
            m += 1
        memo[(x, y)] = m
        return m

    print(nim_mul(a, b))


solve()
計算量: 値の上限を$M$とすると状態数$O(M^2)$、各状態の内側ループが最悪$O(M^2)$で最悪$O(M^4)$。$M<32$程度なら現実的。実運用ではFermatの2べきを利用した$O(\log\log M)$の高速アルゴリズムが知られている。$2\otimes2=3$、$3\otimes3=2$、$2\otimes3=1$を手計算・実行で確認済み（$\mathrm{GF}(4)$の乗算表と一致）。

Step-by-Step 解説

1XOR（Nim和）とNim積の位置づけ
Nim和は「複数の独立したゲームの直和」のGrundy値を求める演算（Sprague-Grundy定理）。Nim積はそれとは別の、ゲームを掛け合わせる操作に対応する演算として定義される。
2mexベース再帰定義の二重帰納法
$a\otimes b$の計算には$a'
3メモ化による重複計算の削減
(x,y)をx<=yに正規化してからメモ化することで、(x,y)と(y,x)を別々に計算する無駄を避ける。
4具体例のトレース（$2\otimes2$）
$a'\in\{0,1\},b'\in\{0,1\}$の4通りを計算すると集合は$\{0,1,2\}$になり、$\mathrm{mex}$は$3$。
5計算量の見積もり
状態数$O(M^2)$、各状態の内側ループが最悪$O(M^2)$なので素朴には$O(M^4)$。$M$が数十程度の学習用途では十分高速。

よくあるミス

ミス原因正しい書き方
Nim積を普通の整数の掛け算だと勘違いしてa*bをそのまま使ってしまうNim和（XOR）との類推でNim積も単純な演算だと誤解するNim積は独自のmexベースの再帰定義であり、通常の乗算とは全く異なる値になる（例: $2\otimes2=3$であって$4$ではない）
再帰の中で$x,y$の大小関係を毎回入れ替えず、メモ化キーが$(x,y)$と$(y,x)$で別々に保存され無駄な再計算が発生する演算の対称性（可換性）を活かせていないif x>y: x,y=y,xで正規化してからメモ化する
内側ループの範囲をrange(x+1)のように1つ多く回してしまう「未満」の定義を範囲指定で間違えるPythonのrange(x)は0から$x-1$までなので、定義通り$a'
再帰の停止条件を「$x,y$両方0」の場合だけにしてしまい、片方だけ0のケースで無限再帰になるmex定義における0を含む場合の扱いを見落とす正規化により小さい方がxになるので、x==0だけで即座に0を返す条件で十分なことを確認する

次のステップ

  • 発展: Fermatの2べき（$2^{2^k}$）を利用した高速アルゴリズム（$O(\log\log(\max(a,b)))$程度）を調べ、今回のmex再帰との対応関係を考える
  • 発展: Nim和・Nim積が体をなすことを利用して、Nim積の逆元（除算）を求める方法を考える

自己評価

自分の回答

気づき・メモ