Operations on Polynomials and Series

Enumerative CP problems often reduce to polynomial or formal power series (FPS) algebra: multiplication (convolution), division, inverses, log/exp, multipoint eval / interpolation.

This lesson follows CP-Algorithms — Operations on polynomials and series (concepts and complexities; a full poly<T> library lives on that page).

Coefficients are assumed to live in a field (e.g. ℝ, or ℤ/pℤ for prime p) so + − × ÷ (≠0) behave as usual.

Polynomials and convolution

A(x) = a₀ + a₁ x + … + aₙ xⁿ    (aₙ ≠ 0 or A ≡ 0)
deg A = n   (deg 0 := −∞)

Product expands to

C(x) = A B = Σₖ cₖ xᵏ ,   cₖ = Σᵢ aᵢ bₖ₋ᵢ

The sequence (cₖ) is the convolution of (aᵢ) and (bⱼ). Write [xᵏ]A for the coefficient of xᵏ.

Complexity: naive O(nm); FFT / NTT → O(N log N) with N ≥ n+m+1. Almost every advanced op below uses mul as a subroutine.

Combinatorics: if A and B generate ways to build objects by “size”, then AB generates pairs by total size (dice sums, knapsacks of two kinds, …).

Formal power series

An FPS is an infinite sum A(x)=Σ_{i≥0} aᵢ xⁱ treated formally (no convergence required). Multiplication uses the same finite convolution for each cₖ. Polynomials are FPS with finitely many nonzero coeffs.

If a₀ ≠ 0, there is a unique inverse series A⁻¹ with A · A⁻¹ = 1. Working mod xⁿ means keeping the first n coefficients.

Long division

For polynomials B ≠ 0 there exist unique D, R with

A = D·B + R ,   deg R < deg B

(D = quotient, R = remainder). Write A ≡ B (mod C) when remainders match.

Useful facts:

• A ≡ 0 (mod B) ⇔ B divides A
• A(x) ≡ A(r) (mod x−r) ⇒ A(r)=0 ⇔ x−r divides A
• Mod xᵏ: truncate to degree < k

FPS don’t use Euclidean division the same way; instead invert when a₀≠0, then A/B = A·B⁻¹ (mod xⁿ).

Inverse series — Newton / Hensel

Sieveking–Kung: start B₀ = a₀⁻¹, then lift

B ← B (2 − A B)  (mod x^{2ᵏ})

until you have n coefficients. Cost T(n)=T(n/2)+O(n log n)=O(n log n) with FFT mul.

Same recurrence appears as Newton’s method for F(Q)=0:

Q ← Q − F(Q)/F'(Q)  (mod x^{2ᵏ})

Special cases (all O(n log n) with FFT, needing sensible Q(0)):

Goal	Idea
A⁻¹	F(Q)=Q⁻¹−A → formula above
ln A	(ln A)' = A'/A then integrate
exp P	solve ln Q = P via Newton
Aᵏ	exp(k ln A) (or factor α xᵗ out first)

Graeffe / D&C inverse: use A(x)A(−x)=T(x²) to cut the problem in half — also O(n log n).

Euclidean division via reversal

With n=deg A ≥ m=deg B, reverse coeffs Aᴿ(x)=xⁿ A(x⁻¹), etc. Then

Dᴿ ≡ Aᴿ (Bᴿ)⁻¹  (mod x^{n−m+1})

recover D, then R = A − B D. Toeplitz structure ↔ series inverse.

Evaluation and interpolation

Task	Method	Time
Powers of z	Chirp-z / Bluestein (one convolution)	O(n log n)
Arbitrary xᵢ	Segment tree of Π(x−xⱼ) + reduce	O(n log² n)
Interpolate (xᵢ,yᵢ)	Lagrange via P' + tree merge	O(n log² n)

GCD and resultants

Polynomial Euclidean algorithm: O(nm).

Resultant ℛ(A,B) vanishes iff A,B share a root (over an algebraic closure). Computable alongside Euclid in O(nm); half-GCD brings GCD/resultant to O(n log² n).

🧪 Convolution + Newton inverse (mod x⁸)

Check: polynomials & FPS

Quiz

Polynomials and series

1 / 4

Coefficient cₖ of AB is…

Pick an answer to see if you are right.

Practice drills

Activity: Convolution

First line: n m. Second: n ints a[0..n). Third: m ints b[0..m). Print n+m−1 coeffs of a*b.

Contest problems

From CP-Algorithms:

• CodeChef — RNG
• Codeforces — Basis Change
• Codeforces — Permutant
• Codeforces — Medium Hadron Collider

(Search the titles on CF/CodeChef if the round numbers move.)

Cheat sheet

Op	Takeaway
Mul	Convolution; FFT O(n log n)
Inv	Newton B(2−AB); need a₀≠0
Div	Reverse + inv, or Euclid
ln / exp / pow	Newton + mul/inv
Eval many	Product tree O(n log² n)
Interp	Lagrange + tree O(n log² n)
Chirp-z	Eval at z^k via one conv
GCD / ℛ	Euclid O(nm); half-GCD faster