---
# System prepended metadata

title: CodeBook

---

# CodeBook
![](https://i.imgur.com/76yBCt7.png)
**_for CCU_Melody_**

## 注意事項
- 編譯參數
    -std=c++11 -Wall -Wextra -Wshadow
- 每一題都小心讀，注意 IO 格式跟限制
- 放輕鬆，不要急，多產幾組測資再丟
- 範測一定要過，多產幾組極端測資，像 input 上下限，特殊 cases: 0,1,-1,空集合等等
- int 都開 long long
	- max int ≒ 2 * 10^9^
	- max long long ≒ 10^19^
- stack size
- 不要每層迴圈都跑strlen()，先存到變數再做
- Bus error:有scanf、fgets 但是卻沒東⻄可以讀取了！可能有 early termination但是時機不對。
- 兩個人一起打一起看，不要一個人自己刻
- submit 後就影印 3 份
- 測機的時候要測影印機
- 模板
	```cpp=
	#include <bits/stdc++.h>
	using namespace std;
	typedef long long ii; // 固定ii
	const int INF = 0x3f3f3f3f;// ⼤寫
	```
- Limit :
	- Time Limited 一秒跑 10萬(10^5^) * O(1)次.
	- 陣列最多開50萬(5 * 10^5^)的int.
	- 遞迴深度 : (待補)
- 無限大 : INF or 0x3f3f3f3f or INT_MAX.


## Useful tool
### sort
```cpp=
sort(beg, end); // 由⼩排到⼤
sort(arr, arr + 5, greater<int>()); // 將 arr 由⼤排到⼩
sort(beg, end, cmp);  // cmp 回傳為false時，要交換
```

### fill && memset
```cpp=
fill(beg, end, number);
void *memset(void *str, int c, size_t n);
memset(arr, 0, sizeof(arr));
```

### lower_bound && upper_bound
```cpp=
lower_bound(起始位址, 結束位址, 要搜尋的number);
lower_bound(要搜尋的number);
//返回一個非遞減减序列[first, last)中的第一個大於等於值val的位置
upper_bound(起始位址, 結束位址, 要搜尋的numbe);
upper_bound(要搜尋的number);
//返回一個非遞減减序列[first, last)中的第一個大於val的位置。
```

### vector+Priority_queue
```cpp=
vec.push_back()	//新增元素至 vector 的尾端
vec.pop_back()	//刪除 vector 最尾端的元素。
vec.insert(位址, num)	//插入一個或多個元素至 vector 內的任意位置。
vec.erase(位址) or vec.erase(beg, end)	//刪除 vector 中一個或多個元素。
vec.clear()	//清空所有元素。
vec.empty()	//如果 vector 內部為空，則傳回 true 值。
vec.size()	//取得 vector 目前持有的元素個數。
vec.begin()	//回傳一個 iterator，它指向 vector 第一個元素。
vec.end()	//回傳最尾端元素的下一個位置（請注意：它不是最末元素）
```
```cpp=
// 最大的優先取出
priority_queue<int> 
priority_queue<int,vector<int>,less<int> >

// 最小的優先取出
priority_queue<int,vector<int>,greater<int> >
```

### pair
```cpp=
pair<int, double> p1;
p1 = make_pair(1, 1.2);
p1.first = 1;  p1.second = 1.2;
// vector + pair
vector<pair<int, int>> data;
```

### map
Search 和 insert 操作很快 (O(logn))
```cpp=
map<string, string> Student;
Student.insert(pair<string, string>("r000", "student_zero"));
Student["r123"] = "student_first";
iter = Student.find("r123");
Student.erase(iter);
int n = Student.erase("r123");//如果刪除了會返回1，否則返回0
Student.clear(); //清空全部
Student.empty(); //回傳 true 則 map 為空
```

### sprintf
可以達到itoa()效果
```cpp=
int sprintf(char* str, const char* format, ...); //回傳字串長度
n=sprintf(buffer, "%d plus %d is %d", a, b, a+b); //a=5, b=3
//buffer = "5 plus 3 is 8", n = 13
```

## Useful Code
### Leap year O(1)
```cpp=
(year % 400 == 0 || (year % 4 == 0 && year % 100 != 0))
```

### Fast Exponentiation O(log(exp)) 快速冪
Fermat’s little theorem: 若 p 是質數,則 a^(p-1) ≡ 1 (mod p)
```cpp=
ll fast_pow(ll a, ll b, ll P) {
	// b %= (P - 1)
	ll ans = 1;
	ll base = a % P;
	while (b) {
		if (b & 1)
			ans = ans * base % P;
		base = base * base % P;
		b >>= 1;
	}
	return ans;
}
```

### Mod Inverse O(logn)
- Case 1: gcd(a;m) = 1: ax + my = gcd(a, m) = 1 (use ext_gcd)
- Case 2: p is prime: a^(p-2) ≡ a^(-1) mod p

### GCD O(log(min(a + b)))
注意負數的 case! C++ 是看被除數決定正負號的。
```cpp=
ll gcd(ll a, ll b){
    return b == 0 ? a : gcd(b, a % b);
}
```

### Extended Euclidean Algorithm GCD O(log(min(a + b)))
Bezout identity ax + by = gcd(a, b), where |x|<=b/d and |y|<=a/d
```cpp=
ll extgcd(ll a, ll b, ll& x, ll&y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    else {
        ll d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
        return d;
    }
}
```

### Prime Generator O(nloglogn) 質數表
```cpp=
const ll MAX_NUM = 1e6; // 要是合數
bool is_prime[MAX_NUM];
vector<ll> primes;
void init_primes() {
    fill(is_prime, is_prime + MAX_NUM, true);
    is_prime[0] = is_prime[1] = false;
    for (ll i = 2; i < MAX_NUM; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (ll j = i * i; j < MAX_NUM; j += i)
                is_prime[j] = false;
        }
    }
}
```

### Binary Search
懶得刻就用lower_bound
```cpp=
int right=n-1,left=0,mid;
while(right>left){
	mid=right+(left-right)/2;
	if(x[mid]<=a) left=mid+1;
	else right=mid-1;
}
printf("%d\n",right);
```

### The 3n+1 problem
```cpp=
maxr=1;
who=1;
for (i=2;i<=100000;i++){
	p=i;
	round=1;
	while (p>1) {
		round++;
		if(p&1) {round++; p+=(p>>1)+1;}
		else p>>=1;
	}
	if (round>maxr){maxr=round; who=i;}
	x[i]=maxr;
}
for (i=100000;i<=1000000;i++) {
	p=i;
	round=0;
	while (p>=100000) {
		round++;
		if (p&1) {round++; p+=(p>>1)+1;}
		else p>>=1;
	}
	round+=x[p];
	if (round>maxr) {maxr=round; who=i;}
}
```

## Math
1. Euclid’s formula (Pythagorean Triples)
a = p^2^ -q^2^
b = 2pq (always even)
c = p^2^ + q^2^
2. Difference between two consecutive numbers’ square is odd
(k + 1)^2^ − k^2^ = 2k + 1
3. Summation
![](https://i.imgur.com/jsdoa3D.png)
4. 2-Circle relations
d = 圓心距, R, r 為半徑(R _ r)
內切: d = R - r
外切: d = R + r
內離: d < R – r

## Graph
### Dijkstra's Algorithm + Priority Queue
==**不可以有負權重**==
```cpp=
struct Node {int b, d;};
bool operator<(Node n1, Node n2) {return n1.d > n2.d;}
int w[n][n];    // adjacency matrix
int d[n];
int parent[n];
bool visit[n];
void dijkstra_with_priority_queue(int source){
    fill(visit, visit + n, false);
    fill(d, d+n, INF);
    priority_queue<Node> pq;
    d[source] = 0;
    parent[source] = source;
    pq.push((Node){source, d[source]});
    for (int i=0; i<n; i++){ // 找出下一個要加入到最短路徑樹的點。
        int a = -1;
        while (!pq.empty() && visit[a = pq.top().b])
            pq.pop();   // 最後少pop一次，不過無妨。
        if (a == -1) break;
        visit[a] = true;
        for (int b=0; b<n; b++)
            if (!visit[b] && d[a] + w[a][b] < d[b]){
                d[b] = d[a] + w[a][b];
                parent[b] = a;
                // 交由Priority Queue比較大小
                pq.push( (Node){b, d[b]} );
            }
    }
}
```
### Bellman Ford(有負環的最短路徑)
```cpp=
struct Edge{
	int from, to, cost;
};
const int MAX_V = ...;
const int MAX_E = ...;
const int INF = 0x3f3f3f3f;
int V, E;
Edge edges[MAX_E];
int d[MAX_V];
bool bellman_ford(){
	fill(d, d + V, INF);
	d[0] = 0;
	for (int i = 0; i < V; i++){
		for (int j = 0; j < E; j++){
			Edge &e = edges[j];
			if (d[e.to] > d[e.from] + e.cost) {
				d[e.to] = d[e.from] + e.cost;
				if (i == V - 1) // negative cycle
					return true;
			}
		}
	}
	return false;
}
```

### 偵測負環
```cpp=
vector<Edge> G;// Edge: int from, to, cost
bool find_negative_loop()
{
	int d[2500];
	memset(d, 0, sizeof(d));
	for(int i=0; i < N; ++i){
		for(int j=0; j<G.size(); ++j){
			Edge e = G[j];
			if(d[e.to] > d[e.from] + e.cost){
				d[e.to] = d[e.from] + e.cost;
				if(i == N-1) return 1;
			}
		}
	}
	return 0;
}
```

### SPFA
```cpp=
typedef pair<int, int> ii;
vector<ii> g[N];
bool SPFA(){
	vector<ll> d(n, INT_MAX);
	d[0] = 0; // origin
	queue<int> q;
	vector<bool> inqueue(n, false);
	vector<int> cnt(n, 0);
	q.push(0);
	cnt[0]++;
	while(q.empty() == false){
		int u = q.front();
		q.pop();
		inqueue[u] = false;
		for(auto i : g[u]){
			int v = i.first, w = i.second;
			if(d[u] + w < d[v]){
				d[v] = d[u] + w;
				if(inqueue[v] == false){
					q.push(v);
					inqueue[v] = true;
					cnt[v]++;
					if(cnt[v] == n) return true;
				}
			}
		}
	}
	return false;
}
```

### Minimum Spanning Tree
#### Kruskal
```cpp=
const int V = 100, E = 1000;
struct Edge {int a, b, c;} e[E];    // edge list
bool operator<(Edge e1, Edge e2) {return e1.c < e2.c;}
// disjoint-sets forest
int p[V];
int init() {for (int i=0; i<V; ++i) p[i] = i;}
int find(int x) {return x == p[x] ? x : (p[x] = find(p[x]));}
void union(int x, int y) {p[find(x)] = find(y);}
void Kruskal(){
    init();
    // 圖上所有邊，依照權重大小，由小到大排序。
    sort(edge, edge+E); // O(NlogN)
    // 依序找出最小生成樹上的V-1條邊。
    int i, j;
    for (i = 0, j = 0; i < V-1 && j < E; ++i){
        // 產生環，則捨棄。直到產生橋。
        while (find(e[j].a) == find(e[j].b)) j++;
        // 產生橋，則以此邊連接兩棵MSS。
        union(e[j].a, e[j].b);
        // 印出最小生成樹（森林）上的邊。
        cout << "起點：" << e[j].a
             << "終點：" << e[j].b
             << "權重：" << e[j].c;
        j++;    // 別忘記累計索引值。也可以寫入迴圈。
    }
    if (i == V-1) cout << "得到最小生成樹";
    else          cout << "得到最小生成森林";
}
```

#### Prim
```cpp=
int ans = 0;
bool used[n];
memset(used, false, sizeof(used));
priority_queue<ii, vector<ii>, greater<ii>> pq;
pq.push(ii(0, 0)); // push (0, origin)
while (!pq.empty()){
	ii cur = pq.top();
	pq.pop();
	int u = cur.second;
	if (used[u])
		continue;
	ans += cur.first;
	used[u] = true;
	for (int i = 0; i < (int)g[u].size(); i++){
		int v = g[u][i].first, w=g[u][i].second;
		if (used[v] == false)
			pq.push(ii(w, v));
	}
}
```

### Euler Path
- 每個邊只能走一次，要走完所有的邊
- 所有點的degree(與點相鄰的邊的數量)都是偶數，或有兩個點的是基數，這兩個點必須分別是出發點和終點。

### BFS
```cpp=
bool adj[n][n]; // 一張圖，資料結構為adjacency matrix。
bool visit[n];  // 記錄圖上的點是否遍歷過，有遍歷過為true。
void BFS(){
    queue<int> q; // 建立一個queue。
    for (int i=0; i<n; i++) // 全部的點都初始化為尚未遍歷
        visit[i] = false;
    for (int k=0; k<n; k++)
        if (!visit[k]){
            q.push(k); // 一、把起點放入queue。
            visit[k] = true;
            // 二、重複下述兩點，直到queue裡面沒有東西為止：
            while (!q.empty()){
                // 甲、從queue當中取出一點。
                int i = q.front(); q.pop();
                // 乙、找出跟此點相鄰的點，並且尚未遍歷的點，
                //     依照編號順序通通放入queue。
                for (int j=0; j<n; j++)
                    if (adj[i][j] && !visit[j]){
                        q.push(j);
                        visit[j] = true;
                    }
            }
        }
}
```

### DFS
```cpp=
bool adj[n][n];
bool visit[n];
void DFS(int i){
    if (visit[i]) return;
    visit[i] = true;
    for (int j=0; j<n; j++)
        if (adj[i][j])
            DFS(j);
}
void traversal(){
    fill(visit, visit + n, false);
    for (int i=0; i < n; i++)
        DFS(i);
}
```

### Tree diameter
Time complexity = O(n).
```cpp=
bool adj[9][9];
int diameter = 0;
int DFS(int x, int px){  // px是x的父親
    int h1 = 0, h2 = 0; // 記錄最高與次高的高度
    for (int y=0; y<9; ++y)
        if (adj[x][y] && y != px){
            int h = DFS(y, x) + 1;
            if (h > h1) h2 = h1, h1 = h;
            else if (h > h2) h2 = h;
        }
    diameter = max(diameter, h1 + h2);
    return h1;
}
void tree_diameter(){
    diameter = 0;   // 初始化
    int root = 0;   // 隨便選一個樹根
    DFS(root, root);
    cout << "樹的直徑是" << diameter;
}
```

### Union Find
```cpp=
const int MAX_N = 20000; // 記得改
struct UFDS{
	int par[MAX_N];
	void init(int n){
		memset(par, -1, sizeof(int) * n);
	}
	int root(int x){
		return par[x] < 0 ? x : par[x] = root(par[x]);
	}
	void merge(int x, int y){
		x = root(x);
		y = root(y);
		if (x != y){
			if (par[x] > par[y])
				swap(x, y);
			par[x] += par[y];
			par[y] = x;
		}
	}
};
```

### Max Flow
```cpp=
struct Edge{
	int to, cap, rev;
	Edge(int a, int b, int c){
		to = a;
		cap = b;
		rev = c;
	}
};
const int INF = 0x3f3f3f3f;
const int MAX_V = 20000 + 10;
// vector<Edge> g[MAX_V];
vector<vector<Edge>> g(MAX_V);
int level[MAX_V];
int iter[MAX_V];
inline void add_edge(int u, int v, int cap){
	g[u].push_back((Edge){v, cap, (int)g[v].size()});
	g[v].push_back((Edge){u, 0, (int)g[u].size() - 1});
}
void bfs(int s){
	memset(level, -1, sizeof(level)); //用 fill
	queue<int> q;
	level[s] = 0;
	q.push(s);
	while (!q.empty()){
		int v = q.front();
		q.pop();
		for (int i = 0; i < int(g[v].size()); i++){
			const Edge &e = g[v][i];
			if (e.cap > 0 && level[e.to] < 0){
				level[e.to] = level[v] + 1;
				q.push(e.to);
			}
		}
	}
}
int dfs(int v, int t, int f){
	if (v == t)
		return f;
	for (int &i = iter[v]; i < int(g[v].size()); i++){ // & 很重要
		Edge &e = g[v][i];
		if (e.cap > 0 && level[v] < level[e.to]){
			int d = dfs(e.to, t, min(f, e.cap));
			if (d > 0){
				e.cap -= d;
				g[e.to][e.rev].cap += d;
				return d;
			}
		}
	}
	return 0;
}
int max_flow(int s, int t){ // dinic
	int flow = 0;
	for (;;){
		bfs(s);
		if (level[t] < 0)
			return flow;
		memset(iter, 0, sizeof(iter));
		int f;
		while ((f = dfs(s, t, INF)) > 0)
			flow += f;
	}
}
```

### Bipartite Matching, Unweighted
最大匹配數:最大匹配的匹配邊的數目
最小點覆蓋數:選取最少的點,使任意一條邊至少有一個端點被選擇
最大獨立數:選取最多的點,使任意所選兩點均不相連
最小路徑覆蓋數:對於一個 DAG(有向無環圖),選取最少條路徑,使得每個頂點屬於且僅屬於一條路徑。路徑長可以為0(即單個點)
1. 最大匹配數 = 最小點覆蓋數(這是 Konig 定理)
2. 最大匹配數 = 最大獨立數
3. 最小路徑覆蓋數 = 頂點數 - 最大匹配數

```cpp=
const int MAX_V = ...;
int V;
vector<int> g[MAX_V];
int match[MAX_V];
bool used[MAX_V];
void add_edge(int u, int v){
	g[u].push_back(v);
	g[v].push_back(u);
}
// 回傳有無找到從 v 出發的增廣路徑
//(首尾都為未匹配點的交錯路徑)
// [待確認] 每次遞迴都找一個末匹配點 v 及匹配點 u
bool dfs(int v){
	used[v] = true;
	for (size_t i = 0; i < g[v].size(); i++){
		int u = g[v][i], w = match[u];
		// 尚未配對或可從w 找到增廣路徑(即路徑繼續增長)
		if (w < 0 || (!used[w] && dfs(w))){
			// 交錯配對
			match[v] = u;
			match[u] = v;
			return true;
		}
	}
	return false;
}
int bipartite_matching(){ //匈牙利演算法
	int res = 0;
	memset(match, -1, sizeof(match));
	for (int v = 0; v < V; v++){
		if (match[v] == -1){
			memset(used, false, sizeof(used));
			if (dfs(v))
				res++;
		}
	}
}
```


## DP
### 切棍子
```cpp=
int dp[55][55];
int cut(int,int,int[]);
int cut(int l,int r,int x[]){
    if(dp[l][r]!=-1)return dp[l][r];
    else if(r-l==1)return dp[l][r]=0;
    int m=INT_MAX,i;
    for(i=l+1;i<r;i++)
        m=min(m,cut(l,i,x)+cut(i,r,x)+x[r]-x[l]);
    return dp[l][r]=m;
}
```

### 一維背包
- 無法得知每種放了幾個。
- 有的可以加自己有的不行，這裡要稍微注意一下，不行的話要由後往前讀來避免重複加到，反之需要重複加來組合的就需要由前往後讀。
```cpp=
const int N = 100, W = 100000;
int cost[N], weight[N];
int c[W + 1];   // 一條陣列就夠了
void knapsack(int n, int w){
    memset(c, 0, sizeof(c));
    for (int i = 0; i < n; ++i)
        for (int j = w; j - weight[i] >= 0; --j)    // 由後往前
            c[j] = max(c[j], c[j - weight[i]] + cost[i]);
    cout << "最高的價值為" << c[w];
}
```

### 最長單調子序列(LCS)
都在上面死兩次了，怎麼也得放進來
```cpp=
const int n1 = 7, n2 = 5;
// 為了實作方便，從陣列的第1格開始存入序列。
int s1[7+1] = {0, 2, 5, 7, 9, 3, 1, 2};
int s2[5+1] = {0, 3, 5, 3, 2, 8};
int length[7+1][5+1];   // DP表格
int prev[7+1][5+1]; // 記錄每一格的的結果是從哪一格而來
int lcs[5];
/*
void LCS() // 只求長度，就用這個
{
    // 初始化：當s1或s2是空集合，則LCS是空集合。
    // length[x][0] = length[0][x] = 0;
    for (int i=0; i<=n1; i++) length[i][0] = 0;
    for (int j=0; j<=n2; j++) length[0][j] = 0;
    // 填表格：依照遞迴公式
    for (int i=1; i<=n1; i++)
        for (int j=1; j<=n2; j++)
            if (s1[i] == s2[j])
                // +1是因為e1的長度為1
                length[i][j] = length[i-1][j-1] + 1;
            else
                length[i][j] = max(length[i-1][j],
                                   length[i][j-1]);
    cout << "LCS的長度是" << length[n1][n2];
}
*/
void LCS()
{
    for (int i=0; i<=n1; i++) length[i][0] = 0;
    for (int j=0; j<=n2; j++) length[0][j] = 0;
    for (int i=1; i<=n1; i++)
        for (int j=1; j<=n2; j++)
            if (s1[i] == s2[j]){
                length[i][j] = length[i-1][j-1] + 1;
                prev[i][j] = 0; // 左上方
            }
            else{
                if (length[i-1][j] < length[i][j-1]){
                    length[i][j] = length[i][j-1];
                    prev[i][j] = 1; // 左方
                }
                else{
                    length[i][j] = length[i-1][j];
                    prev[i][j] = 2; // 上方
                }
            }
    cout << "LCS的長度是" << length[n1][n2];
    cout << "LCS是";
    print_LCS(n1, n2);
}
// 迴圈版本，但是順序會顛倒。
// 暫時儲存於陣列，之後再依序印出。
void print_LCS(int i, int j){
    int l = length[i][j];           // LCS長度
    while (l > 0)
        if (prev[i][j] == 0)        // 左上方
            lcs[--l] = s1[i];
        else if (prev[i][j] == 1)   // 左方
            j--;
        else if (prev[i][j] == 2)   // 上方
            i--;
    l = length[i][j];
    for (int i=0; i<l; ++i)
        cout << lcs[i];
}
```

### LIS(遞增) && LDS(遞減)
LDS : 第11行小於改成大於
```cpp=
int s[5];       // sequence
int length[5];  // 第 x 格的值為 s[0...x] 的 LIS 長度
void LIS(){
    // 初始化。每一個數字本身就是長度為一的 LIS。
    for (int i=0; i<5; i++) length[i] = 1;
    for (int i=0; i<5; i++)
        // 找出 s[i] 能接在哪些數字後面，
        // 若是可以接，長度就增加。
        for (int j=0; j<i; j++)
            if (s[j] < s[i]) // LDS: 小於改成大於
                length[i] = max(length[i], length[j] + 1);
    // length[] 之中最大的值即為 LIS 的長度。
    int n = 0;
    for (int i=0; i<5; i++)
        n = max(n, length[i]);
    cout << "LIS的長度是" << n;
}
```

### 換零錢
```cpp=
int dp[15005]={1}/*每種金額有幾種組合方法*/,d[4]={1,5,10,50}/*幣值種類*/;
int n;  
for(int i=0;i<4;i++) 
    for(int j=d[i];j<=15000;j++)
		dp[j]=dp[j]+dp[j-d[i]];
} 
scanf("%d",&n);  
printf("金額為%d共有%d種換法\n",n,dp[n]); 
```

### 數字組合(含不同排列組合)
```cpp=
int dp[n+1];
memset(dp,0,sizeof(dp));
dp[0]=1;
for(j=1;j<=n;j++)
	for(i=1;i<=3;i++)
		if(j>=i)  dp[j]=dp[j]+dp[j-i];
printf("%d\n",dp[n]);//輸出數字n有多少總組合，比如n=3，(2,1)(1,2)算兩種
```

### Floyd Warshall
可以有負權重
對角線 = 0, 其他為無限大
```cpp=
for (int k = 0; k < N; k++)
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
```

### interval max sum(總和最大的連續子序列)
一串數列，找總和最大的連續子序列，eg. List = {-2, -5, 6, -2, -3, 1, 5, -6}, ans = {6, -2, -3, 1, 5}
```cpp=
int maxCrossingSum(int arr[], int l, int m, int h) 
{
	int sum = 0; 
	int left_sum = INT_MIN; 
	for (int i = m; i >= l; i--) 
	{ 
		sum = sum + arr[i]; 
		if (sum > left_sum) 
			left_sum = sum; 
	}
	sum = 0; 
	int right_sum = INT_MIN; 
	for (int i = m+1; i <= h; i++) 
	{ 
		sum = sum + arr[i]; 
		if (sum > right_sum) 
			right_sum = sum; 
	}
	// Return sum of elements on left and right of mid
	return left_sum + right_sum;
}
// Returns sum of maxium sum subarray in aa[l..h] 
int maxSubArraySum(int arr[], int l, int h) 
{ 
	if (l == h) // Base Case: Only one element
		return arr[l]; 
	int m = (l + h)/2; // Find middle point

	/* Return maximum of following three possible cases 
	  a)Maximum subarray sum in left half 
	  b)Maximum subarray sum in right half 
	  c)Maximum subarray sum such that the subarray crosses the midpoint
	*/
	return max(maxSubArraySum(arr, l, m), 
			  maxSubArraySum(arr, m+1, h), 
			  maxCrossingSum(arr, l, m, h)); 
}
int main() 
{ 
	int max_sum = maxSubArraySum(arr, 0, n-1);
} 
```

### w_job_schedule
```cpp=
struct Job {
	int start, finish, profit;
};
bool cmp(Job s1, Job s2) { return (s1.finish < s2.finish); }
int latestNonConflict(Job arr[], int i) {
	for (int j = i - 1; j >= 0; j--) {
		if (arr[j].finish <= arr[i - 1].start) return j;
	}
	return -1;
}
int findMaxProfitRec(Job arr[], int n) {
	if (n == 1) return arr[0].profit;
	int inclProf = arr[n - 1].profit;
	int i = latestNonConflict(arr, n);
	if (i != -1) {
		inclProf += findMaxProfitRec(arr, i + 1);
	}
	int exclProf = findMaxProfitRec(arr, n - 1);
	return max(inclProf, exclProf);
}
```

## 數論
### 唯一分解定理
每個大於1的自然數，要麼本身就是質數，要麼可以寫為2個或以上的質數的積，而且這些質因子按大小排列之後，寫法僅有一種方式。

### 費馬小定理
費馬小定理是數論中的一個定理：假如![](https://i.imgur.com/z9SENaW.png)是一個整數，![](https://i.imgur.com/rLxFLKz.png)是一個質數，那麼![](https://i.imgur.com/3vvNF42.png)
是![](https://i.imgur.com/Snn8P5q.png)的倍數，可以表示為![](https://i.imgur.com/64xOl7c.png)，如果![](https://i.imgur.com/z9SENaW.png)不是![](https://i.imgur.com/QXXinkM.png)的倍數，這個定理也可以寫成![](https://i.imgur.com/6GDBTOo.png)。

### 擴展歐基理德求逆元
已知整數a、b，擴展歐幾里得算法可以在求得a、b的最大公因數的同時，能找到整數x、y（其中一個很可能是負數），使它們滿足貝祖等式![](https://i.imgur.com/ZqxOhTF.png)，如果a是負數，可以把問題轉化成![](https://i.imgur.com/JSgNkfB.png)(![](https://i.imgur.com/FS6a4yE.png)為a的絕對值），然後令![](https://i.imgur.com/bv4pRAN.png)。


```cpp=
int gcdEx(int a, int b, int *x, int *y) 
 {
     if(b==0)
     {
         *x = 1,*y = 0;
         return a;
     }
     else
     {
         int r = gcdEx(b, a%b, x, y); /* r = GCD(a, b) = GCD(b, a%b) */
         int t = *x;
         *x = *y;
         *y = t - a/b * *y;
         return r;
     }
 }
```

### 中國餘數定理
![](https://i.imgur.com/wriRamK.png)
```cpp=
typedef long long ll;
struct Item {
	ll m, r;
};
Item extcrt(const vector<Item> &v){
	ll m1 = v[0].m, r1 = v[0].r, x, y;
	for (int i = 1; i < int(v.size()); i++) {
		ll m2 = v[i].m, r2 = v[i].r;
		ll g = extgcd(m1, m2, x, y); // now x = (m/g)^(-1)
		if ((r2 - r1) % g != 0)
			return {-1, -1};
		ll k = (r2 - r1) / g * x % (m2 / g);
		k = (k + m2 / g) % (m2 / g); // for the case k is negative
		ll m = m1 * m2 / g;
		ll r = (m1 * k + r1) % m;
		m1 = m;
		r1 = (r + m) % m; // for the case r is negative
	}
	return (Item) {m1, r1};
}
```

## Vimrc
```=
set background=dark
set nu		#顯示行號
set tabstop=4	#縮排間隔數
set shiftwidth=4	#自動縮排對齊間隔數
set ruler		#右下角游標座標顯示
set cursorline		#光標底線
set backspace=indent,eol,start	#開啟「backspace」鍵的所有功能
set nocompatible		#關閉vim的vi相容模式
filetype indent on	#啟用依照檔案類型，決定自動縮排樣式的功能
set mouse=a	#啟用游標選取
set ai		#自動對齊縮排
set wrap		#自動換行
set cindent		#自動縮排
set incsearch		#加強版搜尋功能
syntax on		#語法高亮
set ft=nasm
set showmatch
set encoding=utf-8
inoremap ( ()<LEFT>
inoremap [ []<LEFT>
inoremap { {<CR>}<LEFT><Esc>O
inoremap " ""<LEFT>
inoremap ' ''<LEFT>
