[Educational] Combinatorics Study Notes (2)

Revision en5, by Black_Fate, 2022-12-23 03:24:49

Hello Codeforces!

Today I'll write down what I learn about combinatorics, and I think it common in Codeforces contests and competitive programming.

However, combinatorics is a great subject, and I cannot write it all in one blog. So, this is just the first blog, it's for beginners. If you are interested, please, pay attention to this account and it'll give posts like this for a long term.

If there is something wrong in the text, or if you have some problems about the topic, just give a comment, I'll check it weekly and reply. Also, if you find some grammar mistakes, welcome too.

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.

Tags implementations, combinatorics, maths, number theory

History

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