# CodeBook
**_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
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個或以上的質數的積，而且這些質因子按大小排列之後，寫法僅有一種方式。
### 費馬小定理
費馬小定理是數論中的一個定理：假如是一個整數，是一個質數，那麼
是的倍數，可以表示為，如果不是的倍數，這個定理也可以寫成。
### 擴展歐基理德求逆元
已知整數a、b，擴展歐幾里得算法可以在求得a、b的最大公因數的同時，能找到整數x、y（其中一個很可能是負數），使它們滿足貝祖等式，如果a是負數，可以把問題轉化成(為a的絕對值），然後令。
```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;
}
}
```
### 中國餘數定理
```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>
Sign in with Wallet
Connect another wallet