Day 072-Q3 — 多項式合成・Taylor展開（FPS Composition via Newton法）

問題

$\mathbb{Z}/p\mathbb{Z}$（$p = 998244353$）上の形式的冪級数 $f(x)$ と $g(x)$ が与えられる（共に $x^N$ の係数まで）。

以下を処理せよ：

1. 合成 $h(x) = f(g(x)) \bmod x^N$
2. 平行移動 $f(x + c) \bmod x^N$（定数 $c$ だけシフト）

$g(0) = 0$ が保証される（合成が well-defined）。

入出力例

4
1 1 1 1
0 1 0 0
2

Composition f(g(x)): 1 1 1 1
Taylor shift f(x+2): 27 27 9 1

4
0 1 0 0
0 2 3 4
0

Composition f(g(x)): 0 2 3 4
Taylor shift f(x+0): 0 1 0 0

概念図: Taylor Shift の数学的構造

ヒント（段階的開示）

def taylor_shift(f, c, N, MOD):
    # 階乗前処理
    fact = [1] * N
    for i in range(1, N): fact[i] = fact[i-1] * i % MOD
    inv_fact = [pow(fact[N-1], MOD-2, MOD)] + [0]*(N-1)
    for i in range(N-2, -1, -1): inv_fact[i] = inv_fact[i+1]*(i+1)%MOD

    # A[j] = f[j]*j!
    a = [f[j] * fact[j] % MOD for j in range(N)]
    # B[j] = c^j/j!
    cp = [1]*N
    for i in range(1,N): cp[i] = cp[i-1]*c%MOD
    b = [cp[j]*inv_fact[j]%MOD for j in range(N)]

    # 畳み込み (A, B_reversed)
    product = ntt_conv(a, b[::-1], MOD)
    return [product[N-1+k]*inv_fact[k]%MOD for k in range(N)]

模範解答 (Python)

コピーimport sys
from sys import stdin

MOD = 998244353
g_prim = 3

def ntt(a, invert):
    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_prim, (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:
        inv_n = pow(n, MOD-2, MOD)
        for i in range(n): a[i] = a[i] * inv_n % MOD

def conv(a, b):
    n = 1
    while n < len(a) + len(b): 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

def taylor_shift(f, c, N):
    fact = [1]*N
    for i in range(1, N): fact[i] = fact[i-1]*i%MOD
    inv_fact = [1]*N
    inv_fact[N-1] = pow(fact[N-1], MOD-2, MOD)
    for i in range(N-2, -1, -1): inv_fact[i] = inv_fact[i+1]*(i+1)%MOD

    a = [f[j]*fact[j]%MOD for j in range(N)]
    cp = [1]*N
    for i in range(1, N): cp[i] = cp[i-1]*c%MOD
    b = [cp[j]*inv_fact[j]%MOD for j in range(N)]
    b_rev = b[::-1]

    product = conv(a, b_rev)
    return [product[N-1+k]*inv_fact[k]%MOD for k in range(N)]

def solve():
    data = stdin.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    f = [int(data[idx+i]) for i in range(N)]; idx += N
    g = [int(data[idx+i]) for i in range(N)]; idx += N
    c = int(data[idx]); idx += 1

    # 合成 f(g(x)) - O(N^2) 直接版
    fg = [0]*N
    gpower = [0]*N
    gpower[0] = 1
    for k in range(N):
        for j in range(N):
            fg[j] = (fg[j] + f[k]*gpower[j]) % MOD
        if k+1 < N:
            new_gp = [0]*N
            for i in range(N):
                for j in range(N-i):
                    new_gp[i+j] = (new_gp[i+j]+gpower[i]*g[j])%MOD
            gpower = new_gp

    print("Composition f(g(x)):", *fg)

    # Taylor shift f(x+c)
    ts = taylor_shift(f, c%MOD, N)
    print(f"Taylor shift f(x+{c}):", *ts)

solve()

Step-by-Step 解説

Step 1: Taylor Shift の数学的背景

Step 2: 畳み込み形式への変換

$[x^k] f(x+c) = \frac{1}{k!} \sum_j (f_j \cdot j!) \cdot \frac{c^{j-k}}{(j-k)!}$

$A_j = f_j \cdot j!$、$B_j = c^j / j!$ として畳み込みの係数に対応させる。

Step 3: NTT による高速化

畳み込みを NTT で $O(N \log N)$ で計算。$B$ を反転して $A \star B_{\rm rev}$ の $[N-1+k]$ 番目の係数が $k$ 次係数に対応。

Step 4: 多項式合成の計算量

任意 $g$ に対する $f(g(x))$ の一般的な高速アルゴリズムは困難。本問の直接法は $O(N^2)$。BSGS 法で $O(N^{1.5} \log N)$ まで落とせる。

よくあるミス

次のステップ

• 発展問題: Bostan-Mori アルゴリズム（線形漸化式の $N$ 項目 $O(N \log^2 N)$）
• 多項式合成の BSGS 法（$O(N^{1.5} \log N)$）
• 形式的冪級数の微分・積分との組み合わせ

自己評価