Advanced Counting Patterns

July 2026 · 45 min read

The Art of Hard Counting

Every hard combinatorics problem on Codeforces or ICPC boils down to choosing the right counting paradigm. The difference between a 30–minute solve and a 3–hour dead end is almost always recognising which paradigm fits. In this final post we consolidate everything from the series into a unified toolkit.

There are six master strategies for hard counting:

1. Bijection — map the hard set onto an easy set of the same size.
2. Complementary counting — count the complement and subtract from the universe.
3. Inclusion–exclusion — systematically correct for over-counting among overlapping forbidden conditions.
4. Double counting — count the same quantity two ways, then equate.
5. Generating functions & convolution — encode sequences as polynomials, then multiply.
6. Algebraic manipulation — factor, telescope, or transform a sum into closed form.

The rest of this post devotes a full section to each major pattern, with complete worked examples and C++ implementations ready for contest use.

Pattern: Inclusion–Exclusion on Forbidden Positions

The classic derangement formula D_n = n! Σ_k=0ⁿ (−1)^k/k! is the simplest instance of a much more general technique: counting permutations that avoid a prescribed set of forbidden (position, value) pairs.

General setup

Let F ⊆ {1,…,n}×{1,…,n} be a set of forbidden pairs. We want to count permutations σ such that (i, σ(i)) ∉ F for all i. Equivalently, we want the permanent of the 0/1 matrix A where A[i][j] = 1 iff (i,j) ∉ F.

Define S_k as the number of ways to choose k forbidden pairs that can simultaneously be satisfied (i.e. no two share a row or column), times (n−k)! for the remaining positions. Then by inclusion–exclusion:

answer  =  Σ_k=0ⁿ (−1)^k · r_k · (n−k)!

where r_k is the number of ways to place k non-attacking rooks on the forbidden squares of an n×n board (the rook polynomial).

Derangements as a special case

For derangements, F = {(1,1), (2,2), …, (n,n)}. The forbidden squares lie on the main diagonal. Choosing k of them gives C(n,k) ways, and the remaining positions contribute (n−k)!. So:

D_n = Σ_k=0ⁿ (−1)^k C(n,k) (n−k)! = n! Σ_k=0ⁿ (−1)^k/k!

Worked problem: partial derangements

Problem. Given n and a subset S ⊆ {1,…,n}, count permutations σ such that σ(i) ≠ i for all i ∈ S (positions in S must not be fixed, but positions outside S may be fixed). Answer modulo 998244353.

Let m = |S|. The forbidden set is F = {(i,i) : i ∈ S}. Since the forbidden squares are all on the diagonal and in distinct rows/columns, choosing k of them can be done in C(m,k) ways. The remaining n−k elements can be permuted freely:

answer = Σ_k=0^m (−1)^k C(m,k) (n−k)!

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;

