Day 027-Q3 — 多項式指数・対数（FPS exp/log over NTT）

2026-05-10 赤色 Master / Phase 8+ ★★★★★★★★★ 形式的冪級数 exp/log

問題

形式的冪級数 $F(x) = \sum_{i=0}^{N-1} a_i x^i$（$a_0 = 0$、各 $a_i$ は 998244353 での値）が与えられる。$\exp(F(x)) \pmod{x^N}$ を $\bmod 998244353$ で求めよ。

入力形式

N
a_0 a_1 ... a_{N-1}

制約

$2 \leq N \leq 2^{20}$（$N$ は 2 のべき乗）
$0 \leq a_i < 998244353$
$a_0 = 0$（exp の定義域条件）

入出力例

入力例 1

4
0 1 0 0

出力例 1

1 1 499122177 166374059

入力例 2

8
0 1 2 3 4 5 6 7

出力例 2

1 1 499122178 500540699 754522046 739786015 547396755 626611024

ヒント (段階的開示)

ヒント1: 方向性
$G = \exp(F)$ を Newton 法（Hensel's Lemma）で求める。精度を倍々に増やしながら収束させる。
ヒント2: アプローチ
Newton 法の反復: $G_{2n} \leftarrow G_n (1 - \log G_n + F) \pmod{x^{2n}}$。log の計算: $\log G = \int G^{-1} G' \, dx$（微分・積分・逆元 all $O(n \log n)$ NTT）。全体 $O(N \log N)$。
ヒント3: 誘導 
def poly_exp(F, n, MOD):
    # F[0] == 0 が前提
    G = [1]  # G_1 = 1 = exp(0)
    m = 1
    while m < n:
        m2 = min(m * 2, n)
        lnG = poly_log(G, m2, MOD)
        correction = poly_sub(poly_add([1], poly_sub(F[:m2], lnG, MOD), MOD), [1], MOD)
        G = poly_mul(G, poly_add([1], correction, MOD), MOD)[:m2]
        m = m2
    return G[:n]

模範解答 (Python)

import sys
from typing import List
input = sys.stdin.readline

MOD = 998244353
g_root = 3  # 原始根

def ntt(a: List[int], invert: bool):
    n = len(a)
    j = 0
    for i in range(1, n):
        bit = n >> 1
        while j & bit:
            j ^= bit
            bit >>= 1
        j ^= bit
        if i < j:
            a[i], a[j] = a[j], a[i]
    length = 2
    while length <= n:
        w = pow(g_root, (MOD - 1) // length, MOD)
        if invert:
            w = pow(w, MOD - 2, MOD)
        for i in range(0, n, length):
            wn = 1
            for k in range(length // 2):
                u = a[i + k]
                v = a[i + k + length // 2] * wn % MOD
                a[i + k] = (u + v) % MOD
                a[i + k + length // 2] = (u - v) % MOD
                wn = wn * w % MOD
        length <<= 1
    if invert:
        n_inv = pow(n, MOD - 2, MOD)
        for i in range(n):
            a[i] = a[i] * n_inv % MOD

def poly_mul(a: List[int], b: List[int]) -> List[int]:
    result_len = len(a) + len(b) - 1
    n = 1
    while n < result_len:
        n <<= 1
    fa = a + [0] * (n - len(a))
    fb = b + [0] * (n - len(b))
    ntt(fa, False)
    ntt(fb, False)
    for i in range(n):
        fa[i] = fa[i] * fb[i] % MOD
    ntt(fa, True)
    return fa[:result_len]

def poly_inv(f: List[int], n: int) -> List[int]:
    g = [pow(f[0], MOD - 2, MOD)]
    m = 1
    while m < n:
        m2 = m * 2
        fg = poly_mul(f[:m2], g)[:m2]
        neg_fg = [(MOD - x) % MOD for x in fg]
        neg_fg[0] = (neg_fg[0] + 2) % MOD
        g = poly_mul(g, neg_fg)[:m2]
        m = m2
    return g[:n]

def poly_deriv(f: List[int]) -> List[int]:
    return [(i * f[i]) % MOD for i in range(1, len(f))]

def poly_integr(f: List[int]) -> List[int]:
    res = [0] * (len(f) + 1)
    for i in range(len(f)):
        res[i + 1] = f[i] * pow(i + 1, MOD - 2, MOD) % MOD
    return res

def poly_log(f: List[int], n: int) -> List[int]:
    df = poly_deriv(f[:n])
    inv_f = poly_inv(f, n)
    return poly_integr(poly_mul(df, inv_f)[:n - 1])[:n]

def poly_exp(f: List[int], n: int) -> List[int]:
    assert f[0] == 0
    G = [1]
    m = 1
    while m < n:
        m2 = min(m * 2, n)
        lnG = poly_log(G, m2)
        corr = [0] * m2
        corr[0] = (1 - lnG[0] + (f[0] if 0 < len(f) else 0)) % MOD
        for i in range(1, m2):
            fi = f[i] if i < len(f) else 0
            corr[i] = (fi - lnG[i]) % MOD
        G_new = poly_mul(G, corr)[:m2]
        G = G_new
        m = m2
    return G[:n]

def solve():
    N = int(input())
    a = list(map(int, input().split()))
    res = poly_exp(a, N)
    print(*res)

solve()

Step-by-Step 解説

1形式的冪級数 exp の定義
$\exp(F(x)) = \sum_{n=0}^{\infty} \frac{F(x)^n}{n!}$ を $\pmod{x^N}$ で打ち切る。$F(0) = 0$ が必要条件。
2poly_inv（Newton 法で多項式逆元）
$G = F^{-1}$ を求める反復: $G_{2m} = G_m(2 - F \cdot G_m) \pmod{x^{2m}}$。合計 $O(N \log N)$。
3poly_log（微分 + 積分）
$\log F = \int \frac{F'}{F} \, dx$。$F'$ は微分、$F^{-1}$ は Step 2、積分は係数を次数の逆元で割る。
4poly_exp（Newton 法）
$G_0 = 1$、反復: $G_{2m} \leftarrow G_m \cdot (1 + F - \log G_m) \pmod{x^{2m}}$。各反復で精度倍増、$O(N \log N)$。

よくあるミス

ミス原因正しい書き方
poly_log の長さが $N$ を超える積分で長さが1増える最後に [:n] でクリップ
poly_exp の Newton 反復で corr[0] を誤るlog G の定数項は常に 0lnG[0] == 0 を確認
NTT のサイズ計算が足りないmul(a, b) のサイズが len(a)+len(b)-1result_len = len(a)+len(b)-1
pow(i+1, MOD-2, MOD) を毎回呼ぶ積分のたびに逆元計算で遅い逆元テーブルを事前計算

次のステップ

  • 発展問題: FPS の累乗 $F(x)^k \pmod{x^N}$ を $O(N \log N)$ で計算せよ（$k$ が巨大な整数の場合含む）

自己評価

自分の回答

気づき・メモ