問題
多項式 $F(x) = \sum_{i=0}^{N-1} f_i x^i$ に対し、$\pmod{x^N}$ での $F^{-1}$、$\sqrt{F}$、$\exp(F)$ を求めよ（$P = 998244353$）。
制約
| パラメータ | 範囲 |
|---|---|
| $N$ | $1 \le N \le 2^{17}$ |
| $f_i$ | $0 \le f_i < P$ |
| 逆元 | $f_0 \neq 0$ が保証 |
| 平方根 | $f_0 = 1$ が保証 |
| 指数関数 | $f_0 = 0$ が保証 |
入出力例
入力例 1
4
1 1 0 0出力例 1
(F=1+x の各演算結果 mod P、4項分)$F(x) = 1 + x$。$F^{-1} = 1 - x + x^2 - x^3 \equiv [1, P-1, 1, P-1]$。$\sqrt{1+x} = 1 + x/2 - x^2/8 + \ldots$ をmod Pで表現。$\exp(x) = 1 + x + x^2/2 + x^3/6$ をmod Pで表現。
概念図: FPS Newton反復の構造
ヒント（段階的開示）
ヒント1: 方向性
全演算は Newton 反復法（倍精度法）で統一的に実現。NTT で多項式乗算を $O(N \log N)$ にすることで全体が $O(N \log N)$ になる。$P = 998244353$ は NTT-friendly 素数。
ヒント2: アプローチ
- inv: $G \leftarrow G(2 - FG)$ で精度を倍に
- log: $\int F' / F$ として inv を使って計算
- exp: $G \leftarrow G(1 + F - \log G)$ で精度を倍に
- sqrt: $G \leftarrow (G + F/G)/2$ で精度を倍に
- 各ステップは $\text{mod } x^{2^{k+1}}$ まで切り詰めて計算
ヒント3: コード骨格
def fps_inv(f, n):
g = [pow(f[0], P-2, P)]
sz = 1
while sz < n:
sz = min(sz*2, n)
fg = poly_mul(f[:sz], g)[:sz]
neg = [(2-x)%P for x in fg]
g = poly_mul(g, neg)[:sz]
return g[:n]
def fps_log(f, n):
df = [f[i]*i%P for i in range(1,n)] + [0]
finv = fps_inv(f, n)
prod = poly_mul(df, finv)[:n]
return [0]+[prod[i]*pow(i+1,P-2,P)%P for i in range(n-1)]
def fps_exp(f, n):
g = [1]; sz = 1
while sz < n:
sz = min(sz*2, n)
lg = fps_log(g, sz)
h = [(f[i] if i模範解答 (Python)
import sys
input = sys.stdin.readline
P = 998244353
g_prim = 3
def ntt(a, invert):
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_prim, (P - 1) // length, P)
if invert:
w = pow(w, P - 2, P)
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 % P
a[i + k] = (u + v) % P
a[i + k + length // 2] = (u - v) % P
wn = wn * w % P
length <<= 1
if invert:
n_inv = pow(n, P - 2, P)
for i in range(n):
a[i] = a[i] * n_inv % P
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, False); ntt(fb, False)
for i in range(n):
fa[i] = fa[i] * fb[i] % P
ntt(fa, True)
return fa[:result_len]
def fps_inv(f, n):
g = [pow(f[0], P - 2, P)]
sz = 1
while sz < n:
sz = min(sz * 2, n)
fg = poly_mul(f[:sz], g)[:sz]
g = poly_mul(g, [(2 - x) % P for x in fg])[:sz]
return g[:n]
def fps_log(f, n):
df = [f[i] * i % P for i in range(1, n)] + [0]
finv = fps_inv(f, n)
prod = poly_mul(df, finv)[:n]
return [0] + [prod[i] * pow(i + 1, P - 2, P) % P for i in range(n - 1)]
def fps_exp(f, n):
g = [1]
sz = 1
while sz < n:
sz = min(sz * 2, n)
log_g = fps_log(g, sz)
h = [(f[i] if i < len(f) else 0) - log_g[i] for i in range(sz)]
h[0] = (h[0] + 1) % P
g = poly_mul(g, [x % P for x in h])[:sz]
return g[:n]
def fps_sqrt(f, n):
inv2 = (P + 1) // 2
g = [1]
sz = 1
while sz < n:
sz = min(sz * 2, n)
ginv = fps_inv(g, sz)
fg = poly_mul(f[:sz], ginv)[:sz]
g = [((g[i] if i < len(g) else 0) + fg[i]) % P * inv2 % P for i in range(sz)]
return g[:n]
def solve():
N = int(input())
f = list(map(int, input().split()))
f = f[:N] + [0] * max(0, N - len(f))
g1 = fps_inv(f, N)
g2 = fps_sqrt(f, N)
f_exp = f[:]
f_exp[0] = 0
g3 = fps_exp(f_exp, N)
print(' '.join(map(str, g1)))
print(' '.join(map(str, g2)))
print(' '.join(map(str, g3)))
solve()Step-by-Step 解説
Step 1: NTT（Number Theoretic Transform）
$P = 998244353 = 119 \times 2^{23} + 1$ は NTT-friendly 素数。原始根 $g = 3$。ビット逆順置換後にバタフライ演算で $O(N \log N)$ 変換。逆変換は $\omega$ の代わりに $\omega^{-1}$ を使い、最後に $N^{-1}$ を掛ける。
Step 2: fps_inv（逆元）
Newton 反復: $G_{k+1} \equiv G_k(2 - FG_k) \pmod{x^{2^{k+1}}}$
初期値 $G_1 \equiv f_0^{-1} \pmod{x}$。各反復で精度が2倍になる。
Step 3: fps_log（対数）
$$\log F = \int \frac{F'}{F} \pmod{x^N}$$
微分 $F'_i = (i+1) f_{i+1}$、積分 $(h)_i \to h_i / (i+1)$ をmod P上で計算。
Step 4: fps_exp（指数関数）
Newton 反復: $G_{k+1} \equiv G_k(1 + F - \log G_k) \pmod{x^{2^{k+1}}}$
各反復で fps_log を呼ぶため合計 $O(N \log N)$。
Step 5: 計算量まとめ
| 演算 | 計算量 |
|---|---|
| fps_inv | $O(N \log N)$ |
| fps_log | $O(N \log N)$（inv × 1 + poly_mul × 1） |
| fps_exp | $O(N \log N)$（各反復で log × 1） |
| fps_sqrt | $O(N \log N)$（各反復で inv × 1） |
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| NTTサイズが2の冪でない | result_len に直接使うとNG | while n < result_len: n <<= 1 |
| log の定数項が0でない | log F の [0] 項は常に0 | result = [0] + [...] |
| exp に f[0] != 0 を渡す | exp の前提条件違反 | f_exp[0] = 0 に強制設定 |
| mod P の符号ミス | Python は負数をそのまま保持 | (2 - x) % P で符号を修正 |
| inv2 の計算ミス | P が奇素数なので (P+1)//2 が逆元 | inv2 = (P+1)//2 |
次のステップ
発展問題: fps_pow(F, k) = exp(k × log F) を使った任意べき乗。関連: 多項式 GCD $O(N \log^2 N)$、多項式行列累乗、EGF の exp 応用（順列・Set分割の数え上げ）。