## 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.