Skip to content

Polynomial / Formal Power Series Ladder

This ladder is for the narrow contest route where:

  • coefficients live modulo one NTT-friendly prime
  • the statement wants truncated FPS algebra
  • and plain convolution is only the starting layer

Who This Is For

Use this lane if:

  • FFT And NTT already feels stable
  • you can trust one exact NTT convolution
  • you now need inverse / log / exp / pow style series operations

Warm-Up

Target skill:

  • trust the multiplication layer before trying Newton-style FPS algebra

Core

Target skill:

  • work modulo x^n
  • spot the condition a_0 != 0
  • use Newton doubling with NTT-backed multiplication

Stretch

Target skill:

  • distinguish "same FPS family" from "same exact starter contract"

Retrieval Layer

Repo Anchors And Compare Points

The cleanest in-repo loop here is:

  1. trust the convolution layer in FFT And NTT
  2. learn the inverse contract from Polynomial / Formal Power Series
  3. verify the route on Inv of Formal Power Series

Exit Criteria

You are ready to move on when:

  • you can say why a_0 != 0 is necessary
  • you know the Newton step B <- B(2 - AB)
  • you remember to truncate every intermediate product
  • you can explain why this lane is more than one plain convolution

External Practice