形式的冪級数の実装

形式的冪級数$ f(x) = \sum_{i = 0}^{\infty} a_i x^iは、普通は係数の配列$ aとして表現される。

無限までの総和になっているが、実際は必要なところまで持てばいい。

ここでは$ f(x) = \sum_{i = 0}^{N} a_i x^i, g(x) = \sum_{i = 0}^{M} b_i x^i, h(x) = \sum_{i = 0}^{L} c_i x^iとする。

四則演算

$ h(x) = f(x) \pm g(x)

各項について足す。

短い方に合わせる。

$ L = \max(N, M)

$ c_i = a_i \pm b_i

$ h(x) = f(x) g(x)

畳み込みをする。NTTなどを使って実装すると$ O(L \log L)に。

$ L = N + M - 1

$ c_i = \sum_{j = 0}^{i} a_j b_{i - j}

$ h(x) = f^{-1}(x)

$ h(x) = \frac{f(x)}{g(x)}

$ h(x) = f(x) g^{-1}(x)をする。

指数

$ h(x) = (f(x))^n

$ h(x) = \exp (n \log f(x))→$ O(N \log N)

微分・積分

多項式の微分・積分をする。

$ h(x) = \frac{\rm d}{{\rm d} x} f(x)

$ \frac{\rm d}{{\rm d} x} x^i = i x^{i - 1}より

$ L = N - 1

$ c_i = (i + 1) a_{i + 1}

$ h(x) = \int_0^x f(x) {\rm d} x

$ \int_0^{x} x^i {\rm d} x = \frac{1}{i + 1} x^{i + 1}より

$ L = N + 1

$ c_0 = 0

$ c_i = \frac{1}{i} a_{i - 1} \quad (i \ge 1)

人の実装など

C++

Python

Rust