iii. Contribution and Complementary Counting

The two most common moves in counting problems: swap the order of summation (contribution), and count the complement.

Contribution technique

Instead of summing $f$ over every structure, sum over the atoms and count how many structures each atom appears in:

${\sum }_{S}f(S)={\sum }_S{\sum }_{x\in S}w(x)={\sum }_{x}w(x)\cdot \#\{S:x\in S\}.$

Sum over	Atom	Count
all subarray sums	$a_i$	$(i+1)(n-i)$
all subsequence sums	$a_i$	$2^{n-1}$
pairwise tree distances	edge into a subtree of size $s$	$s(n-s)$
subarray minimums / maximums	$a_i$ as the minimum	$(i-L_i)(R_i-i)$ via monotonic stack
$\max -\min$ over all subarrays	both of the above	subtract
pairwise XOR	bit $b$ with $c_b$ ones	$c_b(n-c_b)2^b$
subarray XORs, ANDs, ORs	bit $b$	prefix parities / last zero positions
max of each $k$-subset	sorted $a_i$ as max	$\left(\genfrac{}{}{0ex}{}{i}{k-1}\right)$
number of distinct values over all subarrays	first occurrence of each value in the subarray	$(i-{\mathrm{prev}}_i)(n-i)$
inversions over all permutations	each pair	$n!/2$
expected value	indicator of an event	its probability (linearity)

Reach for this when: the answer sums over exponentially or quadratically many objects; the object’s value decomposes into a sum over its parts (sum, count, XOR per bit, min/max via “who is the min”); and each part’s number of containing objects has a simple closed form (product of left/right choices, a binomial, a subtree size).

Tie-breaking for minimum/maximum contributions: use strict on one side and non-strict on the other (previous strictly smaller, next smaller-or-equal), so each subarray is counted exactly once.

Proof: the contribution counts in the table, and the tie-break

Subarray sums, atom $a_i$: $a_i$ appears in subarray $[l,r]$ iff $l\le i\le r$; there are $i+1$ choices of $l\in [0,i]$ and $n-i$ choices of $r\in [i,n-1]$, giving $(i+1)(n-i)$ subarrays.
Subsequence sums: $a_i$ appears in a subsequence iff it is included; the other $n-1$ elements are independently in or out, giving $2^{n-1}$.
Tree distances, edge $e$ splitting the tree into a side of size $s$ and $n-s$: $\mathrm{dist}(u,v)={\sum }_{e\text{ on the }u\text{-}v\text{ path}}1$, so summing over all pairs, edge $e$ is counted once for every pair with one endpoint on each side — $s(n-s)$ such pairs, by independent choice of one vertex from each side.
Pairwise XOR, bit $b$ with $c_b$ ones among $n$ numbers: bit $b$ of $a_i\oplus a_j$ is set iff exactly one of $a_i,a_j$ has it set, i.e. one comes from the $c_b$ numbers with that bit set and the other from the $n-c_b$ without — exactly $c_b(n-c_b)$ such unordered pairs (one choice from each group), each contributing $2^b$ to the sum.
The tie-break for subarray minimums. Every subarray has a unique minimum position only if ties are broken consistently; using strictly-smaller on one side (L[i]: nearest index with $a_{L[i]}<a_i$) and smaller-or-equal on the other (R[i]: nearest index with $a_{R[i]}\le a_i$) ensures that among several equal minimum values in one subarray, exactly one of them — the first occurrence (leftmost) — has that subarray counted in its $(i-L_i)(R_i-i)$ range, since any subarray spanning multiple copies of the minimum value is only included in the range computed from the leftmost copy (the other copies’ computed ranges, using the same asymmetric rule, exclude it on their left side). This avoids both under- and over-counting duplicate minimum values. $■$

Tested: sumSubarrayMins checked against the brute-force $O(n^2)$ double sum over all subarrays, including arrays with many duplicate (tied) values, on random small arrays.

ll sumSubarrayMins(const vector<ll>& a) {
    int n = a.size(); vector<int> L(n), R(n), st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
        L[i] = st.empty() ? -1 : st.back(); st.push_back(i);
    }
    st.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && a[st.back()] > a[i]) st.pop_back();
        R[i] = st.empty() ? n : st.back(); st.push_back(i);
    }
    ll ans = 0;
    for (int i = 0; i < n; i++) ans += a[i] * (i - L[i]) * (R[i] - i);
    return ans;
}

