v. Power Series Operations

Polynomial arithmetic and formal power series modulo $x^n$: inverse, logarithm, exponential, square root, power, division with remainder, all $O(n\log n)$ by Newton’s method on top of polyMul from NTT (modulus 998244353). This block is the second half of the chapter’s shared core; evaluation, composition, recurrences and counting build on it.

Operation	Naive	Fast	Method
add, scalar multiply, derivative, integral	$O(n)$	$O(n)$	coefficientwise
multiply	$O(n^2)$	$O(n\log n)$	NTT
divide by $x-a$; evaluate at one point	$O(n)$	$O(n)$	synthetic division = Horner
inverse, log, exp, sqrt, power mod $x^n$	$O(n^2)$	$O(n\log n)$	Newton iteration
divide with remainder	$O(n^2)$	$O(n\log n)$	reversal + inverse
$\prod (x-r_i)$	$O(n^2)$	$O(n{\log }^{2}n)$	divide and conquer
evaluate at / interpolate from $n$ points	$O(n^2)$	$O(n{\log }^{2}n)$	product tree (Evaluation and Interpolation)
gcd	$O(n^2)$	$O(n{\log }^{2}n)$	half-gcd (GCD and Resultant)
composition $A(B(x))$	$O(n^2)$	$O(n{\log }^{2}n)$	Kinoshita–Li / Brent–Kung (Composition)
shift $A(x+c)$	$O(n^2)$	$O(n\log n)$	one convolution with factorials

Newton’s method is the master technique: to solve $F(B)=0$, 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; the last doubling dominates, $T(n)=T(n/2)+O(n\log n)=O(n\log n)$. Every operation below is an instance.

Series	Newton step / formula	Requirement
$B=A^{-1}$	$B\leftarrow B(2-AB)$	$a_0\ne 0$
$\log A$	$\int \frac{A^{\prime }}{A}$	$a_0=1$
$\exp A$	$B\leftarrow B(1-\log B+A)$	$a_0=0$
$\sqrt{A}$	$B\leftarrow \frac{1}{2}(B+A/B)$	lowest non-zero term $a_t{x}^t$ with $t$ even and $a_t$ a quadratic residue
$A^k$, any $k\le 10^{18}$	$a_t^k{x}^{tk}\exp (k\log (A/(a_t{x}^t)))$	only $k\mathrm{mod}p$ enters the exponential; zero if $tk\ge n$
$A=QB+R$	$\mathrm{rev}(Q)=\mathrm{rev}(A)\mathrm{rev}(B{)}^{-1}\mathrm{mod}{x}^{\mathrm{deg}A-\mathrm{deg}B+1}$	$\mathrm{lc}(B)\ne 0$

Poly polyTrunc(Poly a, int n) { a.resize(n); return a; }
Poly mulTrunc(const Poly& a, const Poly& b, int n) { Poly c = polyMul(polyTrunc(a, min(sz(a), n)), polyTrunc(b, min(sz(b), n))); c.resize(n); return c; }
Poly derivative(const Poly& a) { Poly r(max(sz(a) - 1, 0)); for (int i = 1; i < sz(a); i++) r[i - 1] = a[i] * mint(i); return r; }
Poly integrate(const Poly& a) {
    int n = sz(a); Poly r(n + 1, 0); vector<mint> iv(n + 2, 1);
    for (int i = 2; i <= n; i++) iv[i] = -mint(998244353 / i) * iv[998244353 % i];   // 1/i, linear
    for (int i = 0; i < n; i++) r[i + 1] = a[i] * iv[i + 1];
    return r;
}
Poly polyInv(const Poly& a, int n) {                       // a[0] != 0
    Poly b{a[0].inv()};
    for (int k = 1; k < n; k *= 2) {
        Poly t = mulTrunc(a, b, 2 * k); for (auto& x : t) x = -x; t[0] += 2;
        b = mulTrunc(b, t, 2 * k);
    }
    b.resize(n); return b;
}
Poly polyLog(const Poly& a, int n) {                       // a[0] == 1
    if (n == 0) return {};
    Poly r = integrate(mulTrunc(derivative(a), polyInv(a, n), n - 1)); r.resize(n); return r;
}
Poly polyExp(const Poly& a, int n) {                       // a[0] == 0
    Poly b{1};
    for (int k = 1; k < n; k *= 2) {
        Poly t = polyLog(b, 2 * k); for (int i = 0; i < 2 * k; i++) t[i] = (i < sz(a) ? a[i] : mint(0)) - t[i]; t[0] += 1;
        b = mulTrunc(b, t, 2 * k);
    }
    b.resize(n); return b;
}
bool sqrtMint(mint a, mint& r) {                           // Tonelli-Shanks for 998244353
    const ll p = 998244353;
    if (a == mint(0)) { r = 0; return true; }
    if (a.pow((p - 1) / 2) != mint(1)) return false;
    ll q = p - 1; int s = 0; while (q % 2 == 0) q /= 2, s++;
    mint c = mint(3).pow(q), t = a.pow(q), x = a.pow((q + 1) / 2); int m = s;   // 3 is a non-residue
    while (t != mint(1)) {
        int i = 0; mint tt = t; while (tt != mint(1)) tt *= tt, i++;
        mint b = c; for (int j = 0; j < m - i - 1; j++) b *= b;
        x *= b; c = b * b; t *= c; m = i;
    }
    r = x; return true;
}
Poly polySqrt(const Poly& a, int n) {                       // {} if no square root exists
    int t = 0; while (t < sz(a) && a[t] == mint(0)) t++;
    if (t == sz(a) || t >= n) return Poly(n, 0);            // B = 0 works
    if (t % 2) return {};
    Poly b(a.begin() + t, a.end()); mint s0; if (!sqrtMint(b[0], s0)) return {};
    int m = n - t / 2; Poly r{s0}; mint inv2 = mint(2).inv();
    for (int k = 1; k < m; k *= 2) {
        Poly q = mulTrunc(b, polyInv(r, 2 * k), 2 * k); r.resize(2 * k);
        for (int i = 0; i < 2 * k; i++) r[i] = (r[i] + q[i]) * inv2;
    }
    r.resize(m); Poly res(n, 0); for (int i = 0; i < m; i++) res[i + t / 2] = r[i];
    return res;
}
Poly polyPow(const Poly& a, ll k, int n) {                 // a^k mod x^n, k >= 0 (huge allowed)
    if (k == 0) { Poly r(n, 0); if (n) r[0] = 1; return r; }
    int t = 0; while (t < sz(a) && a[t] == mint(0)) t++;
    if (t == sz(a) || (i128)t * k >= n) return Poly(n, 0);
    int m = n - t * k; mint c = a[t], ci = c.inv();
    Poly b(min(sz(a) - t, m)); for (int i = 0; i < sz(b); i++) b[i] = a[i + t] * ci;
    Poly l = polyLog(b, m); for (auto& x : l) x *= mint(k % 998244353);
    Poly e = polyExp(l, m); mint ck = c.pow(k);
    Poly res(n, 0); for (int i = 0; i < m; i++) res[i + t * k] = e[i] * ck;
    return res;
}
pair<Poly, Poly> polyDivMod(Poly a, Poly b) {               // a = q b + r, deg r < deg b; b non-zero
    while (!b.empty() && b.back() == mint(0)) b.pop_back();
    while (!a.empty() && a.back() == mint(0)) a.pop_back();
    int d = sz(a) - sz(b);
    if (d < 0) return {{}, a};
    Poly ra(a.rbegin(), a.rend()), rb(b.rbegin(), b.rend());
    Poly q = mulTrunc(ra, polyInv(rb, d + 1), d + 1); reverse(all(q));
    Poly qb = polyMul(q, b), r(sz(b) - 1);
    for (int i = 0; i < sz(r); i++) r[i] = a[i] - qb[i];
    while (!r.empty() && r.back() == mint(0)) r.pop_back();
    return {q, r};
}
mint evalPoly(const Poly& a, mint x) { mint r = 0; for (int i = sz(a) - 1; i >= 0; i--) r = r * x + a[i]; return r; }   // Horner
Poly divLinear(Poly p, mint a, mint& rem) {                 // p / (x - a); rem = p(a)
    if (p.empty()) { rem = 0; return {}; }
    for (int i = sz(p) - 2; i >= 0; i--) p[i] += a * p[i + 1];
    rem = p[0]; p.erase(p.begin()); return p;
}
Poly productOfLinear(const vector<mint>& r, int lo, int hi) {   // prod_{lo <= i < hi} (x - r_i), O(n log^2 n)
    if (hi - lo == 0) return {1};
    if (hi - lo == 1) return {-r[lo], 1};
    int mid = (lo + hi) / 2;
    return polyMul(productOfLinear(r, lo, mid), productOfLinear(r, mid, hi));
}

Proof: Newton iteration and each formula

