Hello Codeforces!
Today I'll be writing about what I have learnt about combinatorics, which played, and, in my opinion, will still be playing an important role in both Codeforces and CP (short for competitive programming).
However, combinatorics is such a great subject that made that impossible for me to write it all in one blog. So, this is just the fourth blog, which is friendly to beginners. If you are interested, please, pay attention to this account and I'll give posts as series for a long term.
If you have found some mistakes in the text, or if you have some questions about the topic, please, leave a comment, and I'll check it weekly and reply. Also, if you find some grammar mistakes, a kind comment will be also welcomed.
Previous Blogs
- Combinatorics (1), basics.
- Combinatorics (2), implementations.
- Combinatorics (3), arrays and recurrence relations.
Content
- generating function
- using generating function to solve problems
- group theory
- permutation group
- Burnside's lemma
- Polya's enumeration theorem
- Polya's enumeration theorem under generating functions
- using Polya's enumeration theorem to solve problems
- Homework
The homework tutorial will be posted in another blog.
Part 1 — Generating function
How to represent an array $$$a_0,a_1,\dots, a_{n-1}$$$ with a function? Maybe we can use Berlekamp-Massey algorithm to calculate the recurrence relation out.
But it's too complicated. Maybe to be more easy, we can generating a function $$$f(x)=a_0+a_1x^2+\dots+a_{n-1} x^n=\sum_{i=1}^{n}a_{i-1}x^i$$$. For example $$$[1,2,3]$$$'s generating function is $$$3x^2+2x+1$$$.
Wtf? This is really naive isn't it? But you may find that it is meaningless to calculate the value of the function with any possible $$$x$$$.
Don't worry. Here is a task for you:
There are many red and blue tickets. You can choose at most $$$K$$$ red tickets and $$$M$$$ blue tickets only if $$$M$$$ is even. You want to get $$$N$$$ tickets in total. How many different ways are there to do the problem?
We can construct a generating function $$$R(x)$$$ generated with $$$r=[\underbrace{1,1,1,\dots 1}_{\text{n+1 ones}}]$$$, when $$$r_i=1$$$ means you can get $$$i$$$ red tickets.
Also, we can construct a generating function $$$B(x)$$$ generated with $$$b=[1,0,1,0,\dots]$$$, when $$$b_i=1$$$ means you can get $$$i$$$ blue tickets.
Then you can make $$$F(x)=R(x)\times B(x)=\sum\limits_{i=0}^{M}f_ix^i$$$. And $$$f_M$$$ is the answer. Proof is trivial when you do the convolution by yourself, it is same as brute force with $$$\mathcal O(n^2)$$$ complexity.
Under FFT, the time complexity is $$$\mathcal O(n\log n)$$$.
But this is not all what generating functions can do. We have another important property of it: $$$x$$$'s detailed value is useless, so we can give a proper range to it.
What is the generating function of $$$[1,1,1,\dots]$$$?
Answer: $$$\frac{1}{1-x}$$$.
Why??? OK, I have to say $$$1+x+x^2+\dots$$$ is also correct. But why these two are the same? Are you kidding the readers? Actually, we can give the range $$$(-1,1)$$$ to it. Then since $$$1+x+x^2+\dots +x^n=\frac{1-x^n}{1-x}$$$, when $$$x\to \infty$$$, $$$x^n\to 0$$$. Then $$$1-x^n=1$$$, so the answer is $$$\frac{1}{1-x}$$$.
Practice: what is the generating function of $$$[1,0,1,0,1,0,\dots]$$$? What about $$$[1,0,0,1,0,0,\dots]$$$, $$$[1,2,3,4,\dots]$$$ and $$$[1,1+2,1+2+3,1+2+3+4,\dots]$$$?
Try to use special binomial theorem to explain some of and, even more than them. For example what generates $$$\frac{1}{(1-x)^k}$$$. This is homework, proof next time.
Part 2 — using generating function to solve problems
If you want to implement them, you should learn the polynomial theory first.
Codeforces 632E — Thief in a Shop
This is a backpack-dp problem, but can you optimize it?
Construct a generating function $$$f(x)=\sum\limits_{i=1}^{n}x^{a_i}$$$, this is what you can get when you can choose one thing.
Then expand one to $$$\textbf{\textit{k}}$$$，you only need to calculate $$$f^k(x)$$$. Use FFT to reach $$$\mathcal O(n\log n)$$$.
Codeforces 438E — The Child and Binary Tree
Catalan is discussed before, now we construct the generating function for the weights of a single node $$$W(x)=\sum_{i=1}^{n}x^{c_i}$$$.
Additionally, the generating function of Catalan sequence is $$$C=xC^2+1$$$, then we get $$$F^2W-F+1=0$$$. Solve it, we get $$$\dfrac{2}{1-\sqrt{1-4W}}$$$.
Use Newton's method to reach $$$\mathcal O(n\log n)$$$.
