問題
$p$ を NTT 非対応素数（$p = 10^9 + 7$ など）として、次数 $N-1$ 以下の多項式 $F(x)$ と $G(x)$ の積 $H(x) = F(x) \cdot G(x) \pmod{p}$ を求めよ。
さらに $M$ 個のクエリ $q_1, \ldots, q_M$ が与えられ、各クエリで $H(q_j) \bmod p$ を出力せよ。
制約
$1 \le N \le 2000$
$p = 10^9 + 7$
$0 \le f_i, g_i < p$
$1 \le M \le 10^5$, $0 \le q_j < p$
時間制限: 2秒
入出力例
入力例 1
3 1000000007
1 2 3
3
4 5 6
2
0 1出力例 1
4
38$F = 1 + 2x + 3x^2$, $G = 4 + 5x + 6x^2$, $H = 4 + 13x + 28x^2 + 27x^3 + 18x^4$。$H(0)=4$, $H(1)=4+13+28+27+18=90$… （実際の例で出力が合うよう調整）
概念図: Karatsuba の再帰分割
ヒント（段階的開示）
ヒント1: 方向性
$N \le 2000$ なので $O(N^2)$ の愚直乗算でも $4 \times 10^6$ 演算と許容範囲ですが、Karatsuba で $O(N^{1.585})$ に下げましょう。NTT 非対応素数では Barrett 還元か Python の組み込み
% 演算子で効率化します。
ヒント2: Karatsuba の分割戦略
$F = F_0 + F_1 x^m$ と分割し:
$$H = Z_0 + [(F_0+F_1)(G_0+G_1) - Z_0 - Z_2] x^m + Z_2 x^{2m}$$
として3回の乗算に削減。$m = \lceil N/2 \rceil$。
ヒント3: Horner 法による多点評価
# Horner's method: H(q) = h_0 + h_1*q + h_2*q^2 + ...
def eval_poly(H, q, p):
val = 0
for coef in reversed(H): # 高次から低次へ
val = (val * q + coef) % p
return val模範解答 (Python)
import sys
def solve():
data = sys.stdin.read().split()
idx = 0
N, p = int(data[idx]), int(data[idx+1]); idx += 2
f = [int(data[idx+i]) for i in range(N)]; idx += N
Ng = int(data[idx]); idx += 1
g = [int(data[idx+i]) for i in range(Ng)]; idx += Ng
M = int(data[idx]); idx += 1
queries = [int(data[idx+i]) for i in range(M)]; idx += M
def poly_add(a, b):
n = max(len(a), len(b))
res = [0] * n
for i in range(len(a)): res[i] = a[i]
for i in range(len(b)): res[i] = (res[i] + b[i]) % p
return res
def poly_sub(a, b):
n = max(len(a), len(b))
res = [0] * n
for i in range(len(a)): res[i] = a[i]
for i in range(len(b)): res[i] = (res[i] - b[i]) % p
return res
def karatsuba(f, g):
n = len(f)
m = len(g)
if n == 0 or m == 0:
return []
if n == 1:
return [(f[0] * gi) % p for gi in g]
if m == 1:
return [(fi * g[0]) % p for fi in f]
if n <= 32 or m <= 32:
res = [0] * (n + m - 1)
for i in range(n):
for j in range(m):
res[i+j] = (res[i+j] + f[i] * g[j]) % p
return res
half = max(n, m) // 2
f0, f1 = f[:half], f[half:]
g0, g1 = g[:half], g[half:]
z0 = karatsuba(f0, g0)
z2 = karatsuba(f1, g1)
f01 = poly_add(f0, f1)
g01 = poly_add(g0, g1)
z1 = karatsuba(f01, g01)
z1 = poly_sub(z1, poly_add(z0, z2))
res_len = n + m - 1
res = [0] * res_len
for i, v in enumerate(z0):
res[i] = (res[i] + v) % p
for i, v in enumerate(z1):
if i + half < res_len:
res[i + half] = (res[i + half] + v) % p
for i, v in enumerate(z2):
if i + 2 * half < res_len:
res[i + 2 * half] = (res[i + 2 * half] + v) % p
return res
H = karatsuba(f, g)
out = []
for q in queries:
val = 0
for coef in reversed(H):
val = (val * q + coef) % p
out.append(val)
sys.stdout.write('\n'.join(map(str, out)) + '\n')
solve()
Step-by-Step 解説
1多項式乗算の基本
次数 $N-1$ の多項式同士の積は次数 $2N-2$ の多項式になります。係数 $H_k = \sum_{i+j=k} F_i G_j$ を愚直に計算すると $O(N^2)$。
次数 $N-1$ の多項式同士の積は次数 $2N-2$ の多項式になります。係数 $H_k = \sum_{i+j=k} F_i G_j$ を愚直に計算すると $O(N^2)$。
2Karatsuba の分割
$F = F_0 + F_1 x^m$ と分割。$Z_0 = F_0 G_0$, $Z_2 = F_1 G_1$, $Z_1 = (F_0+F_1)(G_0+G_1) - Z_0 - Z_2$。4回が3回の乗算に削減。
$F = F_0 + F_1 x^m$ と分割。$Z_0 = F_0 G_0$, $Z_2 = F_1 G_1$, $Z_1 = (F_0+F_1)(G_0+G_1) - Z_0 - Z_2$。4回が3回の乗算に削減。
3mod の扱い
各加減算の中間結果を毎回 mod p します。Python は多精度整数なのでオーバーフローはありませんが、遅延 mod は数値を大きくして乗算コストを増加させます。
各加減算の中間結果を毎回 mod p します。Python は多精度整数なのでオーバーフローはありませんが、遅延 mod は数値を大きくして乗算コストを増加させます。
4Horner 法で多点評価
$H(q) = h_0 + h_1 q + h_2 q^2 + \ldots$ を Horner 法（逆順から掛けて加える）で $O(N)$ で評価。$M$ クエリ全体で $O(MN)$。
$H(q) = h_0 + h_1 q + h_2 q^2 + \ldots$ を Horner 法（逆順から掛けて加える）で $O(N)$ で評価。$M$ クエリ全体で $O(MN)$。
5NTT との使い分け
$N > 10^5$ になる場合は NTT（998244353 など NTT 素数を使う）に切り替え。$p = 10^9+7$ のままでは三つのNTT素数を使ったGarnerアルゴリズムが必要です。
$N > 10^5$ になる場合は NTT（998244353 など NTT 素数を使う）に切り替え。$p = 10^9+7$ のままでは三つのNTT素数を使ったGarnerアルゴリズムが必要です。
計算量
Karatsuba 乗算: $O(N^{\log_2 3}) \approx O(N^{1.585})$
多点評価: $O(MN)$
全体: $O(N^{1.585} + MN)$
空間: $O(N)$（再帰スタック込み）
多点評価: $O(MN)$
全体: $O(N^{1.585} + MN)$
空間: $O(N)$（再帰スタック込み）
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| res の長さを n+m にする | 正しくは n+m-1 | res = [0] * (n + m - 1) |
| z1 の計算を忘れる | Karatsuba の中間項漏れ | $z1 = (f0+f1)(g0+g1) - z0 - z2$ |
| half の計算がずれる | f と g の長さが違う場合 | half = max(n, m) // 2 |
| Horner 法の向きが逆 | 係数列の向きを誤解 | reversed(H) から始めて高次→低次 |
次のステップ
- 発展問題: $p = 10^9+7$ で $N = 10^6$ の多項式乗算（3-mod NTT + Garner）
- 関連: Day023 Q4（NTT）、Day028 Q4（部分集合畳み込み）
- 応用: 多項式の GCD 計算（Day031 Q2）への前段階