long long power(long long a, long long b, long long mod) {
    long long res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

long long inv(long long a, long long mod) {
    return power(a, mod - 2, mod);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    // m = |S|, the number of positions that must not be fixed

    // Precompute factorials and inverse factorials
    vector<long long> fact(n + 1), ifact(n + 1);
    fact[0] = 1;
    for (int i = 1; i <= n; i++)
        fact[i] = fact[i - 1] * i % MOD;
    ifact[n] = inv(fact[n], MOD);
    for (int i = n - 1; i >= 0; i--)
        ifact[i] = ifact[i + 1] * (i + 1) % MOD;

    auto C = [&](int a, int b) -> long long {
        if (b < 0 || b > a) return 0;
        return fact[a] % MOD * ifact[b] % MOD * ifact[a - b] % MOD;
    };

    long long ans = 0;
    for (int k = 0; k <= m; k++) {
        long long term = C(m, k) % MOD * fact[n - k] % MOD;
        if (k % 2 == 0)
            ans = (ans + term) % MOD;
        else
            ans = (ans - term + MOD) % MOD;
    }

    cout << ans << "\n";
    return 0;
}

Pattern: Counting via Bijection

A bijection is a one-to-one correspondence between two sets. If you can exhibit a bijection between a hard-to-count set A and an easy-to-count set B, then |A| = |B| and you’re done. Many of the most elegant results in combinatorics arise this way.

The Catalan universe

The Catalan number C_n = C(2n,n)/(n+1) counts an astonishing number of different combinatorial objects. Here are the most important ones for competitive programming, all bijectively equivalent:

The cycle lemma (Dvoretzky & Motzkin)

One of the most powerful bijection tools. Given a sequence of n values of +1 and m values of −1 with n ≥ m, exactly n−m+1 of the n+m cyclic rotations have all prefix sums positive (counting from position 0 with the convention that we look at all partial sums). More precisely:

(Cycle lemma)  Exactly 1/(n+m) · C(n+m, n) sequences of n copies of +1 and m copies of −1 have all prefix sums > 0 (when n > m).

Setting n = m+1 gives exactly C_m = 1/(m+1) · C(2m+1, m) — wait, that’s not quite right for Dyck paths. For Dyck paths (steps +1 and −1, n of each, prefix sums ≥ 0), the reflection argument yields:

C_n = C(2n,n) − C(2n, n−1) = C(2n,n)/(n+1)

Bertrand ballot problem

Problem. In an election, candidate A receives a votes and candidate B receives b votes with a > b. If votes are counted in random order, what is the probability that A is strictly ahead of B throughout the counting?

Answer (by reflection/cycle lemma): (a − b) / (a + b).

This is proven by a bijection: sequences where A is not always ahead are in bijection with certain reflected paths, and the count of “good” sequences works out to (a−b)/(a+b) · C(a+b, a).

Pattern: Contribution Counting

Instead of directly counting the number of structures, compute the answer by summing the contribution of each element (edge, vertex, pair, etc.) across all structures. This is the counting analogue of linearity of expectation.

Core identity

If you want Σ_{S ∈ F} |S| where F is a family of combinatorial structures, then:

Σ_{S ∈ F} |S|  =  Σ_{x ∈ U} (number of S ∈ F containing x)

This trivial identity is devastatingly powerful because the right side often simplifies dramatically.

Worked example 1: sum of inversions

Problem. Over all n! permutations of {1,…,n}, what is the total number of inversions?

Solution. For each pair (i,j) with i < j, the pair forms an inversion in exactly half the permutations (by symmetry: σ(i) > σ(j) with probability 1/2). So the total is:

C(n,2) · n!/2 = n(n−1)/2 · n!/2 = n! n(n−1)/4

Worked example 2: sum of edge-weights in spanning trees

Problem. Given a complete graph K_n with weighted edges, compute the sum of weights over all labelled spanning trees. (Equivalently: for each edge e, multiply w(e) by the number of spanning trees containing e, and sum.)

Solution by contribution. By Cayley’s formula, K_n has nⁿ⁻² spanning trees. Each tree has n−1 edges. Over all trees, the total number of edge-slots is (n−1) nⁿ⁻². By symmetry in K_n, each of the C(n,2) edges appears in the same number of trees. So each edge appears in:

(n−1) nⁿ⁻² / C(n,2) = 2 nⁿ⁻³

spanning trees. The total weight sum is then Σ_e w(e) · 2nⁿ⁻³ = 2nⁿ⁻³ · W, where W is the total edge weight.

Worked example 3: sum of GCDs

Problem. Compute Σ_i=1ⁿ Σ_j=1ⁿ gcd(i,j) mod 998244353.

Solution by contribution. For each d from 1 to n, count the number of pairs (i,j) with gcd(i,j) = d. This equals the number of pairs (i’,j’) with 1 ≤ i’,j’ ≤ ⌊n/d⌋ and gcd(i’,j’) = 1. Using Möbius inversion, this is Σ_k=1^⌊n/d⌋ μ(k) ⌊n/(dk)⌋². The total answer becomes:

Σ_d=1ⁿ d · Σ_k=1^⌊n/d⌋ μ(k) ⌊n/(dk)⌋²

Substituting T = dk and swapping order of summation allows O(n sqrt(n)) or even O(n) computation using the Euler totient function:

answer = Σ_T=1ⁿ ⌊n/T⌋² · Σ_d|T d μ(T/d) = Σ_T=1ⁿ ⌊n/T⌋² · φ(T)

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;

int main() {
    int n;
    cin >> n;

    // Compute Euler's totient for 1..n via sieve
    vector<long long> phi(n + 1);
    iota(phi.begin(), phi.end(), 0); // phi[i] = i initially
    for (int i = 2; i <= n; i++) {
        if (phi[i] == i) { // i is prime
            for (int j = i; j <= n; j += i) {
                phi[j] -= phi[j] / i;
            }
        }
    }

    // answer = sum_{T=1}^{n} floor(n/T)^2 * phi(T)
    // Optimise with number-theoretic block summation
    long long ans = 0;
    for (int l = 1, r; l <= n; l = r + 1) {
        long long q = n / l;
        r = n / q;
        // Sum phi[l..r]
        long long phiSum = 0;
        for (int t = l; t <= r; t++)
            phiSum = (phiSum + phi[t]) % MOD;
        ans = (ans + q % MOD * (q % MOD) % MOD * phiSum) % MOD;
    }

    cout << ans << "\n";
    return 0;
}

Pattern: Convolution and NTT

Many counting problems reduce to computing the convolution of two sequences: given a[0..n] and b[0..m], compute c[k] = Σ_i+j=k a[i]·b[j]. Naïvely this is O(nm), but the Number Theoretic Transform (NTT) does it in O((n+m) log(n+m)) when working modulo a prime p with a suitable primitive root.

When the answer is a convolution

• Counting partitions: the number of ways to partition n into parts of sizes s₁, s₂, … is the coefficient of xⁿ in Π_i 1/(1−x^s_i). Euler’s product formula gives the generating function for unrestricted partitions.
• Subset sum counting: how many subsets of a multiset sum to exactly k? This is a repeated convolution of small polynomials.
• Distributing items into bins: if f(x) is the GF for one bin and there are k bins, the answer is [xⁿ] f(x)^k, computable by repeated squaring with NTT.

Subset convolution

Given f and g defined on subsets of {1,…,n} (indexed by bitmasks), the subset convolution is:

(f ∗ g)(S) = Σ_{T ⊆ S} f(T) · g(S \ T)

This can be computed in O(2ⁿ n²) by “ranking” (stratifying by popcount) and applying the Möbius/zeta transforms on each rank. This is crucial for problems like “count ways to partition a set into k groups satisfying certain properties.”

C++ NTT template

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int g_root = 3; // primitive root of MOD

long long power(long long a, long long b, long long mod) {
    long long res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void ntt(vector<long long>& a, bool inverse) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }
    for (int len = 2; len <= n; len <<= 1) {
        long long w = inverse
            ? power(g_root, MOD - 1 - (MOD - 1) / len, MOD)
            : power(g_root, (MOD - 1) / len, MOD);
        for (int i = 0; i < n; i += len) {
            long long wn = 1;
            for (int j = 0; j < len / 2; j++) {
                long long u = a[i + j];
                long long v = a[i + j + len / 2] * wn % MOD;
                a[i + j] = (u + v) % MOD;
                a[i + j + len / 2] = (u - v + MOD) % MOD;
                wn = wn * w % MOD;
            }
        }
    }
    if (inverse) {
        long long n_inv = power(n, MOD - 2, MOD);
        for (auto& x : a) x = x * n_inv % MOD;
    }
}

