Day 179-Q2 — 2026-10-15 | オクタルゲームの周期性定理（Guy–Smith の証明書「$n_0\le n<2n_0+p+t$ で一致すれば以後ずっと一致」を使い、Kayles などの Grundy 数列の周期と前周期を確定させて $10^{18}$ 個の山を判定する）

📋 コピーimport sys
from operator import xor


def extend(g, code, B):
    """g[0..B-1] まで伸ばす（オクタルゲーム 0.d1d2...）"""
    t = len(code)
    for n in range(len(g), B):
        s = set()
        for k in range(1, min(t, n) + 1):
            d = code[k - 1]
            m = n - k                              # 取った後に残る石
            if d & 1 and m == 0:
                s.add(0)                           # 山を取り切る
            if d & 2 and m > 0:
                s.add(g[m])                        # 1 山を残す
            if d & 4 and m >= 2:                   # 2 つの空でない山 (i, m-i) に分ける
                h = m // 2
                s.update(map(xor, g[1:h + 1], g[m - 1:m - h - 1:-1]))
        v = 0
        while v in s:
            v += 1
        g.append(v)


def certificate(g, t):
    """周期性定理: g(n+p)=g(n) が n0 <= n < 2*n0+p+t で成り立てば以後ずっと成り立つ"""
    B = len(g)
    for p in range(1, B):
        last = -1
        for n in range(B - p - 1, -1, -1):         # 後ろから最初の食い違い
            if g[n + p] != g[n]:
                last = n
                break
        n0 = last + 1
        if 2 * n0 + p + t + p <= B:                # 確かめるべき範囲を計算済み
            return p, n0
    return None


def main():
    data = sys.stdin.buffer.read().split()
    code = [int(c) for c in data[0].decode().split(".")[1]]
    t = len(code)
    n = int(data[1])
    hs = [int(x) for x in data[2:2 + n]]
    g = [0]
    B = 64
    while True:
        extend(g, code, B)
        cert = certificate(g, t)
        if cert:
            break
        B *= 2                                     # 倍々に伸ばして証明書を探す
    p, n0 = cert
    # 最小周期へ: p の約数 q のうち、n0 からの 1 周期が q で回るもの（n0 以降は p 周期なのでこれで十分）
    for q in range(1, p + 1):
        if p % q == 0 and g[n0 + q:n0 + q + p] == g[n0:n0 + p]:
            p = q
            break
    n0 = 0                                         # その周期での最小の前周期
    for i in range(len(g) - p - 1, -1, -1):
        if g[i + p] != g[i]:
            n0 = i + 1
            break
    G = 0
    for h in hs:
        G ^= g[h] if h < len(g) else g[n0 + (h - n0) % p]
    print(p, n0)
    print("First" if G else "Second")


main()