Day 061-Q5 — 多項式多点評価・補間（積多項式ツリー）

問題

$N-1$ 次以下の多項式 $f(x)$ が係数列として与えられる。また $N$ 個の異なる点 $x_0, x_1, \ldots, x_{N-1}$ が与えられる。

Part 1 (多点評価): $f(x_0), f(x_1), \ldots, f(x_{N-1})$ を全て $\bmod p$ で求めよ。

Part 2 (多項式補間): $N$ 個の点 $(x_i, y_i)$ を通る $N-1$ 次以下の多項式 $g(x)$ の係数列を求めよ。

$p = 998244353$。

入出力例

4
1 0 1 0
0 1 2 3
0 1 4 9

1 2 5 10
1 0 1 0

$f(x) = x^2 + 1$。評価: $f(0)=1, f(1)=2, f(2)=5, f(3)=10$。補間: $(0,0),(1,1),(2,4),(3,9)$ を通る多項式 → $g(x) = x^2$ → 係数 $[0,0,1,0]$。実際 $y = [0,1,4,9] = x^2$ なので $g$ の係数は $[0,0,1,0]$。

概念図: 積多項式ツリーと多点評価

ヒント（段階的開示）

# 積多項式ツリーの構築
def build_ptree(pts, sz):
    tree = [[1]] * (2*sz)
    for i, x in enumerate(pts):
        tree[sz+i] = [(-x)%MOD, 1]  # (x - x_i)
    for i in range(sz-1, 0, -1):
        tree[i] = poly_mul(tree[2*i], tree[2*i+1])
    return tree

# 多点評価（Top-Down）
def multieval(f, tree, sz, n):
    vals = [None]*(2*sz)
    vals[1] = poly_mod(f, tree[1])
    for i in range(1, sz):
        vals[2*i]   = poly_mod(vals[i], tree[2*i])
        vals[2*i+1] = poly_mod(vals[i], tree[2*i+1])
    return [vals[sz+i][0] if vals[sz+i] else 0 for i in range(n)]

模範解答 (Python)

コピーimport sys
input = sys.stdin.readline
MOD = 998244353

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

def poly_mul(a, b):
    if not a or not b: return [0]
    n = 1
    while n < len(a)+len(b)-1: n <<= 1
    fa=a+[0]*(n-len(a)); fb=b+[0]*(n-len(b))
    ntt(fa); ntt(fb)
    fc=[x*y%MOD for x,y in zip(fa,fb)]
    ntt(fc, inv=True)
    return fc[:len(a)+len(b)-1]

def poly_inv(f, K):
    g = [pow(f[0], MOD-2, MOD)]; sz = 1
    while sz < K:
        sz2 = min(sz*2, K)
        ng = 1
        while ng < sz2*2: ng <<= 1
        fg = f[:sz2]+[0]*(ng-min(len(f),sz2))
        gg = g+[0]*(ng-len(g))
        ntt(fg); ntt(gg)
        tmp=[((2 if i==0 else 0)-fg[i]*gg[i])%MOD*gg[i]%MOD for i in range(ng)]
        ntt(tmp, inv=True); g=tmp[:sz2]; sz=sz2
    return g[:K]

def poly_divmod(a, b):
    if len(a) < len(b): return [0], a[:]
    n = len(a)-len(b)+1
    ar=a[::-1][:n]; br=b[::-1][:n]
    q_rev=poly_mul(ar, poly_inv(br, n))[:n]
    q=q_rev[::-1]
    r_full=poly_mul(q, b)
    r=[(a[i]-(r_full[i] if i