Day 161-Q2 — 2026-09-26 — Kayles の Grundy 数の周期性（$n\ge71$ で周期 12）を使い、長さ $10^{18}$ の列でも勝ち手を数える

📋 コピーimport sys

PRE = 71          # n >= 71 で G(n) = G(n+12)（Guy–Smith 1956。n<=3000 で実測確認）
PER = 12
SMALL = 400       # r < SMALL は表引きで直接数える


def build(limit):
    """G(0..limit) を定義どおり O(limit^2) で計算。"""
    g = [0] * (limit + 1)
    for m in range(1, limit + 1):
        s = set()
        for t in (1, 2):                       # 1 本 / 隣り合う 2 本
            if m >= t:
                r = m - t
                for i in range(r // 2 + 1):    # 左右対称なので半分で足りる
                    s.add(g[i] ^ g[r - i])
        x = 0
        while x in s:
            x += 1
        g[m] = x                               # mex
    return g


g = build(SMALL + PER)
P = [g[PRE + ((c - PRE) % PER)] for c in range(PER)]   # P[c] = G(n)（n>=71, n≡c mod 12）


def G(n):
    return g[n] if n <= SMALL else P[n % PER]


# small[r][v] = #{i in [0,r] : G(i)^G(r-i) == v}（r < SMALL）
small = [[0] * 16 for _ in range(SMALL)]
for r in range(SMALL):
    for i in range(r + 1):
        small[r][g[i] ^ g[r - i]] += 1

# edge[c][v] = #{i in [0,70] : G(i)^P[(r-i)%12] == v}（r ≡ c mod 12 かつ r-i >= 71）
edge = [[0] * 16 for _ in range(PER)]
for c in range(PER):
    for i in range(PRE):
        edge[c][g[i] ^ P[(c - i) % PER]] += 1


def count_split(r, v):
    """長さ r の残りを (i, r-i) に分ける i∈[0,r] のうち G(i)^G(r-i)==v の個数。"""
    if v > 15:
        return 0
    if r < SMALL:
        return small[r][v]
    c = r % PER
    res = 2 * edge[c][v]                 # i<71 と、左右対称な r-i<71
    lo, hi = PRE, r - PRE                # 両側とも周期部分
    for d in range(PER):
        if P[d] ^ P[(c - d) % PER] == v:
            first = lo + ((d - lo) % PER)          # [lo,hi] で i≡d となる最小の i
            if first <= hi:
                res += (hi - first) // PER + 1
    return res


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    L = list(map(int, data[1:1 + n]))
    x = 0
    for l in L:
        x ^= G(l)
    if x == 0:
        print(0)
        return
    total = 0
    for l in L:
        want = x ^ G(l)          # この列を Grundy 数 want の状態にすれば全体の XOR が 0
        total += count_split(l - 1, want)         # 1 本倒す
        if l >= 2:
            total += count_split(l - 2, want)     # 隣り合う 2 本を倒す
    print(total)


main()