Imports
-
../../../../../../.nimble/pkgs/cplib-1.0/cplib/convolution/convolution, ../../../../../../.nimble/pkgs/cplib-1.0/cplib/fps/bostan_mori, ../../../../../../.nimble/pkgs/cplib-1.0/cplib/fps/formal_power_series, ../../../../../../.nimble/pkgs/cplib-1.0/cplib/fps/product_tree, ../../../../../../.nimble/pkgs/cplib-1.0/cplib/math/isqrt, ../../../../../../.nimble/pkgs/cplib-1.0/cplib/modint/modint
Types
SparseFPS[T] = seq[SparseTerm[T]]
- Source Edit
SparseTerm[T] = tuple[degree: int, coefficient: T]
- Source Edit
Procs
proc coefficient[T](f: SparseFPS[T]; degree: int): T
- 指定した次数の係数を返す。項が存在しなければ零を返す。 Source Edit
proc constantTerm[T](f: SparseFPS[T]): T
- Source Edit
proc expCoefficient[T](f: SparseFPS[T]; degree: int): T
- 形式的指数関数の x^degree の係数だけを平方分割で求める。 fの次数をdとして計算量は O(d^3 M(sqrt(degree)) log degree)。 Source Edit
proc initSparseFPS[T](terms: openArray[SparseTerm[T]]): SparseFPS[T]
- 次数の重複をまとめ、零係数を除いた疎なFPSを構築する。 Source Edit
proc invCoefficient[T](f: SparseFPS[T]; degree: int): T
- 乗法逆元の x^degree の係数だけを Bostan--Mori法で求める。 fの次数をdとして計算量は O(M(d) log degree)。 Source Edit
proc logCoefficient[T](f: SparseFPS[T]; degree: int): T
- 形式的対数の x^degree の係数だけを Bostan--Mori法で求める。 fの次数をdとして計算量は O(M(d) log degree)。 Source Edit
proc mulPrefix[T](f: seq[T]; g: SparseFPS[T]; n: int): seq[T]
- 密なFPSと疎なFPSの積を x^n で打ち切って返す。 Source Edit
proc powCoefficient[T](f: SparseFPS[T]; k, degree: int): T
- 非負整数冪の x^degree の係数だけを平方分割で求める。 fの次数をdとして計算量は O(d^3 M(sqrt(degree)) log degree)。 Source Edit