How to incorrectly use Generating Function

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.

On counting the number of zigzag sequences

We will describe on how to find the number of zigzag sequences $a_1 \lt a_2 \gt \ldots$ in $O(N \log N)$.

Sum of $C(N, i) \times i^K$

Given $N \le 10^9$, $K \le 10^5$, find $$\sum_{i=0}^N \binom{N}{i} i^K$$

Notes on Fast Fourier Transform

A summary of what FFT can do.

Factorial mod prime

We are to compute $n! \bmod p$ in $O(\sqrt{p} \log p)$.

Project Euler #100

Given $P$, $Q$, and $M$, find smallest $n$ such that $\frac{b(b-1)}{n(n-1)} = \frac{P}{Q}$, where $b$ and $n$ are positive integers and $n > M$.

On Prime Counting in Sublinear Time

We are to count how many prime numbers are there up to $N$ ($N \leq 10^{11}$). Let $\pi(N)$ be the number of primes up to $N$, and $f(n, p)$ be the number of integers $x$, for $2 \leq x \leq N$, such that it contains no prime factor $< p$. If $p$ is not prime, then $f(n, p) = f(n, p-1)$. Otherwise $$f(n, p) = f(n, p-1) - \left(f\Big(\big\lfloor\frac{n}{p} \big\rfloor, p-1\Big) - \pi(p-1)\right)$$ Our goal is to compute $\pi(N) = f(N, \sqrt N)$.

Binomial Modulo Prime Power

Our goal is to solve ${n \choose m} \pmod {p^e}$, ($n, m, p^e < 10^{300}$, $p$ prime number). After precomputation, the number of operation to compute ${n \choose m} \pmod{p^e}$ is $O(e \log n)$. Define $(n!)_p$ as the product of all positive integers $i \not\equiv 0 \pmod p$ for all $1 \leq i \leq n$. We are to to compute $(n!)_p \pmod{p^e}$.

Project Euler #242

This post will give the analysis to Project Euler 242 from hackerrank, which is an extended version from the original Project Euler. Given 5 integers $m$, $r$, $n$, $k$, and $M$, count the number of k-subsets of $\{1, 2, \ldots, n\}$ such that the sum of the subset is $r \pmod m$. This is actually an extended version of IMO 1995 P6 (having $m = p$, $n = 2p$, $k = p$, $r = 0$). A discussion to this problem can be found in AOPS.