問題
素数 $p = 998244353$ の下で計算せよ。
パートA: $N-1$ 次多項式 $f(x)$ と $M$ 個の評価点で $f(x_i)$ を全て求めよ。
パートB: $N$ 個の点 $(x_i, y_i)$ を通る $N-1$ 次多項式の係数列を求めよ（ラグランジュ補間）。
制約
$1 \le N, M \le 10^5$
$0 \le c_i, x_i, y_i < p$
入出力例
入力例 1 (パートA)
3 3
1 2 1
0 1 2出力例 1
1 4 9ヒント (段階的開示)
ヒント1: 方向性
素朴に各点でホーナー法は O(NM) で TLE。分割統治 + FFT/NTT を使って $O(N \log^2 N)$ に落とす。
ヒント2: アプローチ
多点評価：subproduct tree を構築し、根の多項式 $f$ から $f \mod \text{左の子}$、$f \mod \text{右の子}$ を再帰計算。補間は $f(x) = \sum y_i \cdot \frac{P(x)}{(x-x_i) P'(x_i)}$ を分割統治で。
ヒント3: 誘導
def build_subproduct_tree(xs):
# 各葉は (x - xs[i])、内部ノードは左右の積
def multieval(f, tree, size, n):
# f mod tree[node] を再帰で
# 葉では定数項 = f(xs[i])模範解答 (Python)
import sys
input = sys.stdin.readline
MOD = 998244353
g = 3
def ntt(a, invert=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(g, (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, b):
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); ntt(fb)
for i in range(n): fa[i] = fa[i] * fb[i] % MOD
ntt(fa, True)
return fa[:result_len]
def poly_inv(a, n):
res = [pow(a[0], MOD - 2, MOD)]
length = 1
while length < n:
length <<= 1
tmp = a[:min(len(a), length)]
tmp_r = poly_mul(poly_mul(res, res), tmp)
new_res = [0] * length
for i in range(min(length, len(res))):
new_res[i] = (2 * res[i] - tmp_r[i]) % MOD
for i in range(len(res), length):
new_res[i] = (-tmp_r[i]) % MOD
res = new_res
return res[:n]
def poly_divmod(a, b):
if len(a) < len(b): return [0], a
n = len(a) - len(b) + 1
a_rev = a[::-1][:n]
b_rev = b[::-1][:n]
b_inv = poly_inv(b_rev, n)
q = poly_mul(a_rev, b_inv)[:n][::-1]
qb = poly_mul(q, b)
r = [(a[i] - (qb[i] if i < len(qb) else 0)) % MOD for i in range(len(b) - 1)]
return q, r
def poly_mod(f, m):
_, r = poly_divmod(f, m)
return r
def build_subproduct_tree(xs):
n = len(xs)
size = 1
while size < n: size <<= 1
tree = [[0]] * (2 * size)
for i in range(n):
tree[size + i] = [(-xs[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])
return tree, size
def multieval(f, tree, size, n):
tree_f = [None] * (2 * size)
tree_f[1] = poly_mod(f, tree[1])
for i in range(1, size):
tree_f[2*i] = poly_mod(tree_f[i], tree[2*i])
tree_f[2*i+1] = poly_mod(tree_f[i], tree[2*i+1])
return [tree_f[size + i][0] % MOD if tree_f[size + i] else 0 for i in range(n)]
def main():
N, M = map(int, input().split())
c = list(map(int, input().split()))
xs = list(map(int, input().split()))
tree, size = build_subproduct_tree(xs)
vals = multieval(c, tree, size, M)
print(*vals)
main()Step-by-Step 解説
1部分積木の構築
評価点 $x_0, \ldots, x_{n-1}$ から subproduct tree を作る。各葉は $(x - x_i)$、内部ノードは左右の積。
評価点 $x_0, \ldots, x_{n-1}$ から subproduct tree を作る。各葉は $(x - x_i)$、内部ノードは左右の積。
2多点評価（分割統治）
根の $f$ から始め、各ノードで $f \mod \text{子}$ を計算。葉で $f(x_i)$ = 定数項。
根の $f$ から始め、各ノードで $f \mod \text{子}$ を計算。葉で $f(x_i)$ = 定数項。
3ラグランジュ補間
$f(x) = \sum y_i \cdot \frac{P(x)}{(x-x_i) P'(x_i)}$。$P'(x_i)$ を多点評価、$P(x)/(x-x_i)$ を分割統治で。
$f(x) = \sum y_i \cdot \frac{P(x)}{(x-x_i) P'(x_i)}$。$P'(x_i)$ を多点評価、$P(x)/(x-x_i)$ を分割統治で。
4計算量
部分積木構築、多点評価、補間ともに $O(N \log^2 N)$。
部分積木構築、多点評価、補間ともに $O(N \log^2 N)$。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| poly_inv で a[0]=0 | 逆元が存在しない | 事前チェックが必要 |
| subproduct tree の空葉処理 | [1] (単位元) で埋める | サイズを2のべき乗に揃える |
| ラグランジュで xi が重複 | P'(xi)=0 になる | 問題制約で禁止されているが要確認 |
次のステップ
- 発展: 任意の素数 mod や多倍長整数での多項式演算、GCD 多項式