[Educational] Combinatorics Study Notes (2)

Правка en10, от Black_Fate, 2022-12-23 04:04:25

Hello Codeforces!

Today I'll be writing about what I have learnt about combinatorics, which played, and, in my opinion, will still be playing a 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 second 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

Blogs in the future

If finished, I'll link them.

  • Combinatorics (3)
  • Bitmask
  • Probabilities

Content

  1. Quick power
  2. Fermat's little theorem
  3. extent-gcd
  4. The multiplicative inverse of an integer
  5. Prework optimize
  6. homework

Part 1 — Quick power

How to calculate the value of $$$a^b\bmod p$$$?

You may write out this code easily:

long long power(long long a, long long b, long long p) {
	long long res = 1;
	while(b--) res = res * a % p;
	return res;
}

Seems easy, right? This code has $$$\mathcal O(b)$$$ time complexity. But what if $$$1\leq a,b\leq 10^9$$$? Can you solve it?

Here, we use divide ans conquer to solve this:

$$$a^b=\begin{cases}a^{\left\lfloor \frac{b}{2} \right\rfloor} \times a^{\left\lfloor \frac{b}{2} \right\rfloor} & n \text{ is even} \\ a^{\left\lfloor \frac{b}{2} \right\rfloor} \times a^{\left\lfloor \frac{b}{2} \right\rfloor} \times a & n \text{ is odd}\end{cases}$$$

According to this, we can write out a code easily:

long long powpow(long long a, long long b, long long p) {
	if(b % 2 == 1) {
		long long r = powpow(a, b / 2, p);
		return r * r % p * a % p;
	} else {
		long long r = powpow(a, b / 2, p);
		return r * r % p;
	}
}

Now certainly the time complexity is $$$\mathcal O(\log b)$$$. But this code contains a recursion. Since the recursion is simple, we can get rid of recursion:

long long quickpow(long long a, long long b, long long p) {
	long long res = 1, nowa = 1;
	while(b) {
		if(b % 2 == 1) res = res * nowa % p;
		nowa = a * a % p;
		a = nowa;
		b /= 2;
	}
	return res;
}

Now I'll give a fast version of it without explaining, you can use it in the later implementaions.

long long quickpow(long long a, long long b, long long p) {
	long long res = 1;
	while(b) {
		if(b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}

The time complexity remains the same, but the constant is smaller now. If you still wonders why, you can wait for my bitmask post.

**Exercise: ** Calculate $$$(a\times b) \bmod p$$$, $$$10^9 \leq p\leq 10^{18}$$$.

In C++, long long varible is between $$$-2^{63}$$$ and $$$2^{63}-1$$$, which is about $$$10^{18}$$$. When you do a * b % p, then things below will happen:

  • $$$a\times b$$$ is calculated first, it can overflow and lead to error.
  • $$$a\times b\bmod p$$$ is calculated, the result is already wrong.

So multiply it with brute force is impossible, can you think of an $$$\mathcal O(\log b)$$$ solution?

Solution

You may wonder, if we divide it into $$$2$$$ parts, why don't we divide it into $$$k$$$ parts?

Actually, the time complexity is $$$\mathcal O(k\times\log_{k} n)$$$.

Look at the image we draw out $$$y=k+k\times \log_{k}(8\times 10^9)$$$:

And we draw out $$$\color{green} {x=2}$$$ and $$$\color{red}{x=3}$$$:

So we find that $$$k=2,3$$$ is optimal. But $$$k=3$$$ uses $$$3$$$ if sentences, this lead to larger constant than expected, so we use $$$k=2$$$ instead.

Теги implementations, combinatorics, maths, number theory

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en29 Английский Black_Fate 2022-12-31 18:00:14 0 Homework D changed (published)
en28 Английский Black_Fate 2022-12-31 17:59:38 631 (saved to drafts)
en27 Английский Black_Fate 2022-12-30 15:03:02 11
en26 Английский Black_Fate 2022-12-23 19:21:20 266
en25 Английский Black_Fate 2022-12-23 14:58:44 39
en24 Английский Black_Fate 2022-12-23 14:57:30 429 (published)
en23 Английский Black_Fate 2022-12-23 14:53:43 998
en22 Английский Black_Fate 2022-12-23 14:37:19 1881
en21 Английский Black_Fate 2022-12-23 14:24:23 1873
en20 Английский Black_Fate 2022-12-23 14:07:21 1573
en19 Английский Black_Fate 2022-12-23 13:38:52 5
en18 Английский Black_Fate 2022-12-23 13:38:22 593
en17 Английский Black_Fate 2022-12-23 11:14:57 80
en16 Английский Black_Fate 2022-12-23 11:13:50 40
en15 Английский Black_Fate 2022-12-23 11:12:46 992
en14 Английский Black_Fate 2022-12-23 08:36:29 261
en13 Английский Black_Fate 2022-12-23 08:32:58 434
en12 Английский Black_Fate 2022-12-23 04:07:13 38
en11 Английский Black_Fate 2022-12-23 04:06:26 1
en10 Английский Black_Fate 2022-12-23 04:04:25 1
en9 Английский Black_Fate 2022-12-23 04:03:59 2
en8 Английский Black_Fate 2022-12-23 04:03:35 581
en7 Английский Black_Fate 2022-12-23 03:50:08 939
en6 Английский Black_Fate 2022-12-23 03:34:27 484
en5 Английский Black_Fate 2022-12-23 03:24:49 146
en4 Английский Black_Fate 2022-12-23 03:22:42 993
en3 Английский Black_Fate 2022-12-23 03:06:36 2
en2 Английский Black_Fate 2022-12-23 03:03:01 706
en1 Английский Black_Fate 2022-12-21 17:26:06 792 Initial revision (saved to drafts)