vector<long long> multiply(vector<long long> a, vector<long long> b) {
    int result_size = a.size() + b.size() - 1;
    int n = 1;
    while (n < result_size) n <<= 1;
    a.resize(n); b.resize(n);
    ntt(a, false); ntt(b, false);
    for (int i = 0; i < n; i++)
        a[i] = a[i] * b[i] % MOD;
    ntt(a, true);
    a.resize(result_size);
    return a;
}

Pattern: Broken Profile DP

Broken profile DP (also called plug DP or profile dynamic programming) is a bitmask DP technique for counting configurations on a grid where each cell interacts with its neighbours. The “profile” is a bitmask encoding the state of the boundary between processed and unprocessed cells.

Setup

Consider an n × m grid (with m small, say m ≤ 20). Process cells left to right, top to bottom. At each step the “broken profile” is a bitmask of m bits describing which cells in the current row boundary are “occupied” or “connected” to something above.

Classic application: domino tilings

Problem. Count the number of ways to tile an n×m grid with 1×2 dominoes.

State: dp[col][mask], where mask is an m-bit integer. Bit j = 1 means column j in the current row is already covered by the top half of a vertical domino placed in the previous row.

Transitions: for each cell (row, col), if mask has bit col set, the cell is already covered—clear the bit and move on. Otherwise, place a domino either horizontally (cover the next cell too) or vertically (set the bit for the next row).

