Day 180-Q5 — 2026-10-16 | K 乗（u^K）の出現数と、異なる K 乗の数を runs と接尾辞配列のランクで厳密に（Day177-Q5 のハッシュによる重複除去を、ランクの区間の LCP で置き換える）

📋 コピーimport sys


def sa_is(s, upper):
    # SA-IS（AtCoder Library の Python 移植と同じ手順）。s は 0..upper の整数列
    n = len(s)
    if n == 0:
        return []
    if n == 1:
        return [0]
    if n == 2:
        return [0, 1] if s[0] < s[1] else [1, 0]
    sa = [0] * n
    ls = [False] * n
    for i in range(n - 2, -1, -1):
        ls[i] = ls[i + 1] if s[i] == s[i + 1] else (s[i] < s[i + 1])
    sum_l = [0] * (upper + 1)
    sum_s = [0] * (upper + 1)
    for i in range(n):
        if not ls[i]:
            sum_s[s[i]] += 1
        else:
            sum_l[s[i] + 1] += 1
    for i in range(upper + 1):
        sum_s[i] += sum_l[i]
        if i < upper:
            sum_l[i + 1] += sum_s[i]

    def induce(lms):
        for i in range(n):
            sa[i] = -1
        buf = sum_s[:]
        for d in lms:
            if d == n:
                continue
            sa[buf[s[d]]] = d
            buf[s[d]] += 1
        buf = sum_l[:]
        sa[buf[s[n - 1]]] = n - 1
        buf[s[n - 1]] += 1
        for i in range(n):
            v = sa[i]
            if v >= 1 and not ls[v - 1]:
                sa[buf[s[v - 1]]] = v - 1
                buf[s[v - 1]] += 1
        buf = sum_l[:]
        for i in range(n - 1, -1, -1):
            v = sa[i]
            if v >= 1 and ls[v - 1]:
                buf[s[v - 1] + 1] -= 1
                sa[buf[s[v - 1] + 1]] = v - 1

    lms_map = [-1] * (n + 1)
    m = 0
    for i in range(1, n):
        if not ls[i - 1] and ls[i]:
            lms_map[i] = m
            m += 1
    lms = [i for i in range(1, n) if not ls[i - 1] and ls[i]]
    induce(lms)
    if m:
        sorted_lms = [v for v in sa if lms_map[v] != -1]
        rec_s = [0] * m
        rec_upper = 0
        rec_s[lms_map[sorted_lms[0]]] = 0
        for i in range(1, m):
            l, r = sorted_lms[i - 1], sorted_lms[i]
            end_l = lms[lms_map[l] + 1] if lms_map[l] + 1 < m else n
            end_r = lms[lms_map[r] + 1] if lms_map[r] + 1 < m else n
            same = True
            if end_l - l != end_r - r:
                same = False
            else:
                while l < end_l:
                    if s[l] != s[r]:
                        break
                    l += 1
                    r += 1
                if l == n or s[l] != s[r]:
                    same = False
            if not same:
                rec_upper += 1
            rec_s[lms_map[sorted_lms[i]]] = rec_upper
        rec_sa = sa_is(rec_s, rec_upper)
        for i in range(m):
            sorted_lms[i] = lms[rec_sa[i]]
        induce(sorted_lms)
    return sa


class LCE:
    # 接尾辞配列 + LCP 配列 + Sparse Table で、2 つの接尾辞の最長共通接頭辞を O(1)
    def __init__(self, s):
        n = len(s)
        sa = sa_is(s, max(s) if s else 0)
        rank = [0] * n
        for i, v in enumerate(sa):
            rank[v] = i
        lcp = [0] * max(n - 1, 0)
        h = 0
        for i in range(n):
            if h:
                h -= 1
            if rank[i] == 0:
                continue
            j = sa[rank[i] - 1]
            while i + h < n and j + h < n and s[i + h] == s[j + h]:
                h += 1
            lcp[rank[i] - 1] = h
        table = [lcp]
        k = 1
        while 2 * k <= len(lcp):
            prev = table[-1]
            table.append([a if a < b else b for a, b in zip(prev, prev[k:])])
            k *= 2
        self.n, self.rank, self.table = n, rank, table

    def query(self, i, j):
        # s[i:] と s[j:] の共通接頭辞の長さ（i != j）
        if i >= self.n or j >= self.n:
            return 0
        a, b = self.rank[i], self.rank[j]
        if a > b:
            a, b = b, a
        k = (b - a).bit_length() - 1
        t = self.table[k]
        x, y = t[a], t[b - (1 << k)]
        return x if x < y else y


def lyndon_ends(s, lce, inv):
    # end[i] = s[i:] の最長 Lyndon 接頭辞の終わり。inv=True なら文字の大小を反転した順序で
    n = len(s)
    end = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        j = i + 1
        while j < n:
            if s[i] != s[j]:                        # 1 文字目で決まるときは LCE を引かない
                if (s[i] < s[j]) != inv:
                    j = end[j]
                    continue
                break
            l = lce.query(i, j)
            if j + l == n:
                break                               # s[j:] が s[i:] の接頭辞 → s[i:] の方が大きい
            a, b = s[i + l], s[j + l]
            if (a < b) != inv:
                j = end[j]                          # s[i:] < s[j:]: Lyndon 語を延ばす
            else:
                break
        end[i] = j
    return end


def compute_runs(a, fw, bw):
    n = len(a)
    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():
    data = sys.stdin.read().split()
    s, K = data[0], int(data[1])
    n = len(s)
    a = [ord(c) - 96 for c in s]
    fw = LCE(a)
    bw = LCE(a[::-1])
    runs = compute_runs(a, fw, bw)
    occ = 0
    cand = []                                   # 長さ * (n+1) + 開始位置のランク
    rank = fw.rank
    N1 = n + 1
    for l, r, p in runs:
        L = r - l
        q = K * p                               # 長さ K*j*p の K 乗（j = 1, 2, ...）
        while q <= L:
            c = L - q + 1
            occ += c
            base = q * N1
            for i in range(l, l + (p if p < c else c)):   # 同じ run では先頭 p 個だけが異なる
                cand.append(base + rank[i])
            q += K * p
    cand.sort()
    # 同じ長さで隣り合うランクの 2 つは、その区間の LCP の最小が長さ以上なら同じ文字列
    table = fw.table
    distinct = 0
    prev_len = -1
    prev_rank = -1
    for x in cand:
        ln, rk = divmod(x, N1)
        if ln != prev_len:
            distinct += 1
        else:
            k = (rk - prev_rank).bit_length() - 1
            t = table[k]
            u, v = t[prev_rank], t[rk - (1 << k)]
            if (u if u < v else v) < ln:
                distinct += 1
        prev_len, prev_rank = ln, rk
    print(occ, distinct)


main()