Common Formulae & Conclusions
A compact toolkit of geometric sums, floor-sum transformations, XOR facts, Fibonacci identities, and perfect-square patterns.
Algorithms
Competitive-programming notes: combinatorics, number theory, and matrix methods.
Combinatorics 13
计数中常用的结论
常见计数结论、Lucas 定理、不定方程解计数、平面分拆、DAG 路径计数、多项式平移、XOR 均匀性与若干竞赛常用结论。
Permutations and Combinations
Hockey Stick identity, addition/multiplication principles, binomial identities, example problems: bitonic sequences, multiset permutations, multi-layer coloring DP, CCPC Subpermutation.
Inclusion-Exclusion, Bounded Diophantine Equations, and Derangements
Inclusion-exclusion in set and operator form, equal-count subproblems, bounded Diophantine counting, derangements, Stirling numbers, and selected contest problems.
容斥原理、不定方程、错排
容斥原理的集合与算子形式、有上下界不定方程计数（前缀和DP与分治NTT）、错排公式与第二类斯特林数。
Difference (Correlation) Convolution
Cross-correlation via ordinary convolution: reverse-A and reverse-B extraction methods, derivation, and Ring Trick II (cyclic shift score maximisation via difference convolution).
Cyclic Convolution
Cyclic convolution definition, FFT/NTT implementation for n=2^k, zero-padding, why n must be a power of two, and the fold-back technique for arbitrary n.
FFT and Lagrange Interpolation
Polynomial representations, FFT/DFT over complex numbers, Triple Sums, Fuzzy Search (difference convolution), FFT template, Lagrange interpolation (O(n²) and O(n) equidistant), sum of k-th powers, Assigning Prizes polynomial DP.
Primitive Roots, Discrete Logarithm, NTT, Divide-and-Conquer NTT
Order and primitive roots (Euler’s theorem, BSGS, exBSGS), discrete index as logarithm analogue, SGU 261 Discrete Roots, NTT theory and templates, divide-and-conquer NTT (product tree), Wannafly D team selection, Nowcoder 50F …
Ordinary Generating Functions
Formal power series basics, ordinary generating functions, inversion identities, generalized binomial expansions, bounded counting examples, and recurrence-to-closed-form examples such as Fibonacci and Catalan.
More Operations on Formal Power Series
Newton iteration for polynomial inverse and square root, derivative/integral/composition of formal power series, logarithm and exponential of series, and worked examples including CF438E and a bad-modulus complete-knapsack …
Diophantine Equations
Stars and bars, bounded Diophantine equations via inclusion-exclusion, prefix-sum DP, D&C NTT, equal-cap formula, and a full worked example on CF 2127F.
Order Theory — Chromatic Polynomials, Chordal Graphs, Order Polynomials, Dilworth & Hall
Chromatic polynomial, chordal/interval graphs, PEO product formula, order polynomials (chain/antichain/tree/DAG/divisor lattice), MacMahon formula, Dilworth, Mirsky, Hall’s marriage theorem, Erdős–Szekeres, missile interception.
Number Theory 10
Common Formulae — Legendre's Formula & Divisor Convolutions
Legendre’s formula, divisor and multiple convolutions in O(n log n), offline-difference batch processing for H(n)=Σf(d)g(⌊n/d⌋).
Elementary Number Theory — GCD, LCM, Euler, CRT
GCD/LCM properties, Bézout/Frobenius, Euler’s theorem with power-tower reduction and φ-chain technique, congruence system merging via exGCD, CRT, and n! prime factorisation via Legendre’s formula.
Divisibility Blocking (Floor-Division Decomposition)
Divisibility blocking for O(sqrt n) floor-sum evaluation: lemma, single-variable loop, O(1) interval sum requirements, two-variable min-trick, multi-variable pseudocode, and ceiling-division blocking.
Möbius Practice — LCM Sums, Divisor-Count, Omega Numbers
Practice problems for Möbius inversion: LCMSUM, two-variable lcm sum (O(n^3/4)), FSF’s game with offline difference, divisor-count sum d(ij), Omega Numbers with Dirichlet suffix sum.
Möbius Techniques
Seven core techniques for Möbius inversion problems: loop shortening, gcd indicator expansion, coprimality reduction, Dirichlet convolution via T=dk, divisor symmetry, diagonal symmetry, and value-domain cnt[] tricks.
Multiplicative Functions, Möbius Inversion & Dirichlet Convolution
Multiplicative functions, single-point and linear-sieve evaluation; Möbius function, both forms of Möbius inversion with full derivations and examples; Dirichlet convolution, key identities, Du Jiao sieve; generalized Möbius …
From Eratosthenes to Möbius Inclusion-Exclusion
Eratosthenes sieve for μ; g/f/h framework; Conclusions 1 and 2 with derivations and tables; GCD table intuition; CF 803F Coprime Subsequences with bottom-up and Möbius approaches.
Sieve Problems — Coin System DP via Sieve
Greedy optimality for divisibility-chain coin systems, DP over the maximum denomination, and a sieve-style transition by adding one larger coin.
Min_25 Sieve and Du Jiao Sieve
Min_25 sieve: theory, two complete examples, Lagrange interpolation for power sums. Du Jiao sieve: template, P3768, GCD sum, LCM sum.
Primality, Factorisation & Residues (Miller-Rabin, Pollard Rho, Tonelli-Shanks)
Miller-Rabin primality test, Pollard Rho factorisation, Tonelli-Shanks for quadratic residues, cubic residues via F_p[t]/(t^3-a), quartic residues by double square root, and general k-th residues via primitive root + BSGS, plus …
Matrix 4
Matrix Fast Power — Linear Recurrence, DP Semirings & Kitamasa
Matrix fast power for linear recurrences (4 patterns), 4 semiring templates (count/bool/min-plus/max-plus), matrix+segment tree for range-add Fibonacci queries, Kitamasa O(k²logn) and NTT O(k log²k logn).
Gaussian Elimination — Real, Mod, Mod-2, Incremental
Gauss elimination: real/mod/mod-2 templates (solve, det, inv, rank); incremental online RREF; Extended Lights Out, CF 1344F abstract GF(2) modelling, 2024 ICPC Kunming interactive tree queries.
Linear Basis (XOR Basis) & Simplex Method
XOR linear basis: full template with kth, range basis, normalisation; Nowcoder median example; CF 1101G prefix-XOR rank; gym 104768 C XOR-divisibility; Simplex LP solver.
Matrix Problems — Fibonacci Subarray Sums, Gaussian Elimination & Expected Value
Hard matrix problems: Fibonacci squared subarray sum with segment-tree 4-tuple and companion matrix; cycle-decomposition partition state space for random-swap sorting, first-step analysis, and Gaussian elimination.