Nim-ACL

FPS facade

atcoder/extra/math/fps is a convenience facade for modint-based formal power series.

The existing atcoder/extra/math/formal_power_series module is kept compatible. If you want to explicitly choose a convolution backend or use more generic coefficient types, import formal_power_series directly.

Import

import atcoder/extra/math/fps

The fps module is intended as a short competitive-programming entry point for modint + NTT based formal power series.

Basic usage

import atcoder/extra/math/fpstype mint = modint998244353useFPS(mint{x}, F, prec = 100)let f = F(@[0, 1]) # resized to length 100let g = f.exp()    # length 100let h = f.exp(50)  # explicit length 50 overrides the default

useFPS(mint{x}, F, prec = 100) declares the coefficient type mint, the variable name x, the constructor name F, and the default precision 100.

Custom variable name

useFPS(mint{y}, G, prec = 50)let f = G(y)

Use mint{y} to inject y as the formal variable.

Default precision

When the length is omitted, constructors such as F(@[...]) and F(x) resize the series to the default precision.

useFPS(mint{x}, F, prec = 8)

let f = F(@[0, 1])
doAssert f.len == 8

An explicit length always overrides the default.

let f = F(@[0, 1], 3)
doAssert f.len == 3

Existing FPS methods such as f.exp() usually use the current length of the input series. Therefore, resizing at construction time makes f.exp() use the declared default precision.

Difference from formal_power_series

SageMath-like string declaration

useFPSDecl provides a SageMath-like string declaration helper.

useFPSDecl(H = mint{z}, prec = 6)

let f = H(z)
let g = f.exp()

This declares H as the constructor name, mint as the coefficient type, z as the formal variable name, and 6 as the default precision.

The more basic Nim-style syntax is:

useFPS(mint{z}, H, prec = 6)

useFPSDecl is a convenience helper for readability. If you prefer type resolution and editor support, use useFPS(mint{z}, H, prec = 6).

You can also write the declaration as a string.

useFPSDecl("H = mint{z}", prec = 6)

Angle-bracket string declaration

In string declarations, both mint{z} and mint<z> are supported.

useFPSDecl("L = mint<t>", prec = 9)

let f = L(t)

mint<t> is convenience syntax only inside a string declaration. In normal Nim syntax, use useFPSDecl(L = mint{t}, prec = 9) or useFPS(mint{t}, L, prec = 9).

Default precision and existing operations

Constructors provided by the fps facade resize the series to prec when the length is omitted.

Therefore, existing FPS methods that use the input length naturally follow the default precision chosen at construction time.

useFPS(mint{x}, F, prec = 8)

let f = F(1 + x)   # length 8
let g = f.inv()    # length 8
let h = f.exp()    # length 8

An explicit length always overrides the default precision.

let f = F(1 + x, 4)
doAssert f.len == 4

Default precision with additional operations

The fps facade also imports/exports formal_power_series_sqrt, so sqrt is available from the same entry point.

import std/options
import atcoder/extra/math/fps

type mint = modint998244353
useFPS(mint{x}, F, prec = 8)

let f = F(1 + 2 * x + x^2)
let g = f.sqrt()

doAssert g.isSome
doAssert g.get.len == 8

Existing formal_power_series operations such as powMod and eval can also be used as usual.

let base = F(@[0, 1])
let m = F(@[-1, 0, 0, 1], 4) # x^3 - 1
let r = base.powMod(5, m)    # x^5 mod (x^3 - 1) = x^2

doAssert r[2] == mint(1)

let h = F(@[1, 2, 3])
doAssert h.eval(mint(2)) == mint(17)

String constructor and log / exp

Constructors from strings such as F("x") also follow the default precision.

useFPS(mint{x}, F, prec = 8)

let f = F("x")
doAssert f.len == 8

log and exp can be used through the usual input-length behavior.

let f = F(1 + x)
let g = f.log()
let h = g.exp()

doAssert g.len == 8
doAssert h.len == 8
doAssert h[0] == mint(1)
doAssert h[1] == mint(1)

Explicit lengths still override the default.

let g = f.log(5)
let h = g.exp(5)

doAssert g.len == 5
doAssert h.len == 5

Constructor overload examples

The fps facade constructors accept arrays, seq[int], seq[mint], existing FPS values, and formal variables.

useFPS(mint{x}, F, prec = 8)let a = F([1, 2, 3])let b = F(@[mint(1), mint(2), mint(3)])let c = F(x, 4)doAssert a.len == 8doAssert b.len == 8doAssert c.len == 4

You can also pass an existing FPS and only change its length.

let f = F(@[1, 2, 3])let g = F(f, 5)let h = F(f, 2)doAssert g.len == 5doAssert h.len == 2