問題
形式的冪級数 $f(x) = \sum_{i=0}^{N-1} f_i x^i$ と整数 $k$ が与えられる。 $f(x)^k \bmod x^N$ の係数列を $998244353$ で割った余りで出力せよ。
$f_0 = 0$ の場合は $f(x) = x^m \cdot g(x)$（$g_0 \ne 0$）と分解して処理せよ。$k \cdot m \ge N$ の場合は全係数 0 を出力せよ。
制約
$1 \le N \le 2 \times 10^5$
$0 \le k \le 10^{18}$
$0 \le f_i < 998244353$
時間制限: 3秒
入出力例
入力例 1
4 3
1 2 0 0入力例 2
5 2
0 1 0 0 0出力例 1
1 6 12 8出力例 2
0 0 1 0 0概念図: FPS pow の計算フロー
ヒント（段階的開示）
ヒント1: 方向性
$f_0 \ne 0$ のとき $f^k = \exp(k \ln f)$ を FPS の exp/log で計算します。$f_0 = 0$ の場合は先頭の $0$ をカウントして処理を分けましょう。
ヒント2: アプローチ
- 先頭の零を数える: $f = x^m \cdot g$ と分解（$g_0 \ne 0$）
- $k \cdot m \ge N$ なら全 0 出力
- $g^k = \exp(k \cdot \ln g) \bmod x^{N - km}$
- 先頭に $km$ 個の 0 を付けて出力
- $\ln$: $\ln f = \int (f' / f)$、$\exp$: Newton 法 $O(N \log N)$
ヒント3: log_sum_exp と k の扱い
- $g_0^k$ の計算:
pow(g0, k % (MOD-1), MOD)（フェルマー小定理） - $k \cdot \ln g$ の係数乗算: $k \bmod p$ を掛ける（FPS 係数は mod p で計算）
- log の定数項は必ず 0（正規化が必要な理由）
模範解答 (Python)
import sys
input = sys.stdin.readline
MOD = 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, (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, 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 invert:
inv_n = pow(n, MOD-2, MOD)
for i in range(n): a[i] = a[i] * inv_n % MOD
def poly_mul(f, g, n):
size = 1
while size < len(f) + len(g): size <<= 1
a = f[:] + [0]*(size-len(f))
b = g[:] + [0]*(size-len(g))
ntt(a, False); ntt(b, False)
for i in range(size): a[i] = a[i]*b[i]%MOD
ntt(a, True)
return a[:n]
def fps_inv(f, n):
g = [pow(f[0], MOD-2, MOD)]
k = 1
while k < n:
k = min(2*k, n)
g2 = poly_mul(g, g, k)
fg2 = poly_mul(f[:k], g2, k)
g = [(2*g[i] - fg2[i] if i < len(g) else -fg2[i]) % MOD for i in range(k)]
return g[:n]
def poly_diff(f, n):
return [i * f[i] % MOD for i in range(1, min(len(f), n))]
def poly_integrate(f, n):
res = [0]
inv = [0, 1]
for i in range(2, n+1):
inv.append(-(MOD // i) * inv[MOD % i] % MOD)
for i in range(min(len(f), n)):
res.append(f[i] * inv[i+1] % MOD)
return res[:n]
def fps_log(f, n):
df = poly_diff(f, n)
inv_f = fps_inv(f, n)
prod = poly_mul(df, inv_f, n)
return poly_integrate(prod, n)
def fps_exp(f, n):
g = [1]
k = 1
while k < n:
k = min(2*k, n)
lg = fps_log(g, k)
h = [((f[i] if i < len(f) else 0) - lg[i]) % MOD for i in range(k)]
h[0] = (h[0] + 1) % MOD
g = poly_mul(g, h, k)[:k]
return g[:n]
def fps_pow(f, k, n):
m = 0
while m < len(f) and f[m] == 0:
m += 1
if m == len(f):
return [0] * n
km = m * k
if km >= n:
return [0] * n
g = f[m:]
g0 = g[0]
inv_g0 = pow(g0, MOD - 2, MOD)
nn = n - km
h = [v * inv_g0 % MOD for v in g[:nn]]
lg_h = fps_log(h, nn)
k_mod = k % MOD
kg_h = [v * k_mod % MOD for v in lg_h]
exp_h = fps_exp(kg_h, nn)
g0k = pow(g0, k % (MOD - 1), MOD)
res_shift = [v * g0k % MOD for v in exp_h]
return [0] * km + res_shift + [0] * max(0, n - km - len(res_shift))
def main():
N, k = map(int, input().split())
f = list(map(int, input().split()))
ans = fps_pow(f, k, N)
print(*ans[:N])
main()
Step-by-Step 解説
1FPS pow の特殊ケース分類
$f = 0$: 全 0。$f_0 \ne 0$: $\exp(k \ln f)$ を直接適用。$f_0 = 0$: $f = x^m g$（$g_0 \ne 0$）に分解し $km$ ずらして処理。
$f = 0$: 全 0。$f_0 \ne 0$: $\exp(k \ln f)$ を直接適用。$f_0 = 0$: $f = x^m g$（$g_0 \ne 0$）に分解し $km$ ずらして処理。
2FPS log の計算 $O(N \log N)$
$(\ln f)' = f'/f$ から $\ln f = \int (f' \cdot f^{-1})$。FPS 逆元 Newton 法 + NTT 畳み込みで実装。
$(\ln f)' = f'/f$ から $\ln f = \int (f' \cdot f^{-1})$。FPS 逆元 Newton 法 + NTT 畳み込みで実装。
3FPS exp の Newton 法 $O(N \log N)$
$g_{2k} = g_k(1 + f - \ln g_k) \bmod x^{2k}$。倍々精度で収束。
$g_{2k} = g_k(1 + f - \ln g_k) \bmod x^{2k}$。倍々精度で収束。
4pow = exp(k * log) の注意点
$k$ が大きい（$10^{18}$）ため、$g_0^k$ は mod $p-1$ で指数を計算（フェルマー小定理）。係数への $k$ 乗算は mod $p$ で十分。
$k$ が大きい（$10^{18}$）ため、$g_0^k$ は mod $p-1$ で指数を計算（フェルマー小定理）。係数への $k$ 乗算は mod $p$ で十分。
5NTT (Number Theoretic Transform)
$998244353 = 119 \times 2^{23} + 1$ は NTT 素数。原始根 $g = 3$ を使いビット反転 FFT で $O(N \log N)$ 畳み込みを実現。
$998244353 = 119 \times 2^{23} + 1$ は NTT 素数。原始根 $g = 3$ を使いビット反転 FFT で $O(N \log N)$ 畳み込みを実現。
計算量
FPS log: $O(N \log N)$
FPS exp: $O(N \log N)$
FPS pow: $O(N \log N)$ 全体
空間: $O(N)$
FPS exp: $O(N \log N)$
FPS pow: $O(N \log N)$ 全体
空間: $O(N)$
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| $k$ を mod p で使う | $g_0^k$ の計算で誤り | pow(g0, k % (MOD-1), MOD) |
| $f_0 = 0$ 未処理 | log(0) 未定義 | 先頭零カウント後に処理分岐 |
| NTT サイズを合計長より小さくとる | 畳み込み誤り | while size < len(f)+len(g) |
| log の積分で定数項が残る | 正規化漏れ | 正規化後の h[0] が 0 になることを確認 |
次のステップ
- 発展問題: $\sqrt{f}$（FPS square root）を Newton 法で実装する
- 関連: Day035 Q4 FPS exp/log/pow
- 応用: EGF（指数型母関数）を使ったラベル付き構造の数え上げ