Day 077-Q4 — 多項式剰余木・多点評価（Polynomial Remainder Tree + Subproduct Tree O(N log²N)）

2026-06-30 赤色 Master / Phase 8+ ★★★★★★★★★ 多点評価・Subproduct Tree・NTT・余定理

問題

次数 $N-1$ 以下の多項式 $f(x)$ と $N$ 個の評価点 $x_1, x_2, \ldots, x_N$ が与えられる。$f(x_1), f(x_2), \ldots, f(x_N)$ をすべて求めよ。答えは $998244353$ で割った余りを出力せよ。

制約

パラメータ範囲備考
$N$$1 \le N \le 2 \times 10^5$多項式の次数 + 1 = 評価点数
$a_i$$0 \le a_i < 998244353$係数（mod 998244353）
$x_i$$0 \le x_i < 998244353$評価点（互いに異なる）

入出力例

入力例1

4
1 2 3 4
0 1 2 3

出力例1

1
10
49
142

$f(x) = 1 + 2x + 3x^2 + 4x^3$。$f(0)=1, f(1)=10, f(2)=1+4+12+32=49, f(3)=1+6+27+108=142$。

概念図: Subproduct Tree の構造

Subproduct Tree: 積多項式木（構築フェーズ ↑） (x-x₀)(x-x₁)(x-x₂)(x-x₃) M_{[0,3]} = 次数4 (x-x₀)(x-x₁) M_{[0,1]} = 次数2 (x-x₂)(x-x₃) M_{[2,3]} = 次数2 (x-x₀) (x-x₁) (x-x₂) (x-x₃) 下降フェーズ: f mod M_{[l,r]} を伝播 ↓ f mod M_{[0,3]} → f mod M_{[0,1]} , f mod M_{[2,3]} 葉では f mod (x-xᵢ) = f(xᵢ)（余定理） 計算量: O(N log²N) — 愚直 O(N²) の大幅改善

構築フェーズで葉から根へ積を計算。下降フェーズで根から葉へ多項式剰余を伝播。葉での剰余 = 多項式の余定理により評価値。

ヒント

ヒント1（方向性）

愚直に各 $x_i$ に代入すると $O(N^2)$。$N = 2 \times 10^5$ では間に合わない。$O(N \log^2 N)$ アルゴリズムが存在する。

ヒント2（アプローチ）

Subproduct Tree（積多項式木）+ 分割統治的剰余伝播:
1. $M_{[l,r]}(x) = \prod_{i=l}^{r} (x-x_i)$ を完全二分木で管理
2. $f \bmod M_{[l,r]}$ を根から葉へ伝播
3. 葉では $f \bmod (x-x_i) = f(x_i)$（多項式の余定理）

ヒント3（ほぼ答え） 
# 下降フェーズ
tree[1] = poly_mod(f, tree[1])  # f mod M_{[0,N-1]}
for i in range(1, size):
    tree[2*i]   = poly_mod(tree[i], tree[2*i])
    tree[2*i+1] = poly_mod(tree[i], tree[2*i+1])

模範解答

import sys
input = sys.stdin.readline

MOD = 998244353

def ntt(a, invert, mod=MOD):
    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(3, (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 poly_mul(a, b, mod=MOD):
    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)
    fc = [fa[i] * fb[i] % mod for i in range(n)]
    ntt(fc, True)
    return fc[:result_len]

def poly_mod(a, b, mod=MOD):
    """多項式剰余 a mod b（簡易実装）"""
    a = [x % mod for x in a]
    b = [x % mod for x in b]
    while len(a) >= len(b):
        if a[-1] == 0:
            a.pop()
            continue
        ratio = a[-1] * pow(b[-1], mod - 2, mod) % mod
        for i in range(len(b)):
            a[len(a)-len(b)+i] = (a[len(a)-len(b)+i] - ratio * b[i]) % mod
        while a and a[-1] == 0:
            a.pop()
    return a if a else [0]

def multipoint_eval(f, points):
    n = len(points)
    size = 1
    while size < n:
        size <<= 1
    tree = [[0]] * (2 * size)

    for i in range(n):
        tree[size + i] = [(-points[i]) % MOD, 1]
    for i in range(n, size):
        tree[size + i] = [1]

    for i in range(size - 1, 0, -1):
        tree[i] = poly_mul(tree[2*i], tree[2*i+1])

    tree[1] = poly_mod(f, tree[1])
    for i in range(1, size):
        tree[2*i]   = poly_mod(tree[i], tree[2*i])
        tree[2*i+1] = poly_mod(tree[i], tree[2*i+1])

    result = []
    for i in range(n):
        rem = tree[size + i]
        result.append(rem[0] % MOD if rem else 0)
    return result

def solve():
    N = int(input())
    f = list(map(int, input().split()))
    xs = list(map(int, input().split()))
    ans = multipoint_eval(f, xs)
    print('\n'.join(map(str, ans)))

solve()

Step-by-Step 解説

Step 1: なぜ多点評価が難しいか

愚直: 各 $x_i$ に対して Horner 法で $O(N)$ → 合計 $O(N^2)$。$N=2\times10^5$ では TLE。

Step 2: Subproduct Tree の構築

$M_{[l,r]}(x) = \prod_{i=l}^{r}(x-x_i)$ を完全二分木で管理。葉→根の順に NTT で $O(k \log k)$ の多項式乗算。構築コスト: $O(N \log^2 N)$。

Step 3: 多項式余定理

$f(x) \div (x-c)$ の余りは $f(c)$。したがって葉ノードに蓄積した定数が評価値になる。

Step 4: 計算量

フェーズ計算量
Subproduct Tree 構築$O(N \log^2 N)$
下降フェーズ（剰余伝播）$O(N \log^2 N)$
合計$O(N \log^2 N)$

よくあるミス

ミス原因正しい書き方
葉の多項式符号ミス$(x - x_i)$ の係数[(-x_i) % MOD, 1]（低次から）
剰余の方向ミス積から余を取る順序poly_mod(f_mod, subtree_poly)
NTT の素数998244353 専用実装原始根 3 を使用
木のサイズ計算$N$ が 2 のべき乗でないsize を 2 のべき乗に切り上げ

次のステップ

  • 発展問題: 多点補間（$N$ 個の $(x_i, y_i)$ から多項式を復元）→ Lagrange 補間 $O(N \log^2 N)$
  • 応用: $N$ 個の評価値から元の多項式を再構成する「多項式補間」

自己評価