Hamiltonian paths/cycles via plug DP

For counting Hamiltonian paths or cycles on small grids, the profile encodes not just occupancy but connectivity: which cells on the boundary are connected to each other by partial paths. This requires encoding a partition of the boundary cells into pairs and singletons, typically using a compact encoding with 2–3 bits per cell.

Worked example: counting domino tilings (n×m grid)

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;

int n, m;
long long dp[2][1 << 20]; // two rolling rows, mask up to m=20

// Process cell by cell, left to right, top to bottom
void solve() {
    cin >> n >> m;
    if (m > n) swap(n, m); // optimise: iterate over the longer dimension

    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;

    for (int row = 0; row < n; row++) {
        for (int col = 0; col < m; col++) {
            int cur = (row * m + col) & 1;
            int nxt = 1 - cur;
            memset(dp[nxt], 0, sizeof(dp[nxt]));

            for (int mask = 0; mask < (1 << m); mask++) {
                if (dp[cur][mask] == 0) continue;
                long long val = dp[cur][mask];

                if (mask & (1 << col)) {
                    // Cell already filled by vertical domino from above
                    dp[nxt][mask ^ (1 << col)] = (dp[nxt][mask ^ (1 << col)] + val) % MOD;
                } else {
                    // Place vertical domino (extends into next row)
                    dp[nxt][mask | (1 << col)] = (dp[nxt][mask | (1 << col)] + val) % MOD;

                    // Place horizontal domino (if next column is free)
                    if (col + 1 < m && !(mask & (1 << (col + 1)))) {
                        dp[nxt][mask | (1 << (col + 1))] =
                            (dp[nxt][mask | (1 << (col + 1))] + val) % MOD;
                    }
                }
            }
        }
    }

    int last = (n * m) & 1;
    cout << dp[last][0] << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

Contest Problem Walkthrough

Let’s put multiple techniques together on problems that would appear in Div. 1 C/D or ICPC regionals.

Problem 1: Count arrays with bounded prefix sums

Statement. Count the number of arrays a[1..n] with each a[i] ∈ {−1, +1} such that all prefix sums are non-negative and the total sum equals 0. Answer modulo 998244353.

Analysis. These are exactly Dyck paths of length 2n (n steps of +1, n steps of −1). The count is C_n = C(2n,n)/(n+1). We use the bijection/reflection approach from Section 3.

Implementation. Compute C(2n,n) · inv(n+1) mod 998244353. This is O(n) for factorial precomputation.

Problem 2: coloured permutations with forbidden adjacencies

Statement. Given n, count permutations σ of {1,…,n} such that for every i with 1 ≤ i < n, we have |σ(i) − σ(i+1)| ≠ 1. (No two adjacent positions hold consecutive values.) Answer modulo 998244353. n ≤ 2000.

Analysis. This is the problem of counting smiley permutations (a.k.a. Sade’s problem / discord permutations). Direct bijection is hard; we use inclusion–exclusion on the forbidden adjacencies.

Define the “bad” event B_i as |σ(i) − σ(i+1)| = 1. We want σ avoiding all B_i. By IE:

answer = Σ_{S ⊆ {1,…,n-1}} (−1)^|S| · f(S)

where f(S) counts permutations where positions in S have the adjacency constraint forced. This is still exponential in general, but we can use a DP where we process the n−1 gaps left to right. The key insight: forcing |σ(i) − σ(i+1)| = 1 means σ(i) and σ(i+1) must be consecutive integers, so they form a “block” of consecutive values. Groups of consecutive forced gaps create blocks of various lengths. The number of permutations with these block constraints can be computed via a DP on block structure.

State: dp[i][j] = number of ways to partition the first i positions into blocks, using IE sign, with j total blocks created so far. Transitions: extend the current block or start a new one. Within each block of length L, there are 2^L−1 orientations (the consecutive values can be ascending or descending) — but each contiguous run of forced adjacencies of length L gives a block of L+1 positions with exactly 2 orientations (ascending or descending).

The final answer sums over all valid block structures, multiplied by the number of ways to assign values to blocks (a multinomial coefficient).

Problem 3: NTT convolution for multiset counting

Statement. You have k types of coins with values v₁, v₂, …, v_k. For each type, you have unlimited supply. Count the number of ways to select coins (order doesn’t matter) that sum to exactly n. Answer modulo 998244353. n ≤ 10⁶, k ≤ 50.

Analysis. The generating function is Π_i=1^k 1/(1 − x^v_i). We compute this as exp(Σ −ln(1 − x^v_i)) using the identity ln(1/(1−x^v)) = Σ_j=1^∞ x^jv/j. Summing these contributions and then exponentiating the power series gives the answer in O(n log n) using polynomial exp (or simpler: just accumulate the log-sums directly and use the Newton’s method exp).

For a simpler approach: since k is small, multiply the k polynomials one by one. Each 1/(1−x^v) truncated to degree n has ~n/v terms. Process them by direct prefix sum: if f(x) = Σ a_j x^j, then f(x)/(1−x^v) has coefficients b_j = a_j + b_j−v. Total time: O(nk).

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<int> v(k);
    for (int i = 0; i < k; i++) cin >> v[i];

    // dp[j] = number of multisets summing to j
    vector<long long> dp(n + 1, 0);
    dp[0] = 1;

    for (int i = 0; i < k; i++) {
        // Multiply by 1/(1 - x^{v[i]})
        for (int j = v[i]; j <= n; j++) {
            dp[j] = (dp[j] + dp[j - v[i]]) % MOD;
        }
    }

    cout << dp[n] << "\n";
    return 0;
}