Higher-order contributions

• Squares are pairs. ${\sum }_S|S{|}^2={\sum }_S{\sum }_{x,y\in S}1={\sum }_{(x,y)}\#\{S\ni x,y\}$. Count ordered pairs of atoms that lie together. The same trick gives $E[X^2]$ for a count $X$: sum over ordered pairs of $P(\text{both})$.
• $k$-th powers via falling factorials. $X^k={\sum }_{j}S(k,j)j!\left(\genfrac{}{}{0ex}{}{X}{j}\right)$ (Stirling numbers of the second kind), and $\left(\genfrac{}{}{0ex}{}{X}{j}\right)$ counts $j$-subsets of atoms, which is usually easy to sum. This is how “sum over all subsets of (size)${}^k$” or "$E[X^k]$" problems are solved: ${\sum }_S\left(\genfrac{}{}{0ex}{}{|S|}{j}\right)$ over subsets of an $n$-set equals $\left(\genfrac{}{}{0ex}{}{n}{j}\right)2^{n-j}$.
• Sum over pairs of a function of $\gcd$. $f(\gcd (a,b))={\sum }_{d\mid \gcd }(f\ast \mu )(d)$, so swap to ${\sum }_{d}g(d)\cdot c_d^2$ where $c_d$ counts multiples of $d$ (Möbius).
• “Value at least $t$”. For non-negative integers, $X={\sum }_{t\ge 1}[X\ge t]$. So $\sum$ of maxima $={\sum }_t\#\{S:\max S\ge t\}$, and $E[X]={\sum }_{t}P(X\ge t)$. This often turns a max into a count over thresholds (“count subsets whose max is $\ge t$” = all minus subsets of values $<t$).
• Order statistics. “Sum over subsets of the $k$-th smallest”: sort, then element $i$ contributes $\left(\genfrac{}{}{0ex}{}{i}{k-1}\right)\left(\genfrac{}{}{0ex}{}{n-1-i}{|S|-k}\right)$.
• Per-bit decomposition. Every bitwise expression splits into independent bits. Count, for each bit, how many objects have it set, then multiply by $2^b$. For sums of XORs of subarrays, keep counts of prefix parities 0/1 per bit.
• Tree contributions. For pairs $(u,v)$ the edge contribution is $s(n-s)$. For $k$-subsets of vertices, the number of subsets whose Steiner tree uses edge $e$ is $\left(\genfrac{}{}{0ex}{}{n}{k}\right)-\left(\genfrac{}{}{0ex}{}{s}{k}\right)-\left(\genfrac{}{}{0ex}{}{n-s}{k}\right)$.

Complementary counting

$\#\text{good}=\#\text{all}-\#\text{bad}.$

Use it when “bad” is simpler: at least one becomes none, not all equal becomes all equal, contains a pattern becomes avoids it (automaton DP), connected becomes disconnected.

Want	Count instead
at least one $X$	total minus none
strings containing a pattern	total minus avoiding strings (KMP / Aho-Corasick automaton DP)
intersecting pairs of intervals	all pairs minus disjoint pairs (sort by endpoints)
permutations with a fixed point	$n!-D_n$
triangles in the complement of $G$	$\left(\genfrac{}{}{0ex}{}{n}{3}\right)-t(G)-\frac{1}{2}{\sum }_v\mathrm{deg}v(n-1-\mathrm{deg}v)$ (Goodman: the sum counts triangles with edges of both kinds twice)
binary strings with “11”	$2^n-F_{n+2}$ (proof below)

Connected structures by fixing the component of vertex 1. With $g_n$ all graphs and $c_n$ connected graphs:

$c_n=g_n-{\sum }_{k=1}^{n-1}\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)c_k{g}_{n-k}.$

That’s $O(n^2)$, or $O(n\log n)$ via the exponential formula $C(x)=\log G(x)$ (power series). The same pattern counts connected bipartite graphs, strongly connected tournaments and labelled DAGs (with an inclusion-exclusion sign over the set of sources).

