Formal power series

Operations

Multiplication

Multiplying two finite formal power series is the same as multiplying two polynomials. That can be done in \(O(n\log n)\) time with Fast Fourier transform.

Division

Calculating the multiplicative inverse of a formal power series can be done in \(O(n\log n)\). 1

Square root

Calculating the square root of a formal power series can be done in \(O(n\log n)\). 2

See also


  1. http://codeforces.com/blog/entry/12513

  2. http://codeforces.com/blog/entry/12513