Generating functions can be used to cheese numerous counting problems without too much thinking. Here, I will show the not proper way to use generating function to solve such problems.
A few people may find the generating function approach for some of these problems is more “intuitive”, as the combinatorial approach is a bit out of the blue.
Given $N$, then given $Q$ queries, each gives you an integer $K$ and asks you to compute $\sum_{i=0}^N \binom{3i}{K}$
- $N \le 1\,000\,000$
Let $\text{dp}_0(K)$, $\text{dp}_1(K)$, and $\text{dp}_2(K)$ be the sum $\sum_{i=0}^N \binom{3i}{K}$, $\sum_{i=0}^N \binom{3i + 1}{K}$, and $\sum_{i=0}^N \binom{3i + 2}{K}$ respectively.
We can see that:
With three equations and three unknowns, the values of all DP can then be inferred.
Suppose we are able to evaluate $\sum_{i=0}^N (1 + x)^{3i}$, then for each query, the answer is the $K$-th coefficient of that generating function.
To evaluate that polynomial,
$$ \begin{align*} \sum_{i=0}^N (1 + x)^{3i} &= \frac{1 - (1 + x)^{3N + 3}}{1 - (1 + x)^3} \\ &= \frac{\sum_{i=1}^{3N + 3} \left(\binom{3N + 3}{i} x^i\right)}{-3x -3x^2 - x^3} \end{align*} $$
The binomial coefficients from the numerator can be easily computed, then perform a standard long division to get the final G.F. in $\mathcal{O}(N)$.
Given a sequence $A$ of $N$ integers, compute the sum $\prod_{i=1}^N \binom{B_i}{A_i}$ over all sequences $B$ of $N$ non-negative integers whose sum is at most $M$.
- $1 \le N \le 2000$
- $1 \le M \le 10^9$
- $0 \le A_i \le 2000$
Suppose you have $\sum A_i + N$ bars and $M - \sum A_i$ stars. The stars and bars before the $a_1$-th bar correspond to $\binom{B_1}{A_1}$; the stars and bars strictly between the $a_1$-th and $a_1 + a_2$-th bars correspond to $\binom{B_2}{A_2}$; and so on; and the stars after the $\sum A_i$-th bar are those that does not make the $B$ sum up to $M$.
The number of ways to arrange those stars and bars is then $\binom{M + N}{\sum A_i + N}$.
Recall that $[x^n] \frac{x^k}{(1 - x)^{k + 1}} = \binom{n}{k}$.
That means the sum of products from the description such that $B$ has a sum of exactly $m$ is the $m$-th coefficient of:
$$\prod_{i = 1}^N \frac{x^{A_i}}{(1 - x)^{A_i + 1}} = \frac{x^{\sum A_i}}{(1 - x)^{\sum A_i + N}}$$
And to get the sum for all coefficients of $x^m$ with $m \le M$, we can get the “prefix-sum” of the above G.F. (by multiplying it with $(1 - x)^{-1}$, and simply get the $M$-th coefficient. In short,
$$[x^M] \frac{x^{\sum A_i}}{(1 - x)^{\sum A_i + N + 1}}$$
which conveniently equals to $\binom{M + N}{\sum A_i + N}$.
Given a rooted tree of $N$ nodes, its leaves has initial state of $0$ or $1$. You can assign an integer parameter $p$ for each internal node (and $p$ is at most the number of its children), then its state will be $1$ if at least $p$ of its children have state $1$. Given $Q$ updates which toggle the state of the leaf nodes from $L$ to $R$, find the number of ways to assign those parameters such that the root node has a state of $1$.
The assignment of a parameter to a node can be reinterpreted as an operator that takes a value from one of its children. Hence, for each leaf with state $1$, we count how many ways are there to have its value reaching the root, which equals the product of all internal nodes’, excluding the nodes that are in the path between the leaf to the root, number of children.
Denote $\text{dp}_0(v)$ and $\text{dp}_1(v)$ as the number of ways to assign parameters for all subtree of $v$ such that the state of $v$ is $0$ and $1$ respectively.
Suppose $v_1, \ldots, v_c$ is the children of $v$, then the number of ways such that exactly $k$ children of $v$ has state of $1$ is the $k$-th coefficient of:
$$\prod_{i=1}^c (\text{dp}_0(v_i) + x \text{dp}_1(v_i))$$
That means the number of ways to get state $1$ if we assign parameter $p$ to node $v$, is the sum of $k$-th ($k \ge p$) coefficient of the above G.F.. Summing for all possible $p$, we can see that we actually need the value $k$ times the $k$-th coefficient. So we can transform the generating function by doing its derivative:
$$ \begin{align*} &x \frac{\mathrm{d}}{\mathrm{d}x} \prod_{i=1}^c (\text{dp}_0(v_i) + x \text{dp}_1(v_i)) \\ =&x \frac{\mathrm{d}}{\mathrm{d}x} \exp \log \prod_{i=1}^c (\text{dp}_0(v_i) + x \text{dp}_1(v_i)) \\ =&x \frac{\mathrm{d}}{\mathrm{d}x} \exp \sum_{i=1}^c \log (\text{dp}_0(v_i) + x \text{dp}_1(v_i)) \\ =&\sum_{i=1}^c \frac{x \text{dp}_1(v_i)}{(\text{dp}_0(v_i) + x \text{dp}_1(v_i))} \exp \sum_{i=1}^c \log (\text{dp}_0(v_i) + x \text{dp}_1(v_i)) \\ =&\sum_{i=1}^c \frac{x \text{dp}_1(v_i)}{(\text{dp}_0(v_i) + x \text{dp}_1(v_i))} \prod_{i=1}^c(\text{dp}_0(v_i) + x \text{dp}_1(v_i)) \\ \end{align*} $$
And because we only need the sum of all those coefficients, we substitute $x = 1$, then obtain the final formula of the DP as:
$$\text{dp}_1(v) = \sum_{i=1}^c \frac{\text{dp}_1(v_i)}{(\text{dp}_0(v_i) + \text{dp}_1(v_i))} \prod_{i=1}^c(\text{dp}_0(v_i) + \text{dp}_1(v_i))$$
Now see that $\text{dp}_0(v) + \text{dp}_1(v)$ is equal to $\prod_{u \in \text{subtree}(v)} \deg(u)$ (where $\deg(u)$ is the number of children of $u$, except when $u$ is a leaf which we set to be $1$ for convenience) because we can assign any parameter to the nodes in the subtree of $v$ without any restriction to the end state of $v$. We denote this value as $p(v)$ which can be precomputed and stays constant throughout the whole update.
Rewrite our DP formula:
$$ \begin{align*} \text{dp}_1(v) &= \sum_{i=1}^c \frac{\text{dp}_1(v_i)}{p(v_i)} \prod_{i=1}^c p(v_i) \\ &= \sum_{i=1}^c \left(\frac{p(v)}{\deg(v) p(v_i)} \text{dp}_1(v_i)\right) \end{align*} $$
Now, here comes the “Competitive Programming” part. Imagine you recurse the above formula up to the leaves. Then, suppose $[u_0, u_1, \ldots, u_k]$ is the path from the root node $u_0$ to a leaf node $u_k$, compute $\prod_{i=1}^k \frac{p(u_{i-1})}{\deg(u_{i-1}) p(u_i)}$, and assign this value to the leaf node $u_k$. If the source gate $u_k$ is $1$, then the assigned value will contribute to the sum of the final answer. Otherwise, its contribution is $0$.