Probability. $P(\text{at least one})=1-\prod (1-p_i)$ for independent events. For dependent overlapping events use inclusion-exclusion (Inclusion-Exclusion).

Practice anchors (CSES): Distributing Apples (direct stars-and-bars, no complement needed — the contrast is instructive), Christmas Party (derangements), Grid Paths II (obstacles via complementary counting over forbidden-cell inclusion-exclusion).

Proof: "11"-avoiding binary strings count $F_{n+2}$

Let $f(n)$ be the number of length-$n$ binary strings with no two consecutive 1s. Condition on the last character: if it’s 0, the rest is any valid string of length $n-1$ ($f(n-1)$ ways); if it’s 1, the second-to-last must be 0 (else “11”), and the rest is any valid string of length $n-2$ followed by “01” ($f(n-2)$ ways). So $f(n)=f(n-1)+f(n-2)$ — the Fibonacci recurrence — with $f(0)=1,f(1)=2$, giving $f(n)=F_{n+2}$ (matching the standard indexing $F_1=F_2=1$). Subtracting from the total $2^n$ gives the count with “11”. $■$

Double counting

Count the same set two ways. Classic uses:

• Handshake lemma: count (vertex, incident edge) pairs.
• ${\sum }_{k}k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n{2}^{n-1}$: count (set, chosen element) pairs.
• ${\sum }_{d\le n}\lfloor n/d\rfloor ={\sum }_{m\le n}\tau (m)$: count pairs $(d,m)$ with $d\mid m$.
• Number of triangles $\le m^{3/2}$: orient edges from low to high degree, so every vertex has out-degree $O(\sqrt{m})$.

Proof: the double-counting identities above

${\sum }_{k}k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n{2}^{n-1}$: count pairs (subset $S$, marked element $x\in S$) two ways. Choosing $x$ first ($n$ ways) then the rest of $S$ freely among the remaining $n-1$ elements ($2^{n-1}$ ways) gives $n{2}^{n-1}$; choosing $S$ first (size $k$, $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ ways) then $x\in S$ ($k$ ways) and summing over $k$ gives ${\sum }_{k}k\left(\genfrac{}{}{0ex}{}{n}{k}\right)$. Equal.
${\sum }_{d\le n}\lfloor n/d\rfloor ={\sum }_{m\le n}\tau (m)$: count pairs $(d,m)$ with $1\le d,m\le n$ and $d\mid m$. Fixing $d$, the multiples of $d$ up to $n$ number $\lfloor n/d\rfloor$; fixing $m$, its divisors number $\tau (m)$. Summing each way counts the same set of pairs.
Triangle count $O(m^{3/2})$ via low-to-high orientation: orient every edge from the lower-degree endpoint to the higher (break ties by label), so a vertex’s out-edges go only to vertices of degree $\ge$ its own. Its out-degree is bounded by $O(\sqrt{m})$: if $\mathrm{deg}(v)>\sqrt{2m}$, at most $2m/\mathrm{deg}(v)<\sqrt{2m}$ other vertices can have degree $\ge \mathrm{deg}(v)$ (else ${\sum }_u\mathrm{deg}(u)$ would exceed $2m$), and $v$‘s out-neighbours are a subset of those. Every triangle, listed in this orientation, has exactly one vertex from which both its other two vertices are reached by a single out-edge each (the “source” of the triangle’s two forward edges), so enumerating, for every vertex, every pair of its out-neighbours and checking the edge between them counts every triangle exactly once, in ${\sum }_{v}O(\text{outdeg}(v{)}^2)=O(m\cdot \sqrt{m})=O(m^{3/2})$ total (each vertex contributes at most its out-degree squared, and out-degree is $O(\sqrt{m})$, summed over $O(m)$ vertex-edge incidences). $■$

Pitfalls

• Equal values: fix a tie-break by index.
• Modular subtraction needs (all - bad + MOD) % MOD.
• Make sure “all” and “bad” live in the same universe (ordered vs unordered, labelled vs unlabelled, empty set included or not).
• Overflow in $a_i\cdot i\cdot (n-i)$: use ll or reduce modulo.