Day 166-Q3 — 2026-09-30 | 回文への分割の個数（回文木と series link で O(N log N)）

📋 コピーimport sys
MOD = 998244353
def main():
    s = sys.stdin.readline().strip()
    n = len(s)
    # 回文木（eertree）。節点 0 = 長さ -1 の根、節点 1 = 長さ 0 の根
    ln = [-1, 0]; link = [0, 0]; diff = [0, 0]; slink = [0, 0]
    nxt = [dict(), dict()]
    series = [0, 0]
    ans = [0]*(n+1); ans[0] = 1
    last = 1
    for i in range(1, n+1):
        c = s[i-1]
        v = last
        while True:
            l = ln[v]
            if i-2-l >= 0 and s[i-2-l] == c: break
            v = link[v]
        if c in nxt[v]:
            last = nxt[v][c]
        else:
            u = len(ln)
            ln.append(ln[v]+2); nxt.append(dict())
            if ln[u] == 1:
                link.append(1)
            else:
                w = link[v]
                while True:
                    l = ln[w]
                    if i-2-l >= 0 and s[i-2-l] == c: break
                    w = link[w]
                link.append(nxt[w][c])
            nxt[v][c] = u
            diff.append(ln[u]-ln[link[u]])
            slink.append(link[u] if diff[u] != diff[link[u]] else slink[link[u]])
            series.append(0)
            last = u
        v = last
        tot = 0
        while ln[v] > 0:
            # v から slink[v] の手前までの回文接尾辞の列（公差 diff[v]）をまとめて足す
            series[v] = ans[i-ln[slink[v]]-diff[v]]
            if diff[v] == diff[link[v]]:
                series[v] += series[link[v]]
            tot += series[v]
            v = slink[v]
        ans[i] = tot % MOD
    print(ans[n])
main()