Day 177-Q5 — 2026-10-13 | runs から平方を数える（出現の総数は run ごとの閉じた式、異なる平方の数は run ごとに p 個以下の候補）

📋 コピーimport sys

# ---- ここに Day175-Q5 の sa_is, class LCE, lyndon_ends をそのまま置く ----


def compute_runs(a):
    # Day175-Q5 と同じ: 2 順序の Lyndon 配列から候補 2N 個、LCE で左右に延ばす
    n = len(a)
    fw = LCE(a)
    bw = LCE(a[::-1])
    runs = set()
    for inv in (False, True):
        end = lyndon_ends(a, fw, inv)
        for i in range(n):
            j = end[i]
            p = j - i
            r = j + (fw.query(i, j) if j < n and a[i] == a[j] else 0)
            if r - i < 2 * p and (i == 0 or a[i - 1] != a[j - 1]):
                continue
            l = i - (bw.query(n - i, n - j) if i > 0 and a[i - 1] == a[j - 1] else 0)
            if r - l >= 2 * p:
                runs.add((l, r, p))
    return runs


def main():
    import random
    s = sys.stdin.readline().strip()
    n = len(s)
    a = [ord(c) - 96 for c in s]
    runs = compute_runs(a)

    # (1) 平方の出現数: 平方 ww の最小周期 p は |w| を割り切り、周期 p の run にちょうど 1 つ含まれる
    occ = 0
    for l, r, p in runs:
        L = r - l
        K = L // (2 * p)                       # |w| = kp（k = 1..K）
        occ += K * (L + 1) - p * K * (K + 1)   # Σ_k (L - 2kp + 1)

    # (2) 異なる平方の数: run の中では開始位置が p ずれると同じ文字列 → 先頭 min(p, 出現数) 個が候補。
    #     run をまたいだ重複はロリングハッシュ（法 2^61-1）で除く
    MOD = (1 << 61) - 1
    B = random.randrange(10 ** 6, MOD - 1)
    H = [0] * (n + 1)
    PW = [1] * (n + 1)
    for i, c in enumerate(a):
        H[i + 1] = (H[i] * B + c) % MOD
        PW[i + 1] = PW[i] * B % MOD
    seen = set()
    for l, r, p in runs:
        L = r - l
        k2p = 2 * p
        while k2p <= L:
            cnt = L - k2p + 1
            for st in range(l, l + (p if p < cnt else cnt)):
                h = (H[st + k2p] - H[st] * PW[k2p]) % MOD
                seen.add((k2p, h))
            k2p += 2 * p
    print(occ)
    print(len(seen))


main()