問題
次数 N の多項式 $F(x)$ (係数 mod $p = 998244353$) について、(1) 微分, (2) 積分, (3) 逆元, (4) log, (5) exp を計算。
制約
$1 \le N \le 2 \times 10^5$
$0 \le a_i < p$
入出力例
入力例 1
4
1 2 3 4 5出力例 1
# 微分: 2 6 12 20
# 積分: 0 1 1 1 1 1
# 逆元: 1 998244351 1 998244349ヒント (段階的開示)
ヒント1: 方向性
NTT で多項式乗算 $O(N \log N)$。逆元・log・exp は Newton 法で $O(N \log N)$。
ヒント2: アプローチ
逆元 Newton: $G_{k+1} = G_k(2 - F G_k)$。exp Newton: $H_{k+1} = H_k(1 - \log H_k + F)$。
ヒント3: 誘導
log = ∫(F'/F) = 微分 + 逆元 + 積分。MOD = 998244353 は NTT-friendly。
模範解答 (Python)
import sys
input = sys.stdin.readline
MOD = 998244353
g = 3
def power(a, b, mod):
res = 1; a %= mod
while b > 0:
if b & 1:
res = res * a % mod
a = a * a % mod
b >>= 1
return res
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 = power(g, (MOD - 1) // length, MOD)
if inv:
w = power(w, MOD - 2, MOD)
for i in range(0, n, length):
wn = 1
for k in range(length // 2):
u, v = a[i+k], 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:
n_inv = power(n, MOD - 2, MOD)
for i in range(n):
a[i] = a[i] * n_inv % MOD
def poly_mul(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); ntt(fb)
for i in range(n):
fa[i] = fa[i] * fb[i] % MOD
ntt(fa, inv=True)
return fa
def poly_inv(f, n):
g_arr = [power(f[0], MOD - 2, MOD)]
length = 1
while length < n:
length <<= 1
fg = poly_mul(f[:length], g_arr)[:length]
neg_fg = [(2 - x) % MOD if i == 0 else (-x) % MOD for i, x in enumerate(fg)]
g_arr = poly_mul(g_arr, neg_fg)[:length]
return g_arr[:n]
def poly_deriv(f):
return [i * f[i] % MOD for i in range(1, len(f))]
def poly_integr(f):
n = len(f)
inv_i = [0, 1]
for i in range(2, n + 1):
inv_i.append(-(MOD // i) * inv_i[MOD % i] % MOD)
return [0] + [f[i] * inv_i[i+1] % MOD for i in range(n)]
def solve():
N = int(input())
a = list(map(int, input().split()))
deriv = poly_deriv(a)
print("Derivative:", deriv)
integ = poly_integr(a)
print("Integral:", integ[:N+1])
if a[0] != 0:
inv_f = poly_inv(a, N)
print("Inverse:", inv_f[:N])
solve()Step-by-Step 解説
1NTT
MOD = $998244353 = 119 \times 2^{23} + 1$ で原始根 g=3。FFT の有限体版。
MOD = $998244353 = 119 \times 2^{23} + 1$ で原始根 g=3。FFT の有限体版。
2逆元の Newton 法
$G_{k+1} = G_k(2 - F G_k)$ で精度が倍に、$\log N$ 回で完成。
$G_{k+1} = G_k(2 - F G_k)$ で精度が倍に、$\log N$ 回で完成。
3log/exp
log = ∫(F'/F)、exp は Newton 法。いずれも $O(N \log N)$。
log = ∫(F'/F)、exp は Newton 法。いずれも $O(N \log N)$。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| poly_mul 後の長さ超過 | 結果が 2N-1 | [:n] でトリム |
| 逆数計算の負数 | Python の % 注意 | 常に % MOD |
| exp の初期値 | H_0 = 0 にしてしまう | H_0 = [1] |
次のステップ
- 多項式合成 $F(G(x))$ を $O(N^{1.5} \log N)$ で