Tags
7 posts
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).
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.
Greedy optimality for divisibility-chain coin systems, DP over the maximum denomination, and a sieve-style transition by adding one larger coin.
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.
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.
Hockey Stick identity, addition/multiplication principles, binomial identities, example problems: bitonic sequences, multiset permutations, multi-layer coloring DP, CCPC Subpermutation.
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.