Quadratic convergence. Suppose $F(B)=0$ with $F^{\prime }(B)$ invertible and $B_k\equiv B(\mathrm{mod}{x}^k)$. Taylor expansion gives $0=F(B)=F(B_k)+F^{\prime }(B_k)(B-B_k)+O((B-B_k{)}^2)$, and $(B-B_k{)}^2\equiv 0(\mathrm{mod}{x}^{2k})$, so $B\equiv B_k-F(B_k)/F^{\prime }(B_k)(\mathrm{mod}{x}^{2k})$. Inverse: $F(B)=B^{-1}-A$ gives $B_k-\frac{B_k^{-1}-A}{-B_k^{-2}}=B_k(2-A{B}_k)$; the base $b_0=a_0^{-1}$ needs $a_0\ne 0$. Log: $(\log A{)}^{\prime }=A^{\prime }/A$ and $\log A$ has constant term $\log a_0=0$ for $a_0=1$, so integrate; the integral divides by $\mathrm{1..}n$, fine for $n<p$ (the linear-time inverses use $p=\lfloor p/i\rfloor i+(p\mathrm{mod}i)$). Exp: $F(B)=\log B-A$, $F^{\prime }(B)=1/B$, giving $B_k-B_k(\log B_k-A)=B_k(1-\log B_k+A)$. Sqrt: $F(B)=B^2-A$ gives $B_k-\frac{B_k^2-A}{2B_k}=\frac{1}{2}(B_k+A/B_k)$; a series with lowest term $a_t{x}^t$ has a square root iff $t$ is even and $a_t$ is a square (then $\sqrt{A}=x^{t/2}\sqrt{A/x^t}$), and sqrtMint is Tonelli–Shanks (Modular Square Roots). Power: $A=a_t{x}^{t}B$ with $b_0=1$, so $A^k=a_t^k{x}^{tk}\exp (k\log B)$; the coefficient of $x^m$ in $B^k$ is a polynomial in $k$ of degree $m$ whose denominators divide $m!$ (coefficients of $\left(\genfrac{}{}{0ex}{}{k}{m}\right)$-type terms), so for $m<n<p$ only $k\mathrm{mod}p$ matters, while $a_t^k$ uses the true $k$. Costs: each step does $O(1)$ multiplications of length $2k$ (exp also a log), so the totals are $O(n\log n)$.

Division. For $A=QB+R$ with $\mathrm{deg}A=a$, $\mathrm{deg}B=b$, reversing ($\mathrm{rev}P(x)=x^{\mathrm{deg}P}P(1/x)$) gives $\mathrm{rev}A=\mathrm{rev}Q\mathrm{rev}B+x^{a-b+1}(\dots )$, so $\mathrm{rev}Q\equiv \mathrm{rev}A(\mathrm{rev}B{)}^{-1}(\mathrm{mod}{x}^{a-b+1})$ ($\mathrm{rev}B$ has constant term $\mathrm{lc}B\ne 0$), and $\mathrm{deg}Q=a-b$ makes this determine $Q$; then $R=A-QB$ has degree $<b$. Synthetic division / Horner: $p(x)=(x-a)q(x)+p(a)$, and matching coefficients from the top gives $q_{i-1}=p_i+a{q}_i$, the same recurrence as Horner’s evaluation. Product tree: $T(n)=2T(n/2)+O(n\log n)=O(n{\log }^{2}n)$. All functions were checked against $O(n^2)$ series arithmetic (and $B^2=A$, $\exp \log A=A$, $A\cdot A^{-1}=1$, long division) for random inputs.

Root / factor task	Method
rational roots over $\mathbb{Z}$	$p\mid a_0$, $q\mid a_n$ (rational root theorem)
roots modulo a prime	$\gcd (f,x^p-x)$, then Cantor–Zassenhaus (Factorization)
real roots	Sturm sequences + bisection (Roots and Integration)
all complex roots	Durand–Kerner, or companion-matrix eigenvalues
squarefree part	$f/\gcd (f,f^{\prime })$
factorisation over ${\mathbb{F}}_p$ / $\mathbb{Z}$	SFF $\to$ DDF $\to$ EDF / mod $p$, Hensel lifting, recombination

Identities: $\mathrm{deg}(AB)=\mathrm{deg}A+\mathrm{deg}B$ (over a domain), $(AB{)}^{\prime }=A^{\prime }B+A{B}^{\prime }$, the remainder theorem $A\mathrm{mod}(x-a)=A(a)$, and Vieta: the coefficients of $\prod (x-r_i)$ are $\pm$ the elementary symmetric polynomials of the $r_i$. Representation: vector<mint>, index = degree; trim trailing zeros where degrees matter (division, gcd).

EGFs and the standard series

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

$\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.$

Problem	Method
objects with a recursive structure	solve the functional equation, extract coefficients (Newton or online convolution)
set partitions, permutations by cycles	EGF + $\exp$ / $\log$
labelled connected graphs	$\log$ of $\sum 2^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}\frac{x^n}{n!}$ (Graph Counting)
linear recurrence	rational GF, Bostan–Mori (Linear Recurrences)
${\sum }_k\left(\genfrac{}{}{0ex}{}{n}{k}\right)f(k)$	binomial transform = multiply the EGF by $e^x$
“at least one of each”	inclusion–exclusion, or $(e^x-1{)}^k$
integer partitions	$\prod \frac{1}{1-x^k}$ via $\exp {\sum }_k\frac{\sigma (k)}{k}{x}^k$ (Counting with Power Series)

The exponential formula ($C$ = connected structures, $e^C$ = all structures) turns “count connected graphs” into “count all graphs, take a log”. Practical notes: everything is modulo $x^n$ (truncate aggressively; mulTrunc saves about half); precompute factorials for OGF/EGF conversions; normalise before calling (inv needs $a_0\ne 0$, log $a_0=1$, exp $a_0=0$); use 998244353 so NTT applies directly.

Related notes

• NTT (polyMul)
• Generating Functions
• Online Convolution (when the series is defined by its own prefix)