notebook
26 pág.

notebook


DisciplinaPreparação para Maratona de Programação I17 materiais19 seguidores
Pré-visualização7 páginas
1
IIUM cat-us-trophy
Contents
Combinatorics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Data structures (BIT, BIT2D, RMQ-DP, RMQ-segment tree, union-find, misof\u2019s tree, treap) . . . 4
Number theory (*gcd, totient, sieve, modexp, rabinmiller) . . . . . . . . . . . . . . . . . . . . . . . 7
String algorithms (SuffixA, Aho-Corasick, KMP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Graph algorithms (LCA, SCC, BPM-konig, Bellman-Ford, NetFlow, MinCost MaxFlow) . . . . . . 13
Games theory (Grundy, Misère) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Appendices (LU, Blossom, binary search, ASCII table) . . . . . . . . . . . . . . . . . . . . . . . . . 22
.vimrc
set ai ts=4 sw=4 st=4 noet nu nohls
syntax enable
filetype plugin indent on
map <F6> :w<CR>:!g++ % -g && (ulimit -c unlimited; ./a.out < ~/input.txt) <CR>
map <F5> <F6>
colo pablo
map <F12> :!gdb ./a.out -c core <CR>
template.cpp
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<cassert>
#include<climits>
using namespace std;
#define REP(i,n) for(int i=0, _e(n); i<_e; i++)
#define FOR(i,a,b) for(int i(a), _e(b); i<=_e; i++)
#define FORD(i,a,b) for(int i(a), _e(b); i>=_e; i--)
#define FORIT(i, m) for (__typeof((m).begin()) i=(m).begin(); i!=(m).end(); ++i)
#define SET(t,v) memset((t), (v), sizeof(t))
#define ALL(x) x.begin(), x.end()
#define UNIQUE(c) (c).resize( unique( ALL(c) ) - (c).begin() )
#define sz size()
#define pb push_back
#define VI vector<int>
#define VS vector<string>
2
typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
#define D(x) if(1) cout << __LINE__ <<&quot; &quot;<< #x &quot; = &quot; << (x) << endl;
#define D2(x,y) if(1) cout << __LINE__ <<&quot; &quot;<< #x &quot; = &quot; << (x) \
<<&quot;, &quot; << #y &quot; = &quot; << (y) << endl;
Combinatorics
Mathematical Sums\u2211\ufe00\ud835\udc5b
\ud835\udc58=0 \ud835\udc58 = \ud835\udc5b(\ud835\udc5b + 1)/2
\u2211\ufe00\ud835\udc4f
\ud835\udc58=\ud835\udc4e \ud835\udc58 = (\ud835\udc4e + \ud835\udc4f)(\ud835\udc4f\u2212 \ud835\udc4e + 1)/2\u2211\ufe00\ud835\udc5b
\ud835\udc58=0 \ud835\udc58
2 = \ud835\udc5b(\ud835\udc5b + 1)(2\ud835\udc5b + 1)/6
\u2211\ufe00\ud835\udc5b
\ud835\udc58=0 \ud835\udc58
3 = \ud835\udc5b2(\ud835\udc5b + 1)2/4\u2211\ufe00\ud835\udc5b
\ud835\udc58=0 \ud835\udc58
4 = (6\ud835\udc5b5 + 15\ud835\udc5b4 + 10\ud835\udc5b3 \u2212 \ud835\udc5b)/30 \u2211\ufe00\ud835\udc5b\ud835\udc58=0 \ud835\udc585 = (2\ud835\udc5b6 + 6\ud835\udc5b5 + 5\ud835\udc5b4 \u2212 \ud835\udc5b2)/12\u2211\ufe00\ud835\udc5b
\ud835\udc58=0 \ud835\udc65
\ud835\udc58 = (\ud835\udc65\ud835\udc5b+1 \u2212 1)/(\ud835\udc65\u2212 1) \u2211\ufe00\ud835\udc5b\ud835\udc58=0 \ud835\udc58\ud835\udc65\ud835\udc58 = (\ud835\udc65\u2212 (\ud835\udc5b + 1)\ud835\udc65\ud835\udc5b+1 + \ud835\udc5b\ud835\udc65\ud835\udc5b+2)/(\ud835\udc65\u2212 1)2
Binomial coefficients
0 1 2 3 4 5 6 7 8 9 10 11 12
0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5 1
6 1 6 15 20 15 6 1
7 1 7 21 35 35 21 7 1
8 1 8 28 56 70 56 28 8 1
9 1 9 36 84 126 126 84 36 9 1
10 1 10 45 120 210 252 210 120 45 10 1
11 1 11 55 165 330 462 462 330 165 55 11 1
12 1 12 66 220 495 792 924 792 495 220 66 12 1
0 1 2 3 4 5 6 7 8 9 10 11 12
(\ufe00
\ud835\udc5b
\ud835\udc58
)\ufe00
= \ud835\udc5b!
(\ud835\udc5b\u2212\ud835\udc58)!\ud835\udc58!(\ufe00
\ud835\udc5b
\ud835\udc58
)\ufe00
=
(\ufe00
\ud835\udc5b\u22121
\ud835\udc58
)\ufe00
+
(\ufe00
\ud835\udc5b\u22121
\ud835\udc58\u22121
)\ufe00(\ufe00
\ud835\udc5b
\ud835\udc58
)\ufe00
= \ud835\udc5b
\ud835\udc5b\u2212\ud835\udc58
(\ufe00
\ud835\udc5b\u22121
\ud835\udc58
)\ufe00(\ufe00
\ud835\udc5b
\ud835\udc58
)\ufe00
= \ud835\udc5b\u2212\ud835\udc58+1
\ud835\udc58
(\ufe00
\ud835\udc5b
\ud835\udc58\u22121
)\ufe00(\ufe00
\ud835\udc5b+1
\ud835\udc58
)\ufe00
= \ud835\udc5b+1
\ud835\udc5b\u2212\ud835\udc58+1
(\ufe00
\ud835\udc5b
\ud835\udc58
)\ufe00(\ufe00
\ud835\udc5b
\ud835\udc58+1
)\ufe00
= \ud835\udc5b\u2212\ud835\udc58
\ud835\udc58+1
(\ufe00
\ud835\udc5b
\ud835\udc58
)\ufe00
\u2211\ufe00\ud835\udc5b
\ud835\udc58=1 \ud835\udc58
(\ufe00
\ud835\udc5b
\ud835\udc58
)\ufe00
= \ud835\udc5b2\ud835\udc5b\u22121\u2211\ufe00\ud835\udc5b
\ud835\udc58=1 \ud835\udc58
2
(\ufe00
\ud835\udc5b
\ud835\udc58
)\ufe00
= (\ud835\udc5b + \ud835\udc5b2)2\ud835\udc5b\u22122
(\ufe00
\ud835\udc5a+\ud835\udc5b
\ud835\udc5f
)\ufe00
=
\u2211\ufe00\ud835\udc5f
\ud835\udc58=0
(\ufe00
\ud835\udc5a
\ud835\udc58
)\ufe00(\ufe00
\ud835\udc5b
\ud835\udc5f\u2212\ud835\udc58
)\ufe00(\ufe00
\ud835\udc5b
\ud835\udc58
)\ufe00
=
\u220f\ufe00\ud835\udc58
\ud835\udc56=1
\ud835\udc5b\u2212\ud835\udc58+\ud835\udc56
\ud835\udc56
Number of ways to pick a multiset of size \ud835\udc58 from \ud835\udc5b elements:
(\ufe00
\ud835\udc5b+\ud835\udc58\u22121
\ud835\udc58
)\ufe00
Number of \ud835\udc5b-tuples of non-negative integers with sum \ud835\udc60:
(\ufe00
\ud835\udc60+\ud835\udc5b\u22121
\ud835\udc5b\u22121
)\ufe00
, at most \ud835\udc60:
(\ufe00
\ud835\udc60+\ud835\udc5b
\ud835\udc5b
)\ufe00
Number of \ud835\udc5b-tuples of positive integers with sum \ud835\udc60:
(\ufe00
\ud835\udc60\u22121
\ud835\udc5b\u22121
)\ufe00
Number of lattice paths from (0, 0) to (\ud835\udc4e, \ud835\udc4f), restricted to east and north steps:
(\ufe00
\ud835\udc4e+\ud835\udc4f
\ud835\udc4e
)\ufe00
Catalan numbers \ud835\udc36\ud835\udc5b =
1
\ud835\udc5b+1
(\ufe00
2\ud835\udc5b
\ud835\udc5b
)\ufe00
. \ud835\udc360 = 1, \ud835\udc36\ud835\udc5b =
\u2211\ufe00\ud835\udc5b\u22121
\ud835\udc56=0 \ud835\udc36\ud835\udc56\ud835\udc36\ud835\udc5b\u22121\u2212\ud835\udc56. \ud835\udc36\ud835\udc5b+1 = \ud835\udc36\ud835\udc5b
4\ud835\udc5b+2
\ud835\udc5b+2
.
\ud835\udc360, \ud835\udc361, . . . = 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, . . .
\ud835\udc36\ud835\udc5b is the number of: properly nested sequences of \ud835\udc5b pairs of parentheses; rooted ordered binary trees
with \ud835\udc5b + 1 leaves; triangulations of a convex (\ud835\udc5b + 2)-gon.
Derangements . Number of permutations of \ud835\udc5b = 0, 1, 2, . . . elements without \ufb01xed points is
1, 0, 1, 2, 9, 44, 265, 1854, 14833, . . . Recurrence: \ud835\udc37\ud835\udc5b = (\ud835\udc5b \u2212 1)(\ud835\udc37\ud835\udc5b\u22121 + \ud835\udc37\ud835\udc5b\u22122) = \ud835\udc5b\ud835\udc37\ud835\udc5b\u22121 + (\u22121)\ud835\udc5b.
Corollary: number of permutations with exactly \ud835\udc58 \ufb01xed points is
(\ufe00
\ud835\udc5b
\ud835\udc58
)\ufe00
\ud835\udc37\ud835\udc5b\u2212\ud835\udc58.
Stirling numbers of 1\ud835\udc60\ud835\udc61 kind . \ud835\udc60\ud835\udc5b,\ud835\udc58 is (\u22121)\ud835\udc5b\u2212\ud835\udc58 times the number of permutations of \ud835\udc5b elements
with exactly \ud835\udc58 permutation cycles.
[\ufe00
\ud835\udc5b
\ud835\udc58
]\ufe00
= |\ud835\udc60\ud835\udc5b,\ud835\udc58| = |\ud835\udc60\ud835\udc5b\u22121,\ud835\udc58\u22121| + (\ud835\udc5b \u2212 1)|\ud835\udc60\ud835\udc5b\u22121,\ud835\udc58| \ud835\udc60(0, 0) = 1 and
\ud835\udc60(\ud835\udc5b, 0) = \ud835\udc60(0, \ud835\udc5b) = 0.
3
n/k 0 1 2 3 4 5 6 7 8 9
0 1
1 0 1
2 0 =1 1
3 0 2 =3 1
4 0 =6 11 =6 1
5 0 24 =50 35 =10 1
6 0 =120 274 =225 85 =15 1
7 0 720 =1764 1624 =735 175 =21 1
8 0 =5040 13068 =13132 6769 =1960 322 =28 1
9 0 40320 =109584 118124 =67284 22449 =4536 546 =36 1
0 1 2 3 4 5 6 7 8 9
Stirling numbers of 2\ud835\udc5b\ud835\udc51 kind . \ud835\udc46\ud835\udc5b,\ud835\udc58 =
{\ufe00
\ud835\udc5b
\ud835\udc58
}\ufe00
is the number of ways to partition a set of \ud835\udc5b elements
into exactly \ud835\udc58 non-empty subsets.
{\ufe00
\ud835\udc5b
\ud835\udc58
}\ufe00
= \ud835\udc46\ud835\udc5b,\ud835\udc58 = \ud835\udc46\ud835\udc5b\u22121,\ud835\udc58\u22121 + \ud835\udc58\ud835\udc46\ud835\udc5b\u22121,\ud835\udc58; \ud835\udc46\ud835\udc5b,1 = \ud835\udc46\ud835\udc5b,\ud835\udc5b = 1.{\ufe00
\ud835\udc5b
\ud835\udc58
}\ufe00
= 1
\ud835\udc58!
\u2211\ufe00\ud835\udc58
\ud835\udc57=0(\u22121)\ud835\udc57
(\ufe00
\ud835\udc58
\ud835\udc57
)\ufe00
(\ud835\udc58 \u2212 \ud835\udc57)\ud835\udc5b.
n/k 0 1 2 3 4 5 6 7 8 9 10
0 1
1 0 1
2 0 1 1
3 0 1 3 1
4 0 1 7 6 1
5 0 1 15 25 10 1
6 0 1 31 90 65 15 1
7 0 1 63 301 350 140 21 1
8 0 1 127 966 1701 1050 266 28 1
9 0 1 255 3025 7770 6951 2646 462 36 1
10 0 1 511 9330 34105 42525 22827 5880 750 45 1
0 1 2 3 4 5 6 7 8 9 10
Bell numbers . \ud835\udc35\ud835\udc5b is the number of partitions of \ud835\udc5b elements. \ud835\udc350, . . . = 1, 1, 2, 5, 15, 52, 203, 877, . . .
\ud835\udc35\ud835\udc5b+1 =
\u2211\ufe00\ud835\udc5b
\ud835\udc58=0
(\ufe00
\ud835\udc5b
\ud835\udc58
)\ufe00
\ud835\udc35\ud835\udc58 =
\u2211\ufe00\ud835\udc5b+1
\ud835\udc58=1 \ud835\udc46\ud835\udc5b,\ud835\udc58. Bell triangle: \ud835\udc35\ud835\udc5f = \ud835\udc4e\ud835\udc5f,1 = \ud835\udc4e\ud835\udc5f\u22121,\ud835\udc5f\u22121, \ud835\udc4e\ud835\udc5f,\ud835\udc50 = \ud835\udc4e\ud835\udc5f\u22121,\ud835\udc50\u22121 + \ud835\udc4e\ud835\udc5f,\ud835\udc50\u22121.
Eulerian numbers . \ud835\udc38(\ud835\udc5b, \ud835\udc58) =
\u27e8\ufe00
\ud835\udc5b
\ud835\udc58
\u27e9\ufe00
is the number of permutations with exactly \ud835\udc58 descents (\ud835\udc56 : \ud835\udf0b\ud835\udc56 <
\ud835\udf0b\ud835\udc56+1) / ascents (\ud835\udf0b\ud835\udc56 > \ud835\udf0b\ud835\udc56+1) / excedances (\ud835\udf0b\ud835\udc56 > \ud835\udc56) / \ud835\udc58 + 1 weak excedances (\ud835\udf0b\ud835\udc56 \u2265 \ud835\udc56).
Formula: \ud835\udc38(\ud835\udc5b,\ud835\udc5a) = (\ud835\udc5a + 1)\ud835\udc38(\ud835\udc5b \u2212 1,\ud835\udc5a) + (\ud835\udc5b \u2212 \ud835\udc5a)\ud835\udc38(\ud835\udc5b \u2212 1,\ud835\udc5a \u2212 1). \ud835\udc38(\ud835\udc5b, 0) = \ud835\udc38(\ud835\udc5b, \ud835\udc5b=1) = 1.
\ud835\udc38(\ud835\udc5b,\ud835\udc5a) =
\u2211\ufe00\ud835\udc5a
\ud835\udc58=0(\u22121)\ud835\udc58
(\ufe00
\ud835\udc5b+1
\ud835\udc58
)\ufe00
(\ud835\udc5a + 1\u2212 \ud835\udc58)\ud835\udc5b.
Double factorial . Permutations of the multiset {1, 1, 2, 3, . . . \ud835\udc5b, \ud835\udc5b} such that for each \ud835\udc58, all the num-
bers between two occurrences of \ud835\udc58 in the permutation are greater than \ud835\udc58. (2\ud835\udc5b\u22121)!! = \u220f\ufe00\ud835\udc5b\ud835\udc58=1 (2\ud835\udc58 \u2212 1).
Eulerian numbers of 2\ud835\udc5b\ud835\udc51 kind . Related to Double factorial, number of all such permutations
that have exactly \ud835\udc5a ascents.
\u27e8\ufe00\u27e8\ufe00
\ud835\udc5b
\ud835\udc5a
\u27e9\ufe00\u27e9\ufe00
= (2\ud835\udc5b\u2212\ud835\udc5a\u2212 1) \u27e8\ufe00\u27e8\ufe00 \ud835\udc5b\u22121
\ud835\udc5a\u22121
\u27e9\ufe00\u27e9\ufe00
+ (\ud835\udc5a + 1)
\u27e8\ufe00\u27e8\ufe00
\ud835\udc5b\u22121
\ud835\udc5a
\u27e9\ufe00\u27e9\ufe00
.
\u27e8\ufe00\u27e8\ufe00
\ud835\udc5b
0
\u27e9\ufe00\u27e9\ufe00
= 1
Multinomial theorem . (\ud835\udc4e1 + · · ·+ \ud835\udc4e\ud835\udc58)\ud835\udc5b =
\u2211\ufe00(\ufe00 \ud835\udc5b
\ud835\udc5b1,...,\ud835\udc5b\ud835\udc58
)\ufe00
\ud835\udc4e\ud835\udc5b11 . . . \ud835\udc4e
\ud835\udc5b\ud835\udc58
\ud835\udc58 , where \ud835\udc5b\ud835\udc56 \u2265 0 and
\u2211\ufe00
\ud835\udc5b\ud835\udc56 = \ud835\udc5b.(\ufe00
\ud835\udc5b
\ud835\udc5b1,...,\ud835\udc5b\ud835\udc58
)\ufe00
= \ud835\udc40(\ud835\udc5b1, . . . , \ud835\udc5b\ud835\udc58) =
\ud835\udc5b!
\ud835\udc5b1!...\ud835\udc5b\ud835\udc58!
. \ud835\udc40(\ud835\udc4e, . . . , \ud835\udc4f, \ud835\udc50, . . . ) = \ud835\udc40(\ud835\udc4e + · · ·+ \ud835\udc4f, \ud835\udc50, . . . )\ud835\udc40(\ud835\udc4e, . . . , \ud835\udc4f)
Necklaces and bracelets Necklace of length \ud835\udc5b is an equivalence class of n-character strings over an
alphabet of size \ud835\udc58, taking all rotations as equivalent. Number of necklases: \ud835\udc41\ud835\udc58(\ud835\udc5b) =
1
\ud835\udc5b
\u2211\ufe00
\ud835\udc51|\ud835\udc5b \ud835\udf19(\ud835\udc51)\ud835\udc58
\ud835\udc5b/\ud835\udc51
Bracelet is a necklace such that strings may also be equivalent under re\ufb02ection. Number of bracelets:
\ud835\udc35\ud835\udc58(\ud835\udc5b) =
{\ufe03
1
2
\ud835\udc41\ud835\udc58(\ud835\udc5b) +
1
4
(\ud835\udc58 + 1)\ud835\udc58\ud835\udc5b/2 if \ud835\udc5b is even
1
2
\ud835\udc41\ud835\udc58(\ud835\udc5b) +
1
2
\ud835\udc58(\ud835\udc5b+1)/2 if \ud835\udc5b is odd
An aperiodic necklace of length \ud835\udc5b is an equivalence class of size \ud835\udc5b, i.e., no two distinct rotations of a
necklace from such class are equal. Number of aperiodic necklaces: \ud835\udc40\ud835\udc58(\ud835\udc5b) =
1
\ud835\udc5b
\u2211\ufe00
\ud835\udc51|\ud835\udc5b \ud835\udf07(\ud835\udc51)\ud835\udc58
\ud835\udc5b/\ud835\udc51
.