Hi Codeforces,

Our last topic stream was on Combinatorics. We talked about exponentiation, combination (+ why does it have that formula), what is a combinatorial proof (the most interesting part), and proved Pascal's equality and a bunch of other problems using that. Then, we talked about how to calculate combination with O(N) preprocess time and O(1) query time, and finally, solved 559C — Gerald and Giant Chess.

Exponentiation ($$$a^b$$$) in $$$O(lgb)$$$

Combination $$$n\choose k$$$ and why is it $$$\frac{n!}{k!(n-k)!}$$$

Algebraic proofs suck, what is a Combinatorial Proof

(+ Proving a bunch of equalities like Pascal's, using combinatorial proof)

ChatGPT trolling me

Calculating combination in code

simplest: $$$O(n^2+q)$$$

better: $$$O(n+qlgn)$$$

even better: $$$O(nlgn+q)$$$

not that much different: $$$O(n + q)$$$

Solving 559C — Gerald and Giant Chess

(Combination + DP)

This is the link to choose the topic for the next topic stream: