Formal Power Series

An infinite series $A(x)={\sum }_{n\ge 0}{a}_n{x}^n$, manipulated modulo $x^n$ — we only ever compute the first $n$ coefficients. All the operations below are $O(n\log n)$ via NTT and Newton’s method.

Newton’s method — the master technique

To solve $F(B)=0$ for a series $B$, iterate

$B_{2k}=B_k-\frac{F(B_k)}{F^{\prime }(B_k)}(\mathrm{mod}{x}^{2k}),$

doubling the number of correct coefficients each step. Since the cost is dominated by the last doubling,

$T(n)=T(n/2)+O(n\log n)=O(n\log n).$

Every operation below is an instance of this. Recognising that is worth more than memorising the formulas.

The operations

Inverse — $AB\equiv 1$

$B_{2k}=B_k(2-A{B}_k)(\mathrm{mod}{x}^{2k}).$

Poly inverse(const Poly& a, int n) {
    Poly b{ powmod(a[0], MOD - 2, MOD) };                  // requires a[0] != 0
    for (int k = 1; k < n; k <<= 1) {
        Poly t = mulTrunc(a, b, 2 * k);
        for (auto& x : t) x = MOD - x;
        t[0] = (t[0] + 2) % MOD;
        b = mulTrunc(b, t, 2 * k);
    }
    b.resize(n);
    return b;
}

Requires $a_0\ne 0$.

Logarithm — requires $a_0=1$

$\log A=\int \frac{A^{\prime }}{A}.$

Poly logSeries(const Poly& a, int n) {
    return integrate(mulTrunc(derivative(a), inverse(a, n), n - 1), n);
}

Exponential — requires $a_0=0$

$B_{2k}=B_k(1-\log B_k+A)(\mathrm{mod}{x}^{2k}).$

The most expensive of the basic operations, but still $O(n\log n)$.

Square root — requires $a_0$ to be a quadratic residue

$B_{2k}=\frac{1}{2}\left(B_k+\frac{A}{B_k}\right).$

Power

$A^k=\exp (k\log A)$

for $a_0=1$. Otherwise factor out $x^m{a}_0$: $A=a_0{x}^m(1+\dots )$, raise the normalised part, and multiply back — being careful that $mk<n$ or the result is zero.

$O(n\log n)$ regardless of how large $k$ is (only $k\mathrm{mod}p$ matters in the exponent).

The EGF dictionary

Working with exponential generating functions ($\sum a_n\frac{x^n}{n!}$), these operations have direct combinatorial meanings:

Series operation	Combinatorial meaning
$A\cdot B$	split a labelled set into two parts
$\exp (A)$	a set of $A$-structures (the exponential formula)
$\frac{1}{1-A}$	a sequence of $A$-structures
$\log$	invert $\exp$ — recover connected structures from all structures
$A^{\prime }$	mark and remove one element
$\int A$	add a distinguished element

The exponential formula — if $C$ is the EGF for connected structures, then $e^C$ is the EGF for all structures — converts “count connected graphs” into “count all graphs, then take a log”. That is a genuinely powerful move.

The standard series

$\frac{1}{1-x}=\sum x^n,e^x=\sum \frac{x^n}{n!},\ln \frac{1}{1-x}={\sum }_{n\ge 1}\frac{x^n}{n}$

$(1+x{)}^{\alpha }=\sum (\genfrac{}{}{0ex}{}{\alpha }{n})x^n,\frac{1}{(1-x{)}^k}=\sum (\genfrac{}{}{0ex}{}{n+k-1}{k-1})x^n$

$\frac{1-\sqrt{1-4x}}{2x}=\sum C_n{x}^n\text{(Catalan)},\frac{x}{1-x-x^2}=\sum F_n{x}^n$

What it is for

Problem	Method
Count objects with a recursive structure	solve the functional equation, extract coefficients
Count set partitions, permutations by cycles	EGF + exp/log
Count labelled connected graphs	$\log$ of the all-graphs EGF
Solve a linear recurrence	a rational GF; use Bostan-Mori
Sum ${\sum }_k\left(\genfrac{}{}{0ex}{}{n}{k}\right)f(k)$	binomial transform = multiply by $e^x$
Convert between OGF and EGF	multiply/divide by $n!$
Count with a “at least one of each” constraint	inclusion-exclusion, or $(e^x-1{)}^k$
Partitions of an integer	$\prod \frac{1}{1-x^k}$

Practical notes

• Everything is modulo $x^n$ — truncate aggressively; carrying extra coefficients is pure waste.
• Precompute factorials and inverse factorials for EGF conversions.
• The base cases matter: inverse needs $a_0\ne 0$, log needs $a_0=1$, exp needs $a_0=0$, sqrt needs $a_0$ to be a QR. Normalise first.
• Use 998244353 so NTT applies directly.
• Truncated multiplication (mulTrunc) that discards coefficients beyond the needed length saves roughly half the work.

See also: Generating Functions · FFT and NTT · Newton’s Method