Day 168-Q1 — 2026-10-03 | Turning Corners（コイン反転ゲームの Grundy 数は nim 積。単独コイン (x,y) の値は (x−1)⊗(y−1)）

📋 コピーimport sys


def build_table():
    # 8 ビット同士の nim 積の表。1 ビット（0/1 の通常の積）から倍々に作る
    def mul(a, b, h):
        if a < 2 or b < 2:
            return a * b
        m = h >> 1
        mask = (1 << m) - 1
        a1, a0, b1, b0 = a >> m, a & mask, b >> m, b & mask
        c = mul(a1, b1, m)
        d = mul(a0, b0, m)
        e = mul(a1 ^ a0, b1 ^ b0, m)
        return ((e ^ d) << m) ^ d ^ mul(c, 1 << (m - 1), m)
    return [[mul(a, b, 8) for b in range(256)] for a in range(256)]


T = build_table()


def nim_mul(a, b, h=32):
    # a, b < 2^h の nim 積。h = 8 で表引き
    if h == 8:
        return T[a][b]
    m = h >> 1
    mask = (1 << m) - 1
    a1, a0, b1, b0 = a >> m, a & mask, b >> m, b & mask
    c = nim_mul(a1, b1, m)
    d = nim_mul(a0, b0, m)
    e = nim_mul(a1 ^ a0, b1 ^ b0, m)
    return ((e ^ d) << m) ^ d ^ nim_mul(c, 1 << (m - 1), m)


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    x = 0
    for i in range(n):
        a = int(data[1 + 2 * i]) - 1
        b = int(data[2 + 2 * i]) - 1
        x ^= nim_mul(a, b)
    print("First" if x else "Second")


main()