Summary & Problem Set

This post covered six major patterns for hard combinatorics in competitive programming. Here is the cheat sheet:

Practice problems

Work through these problems grouped by technique:

Inclusion–Exclusion

• CF 340E — Iahub and Permutations (partial derangement IE)
• CF 285E — Positions in Permutations (double IE on fixed points)
• CF 1228E — Another Filling the Grid (IE on rows/columns)
• AtCoder ABC 214G — Three Permutations (IE with permanent)

Bijection & Catalan

• CF 1644E — Expand the Path (lattice path counting)
• CF 1178F2 — Long Colorful Strip (Catalan-like structure)
• SPOJ DCEPC14B — Balloon Collecting (ballot problem variant)
• CF 1874E — Jellyfish and Mex (bijection + DP on permutations)

Contribution Counting

• CF 1553F — Pairwise Modular Arithmetic (contribution of each pair)
• CF 1392D — Omkar and Bed Wars (contribution per element)
• AtCoder ABC 162E — Sum of gcd (Möbius + contribution)
• CF 1064D — Labyrinth (expected value via linearity)

NTT / Polynomial

• CF 993E — Nikita and Order Statistics (convolution)
• CF 1096G — Lucky Tickets (multi-polynomial multiply)
• CF 1613F — Tree Coloring (polynomial exp)
• AtCoder ARC 106F — Power Series (polynomial inverse)

Broken Profile & Grid DP

• SPOJ M3TILE — Tiling a 3×n rectangle
• SPOJ GNY07H — Tiling (broken profile on 4×n)
• CF 1774G — Segment Painting (profile DP with constraints)
• POJ 1739 — Tony’s Tour (Hamiltonian path plug DP)

Mixed / Multi-technique

• CF 1842F — Tenzing and Tree (contribution + Catalan)
• CF 1500D — Tiles for Bathroom (IE + broken profile)
• ICPC WF 2019 Problem G — First of Her Name (suffix structure + counting)
• CF 1906F — Garden (NTT + IE combined)

This concludes the Combinatorics II module. You now have a complete toolbox: from basic counting principles through generating functions, group theory, Burnside’s lemma, Pólya enumeration, chromatic polynomials, and the advanced patterns covered here. The next step is practice—lots of it. Good luck in your contests!