This is my template for Algorithm Contest

// c11 編譯器選項(xiàng) -std=c++11

// 注意： 當(dāng)設(shè)置為 false 時(shí)，cin 就不能和scanf，sscanf, getchar, fgets等同時(shí)使用。
// 取消cin和cout對(duì)于C語言的流同步 （這時(shí)盡量不要將兩種輸入輸出混合）
ios::sync_with_stdio(false);

// 解除 cin 和 cout 運(yùn)行庫層面的對(duì)數(shù)據(jù)傳輸?shù)哪J(rèn)綁定。由于存在數(shù)據(jù)傳輸?shù)哪J(rèn)綁定， cin 和 cout 在每次操作的時(shí)候（也就是調(diào)用”<<”或者”>>”）都要刷新（調(diào)用flush），這樣增加了IO的負(fù)擔(dān)。通過解除綁定，可提高輸入輸出效率。
// cin構(gòu)造出來就會(huì)調(diào)用cin.tie() 與cout綁定每次格式化輸入都會(huì)調(diào)用cout.flush();導(dǎo)致效率低，可以使用該語句解綁
cin.tie(NULL); 

cout.tie(NULL);

// 求最大值
auto it = max_element(std::begin(cloud), std::end(cloud)); // C++11
min_element同理

表示圓周率：#define PI acos(-1.0)

getline(cin, t) // 用C++讀取一行
    
string b = "chi1 huo1 guo1", a = "1chi1 huo1 guo1";
a.find(b); // 若找到字串返回位置(0開始的索引), 否則返回-1

priority_queue<int> s2; // 默認(rèn)大頂堆
priority_queue<int, vector<int>, greater<int>> s1; // 這里可以設(shè)置成小頂堆

// 底層哈希表（鍵有限制，只能int，string，double等，不能是自己定義的結(jié)構(gòu)體
// 查詢O(1) 修改O(logn)
unordered_map<string, int> ump;

// 底層紅黑樹（鍵無限制）
// 查詢O(logn) 修改O(logn)
map<node, int> mp;

// cout 輸出較大小數(shù)或特別大的數(shù)可能會(huì)輸出科學(xué)計(jì)數(shù)法，這時(shí)前面需要加一個(gè)fixed
cout << fixed << setprecision(6) << n;

// lower表示等于 >=
int r = lower_bound(v.begin(), v.end(), x) - v.end();
// upper表示大于 >
int l = upper_bound(v.begin(), v.end(), y) - v.end();


// multiset 可以插入重復(fù)的數(shù)字，并且保證集合有序 插入和刪除為O(logn), <set>庫
multiset
/* 字符串處理 */
  
注意C++的字符串末尾也會(huì)加\0,但是他會(huì)放在a.size()這個(gè)位置上，所以原則上可以越界到這個(gè)位置
string a;
a = string("1234") // 字符串構(gòu)造函數(shù)
a = string(cnt, '1') //賦值cnt個(gè)1構(gòu)成的字符串給a
  
// i為起始坐標(biāo)（從0開始），len為長度，獲取字串
a.substr(i, len);
// 找子串，存在返回下標(biāo)（0開始），不存在返回-1
a.find("haha");

// cctype中的東西
isalpha('a') // 判斷是否為字母包括大小寫
islower('a') //  判斷是否為小寫字母
isuppper('a') // 判斷是否為大寫字母
isalnum('a') // 判斷是否為大小寫字母或數(shù)字
isblank('a') // 判斷是否為空格或制表符\t
isspace('a') // 判斷是否為 space, \t, \r, \n
char t = tolower('A') // 轉(zhuǎn)換小寫
char t = toupper('a') // 轉(zhuǎn)換為大寫
string n = to_string(123) // 轉(zhuǎn)換為字符串 可以是int float double 等

string str = "123";
int a = stoi(str); // 將字符串轉(zhuǎn)變?yōu)閿?shù)（注意若str是非法的，那么stoi將會(huì)讀取到非數(shù)字為止）
string str2 = "123.4"
double b = stod(str); // 將字符串轉(zhuǎn)變?yōu)閐ouble型，若非法，自動(dòng)截取前面的浮點(diǎn)數(shù)，非法為止，若前面不是數(shù)字或小數(shù)點(diǎn)發(fā)生運(yùn)行錯(cuò)誤，若前面是小數(shù)點(diǎn)會(huì)轉(zhuǎn)化后在前面自動(dòng)補(bǔ)0

// 類似的還有
stof (string to float)
stold (string to long double)
stol (string to long)
stoll (string to long long)
stoul (string to unsigned long)
stoull (string to unsigned long long)

Basic algorithm

前綴異或

由異或性質(zhì)（結(jié)合律）$a \oplus (b \oplus c) = (a \oplus b) \oplus c$, $a \oplus a = 0$, 因此對(duì)于給定的區(qū)間異或假設(shè)我們有一個(gè)前綴異或函數(shù)$f(i)$, 那么對(duì)于區(qū)間$[l, r]$的異或，我們可以得到$Xor(i, j) =f(j) \oplus f(i - 1)$

前綴和

O(1) 對(duì)矩陣求和

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e3 + 5;

int main() {
	int n, m, q, a[N][N], sum[N][N]; cin >> n >> m >> q;
	for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) {
		cin >> a[i][j];
		sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
	}
	while(q --) {
		int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
		cout << sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1] << endl;
	}
}

差分

O(1) 對(duì)矩陣操作 + - * /

#include <iostream>
#include <cstring>
#include <iostream>
using namespace std;

const int N = 1e3 + 5;

int diff[N][N];
// 差分矩陣主要記住insert就行了，相當(dāng)于輸入打標(biāo)記，區(qū)間打標(biāo)記
void insert(int x1, int y1, int x2, int y2, int c) {
	diff[x1][y1] += c, diff[x1][y2 + 1] -= c, diff[x2 + 1][y1] -= c, diff[x2 + 1][y2 + 1] += c;
}

int main() {
	int n, m, q, a[N][N]; cin >> n >> m >> q;
	for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) {
		cin >> a[i][j], insert(i, j, i, j, a[i][j]);
	}
	while(q --) {
		int x1, y1, x2, y2, c; cin >> x1 >> y1 >> x2 >> y2 >> c;
		insert(x1, y1, x2, y2, c);	
	}
	for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++)
		cout << (diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1]) << "\0 \n "[2 * (i != n) + (j != m)];
}

位運(yùn)算

異或

$a \oplus a = 0$

$0 \oplus a = a$

$a \oplus b = b \oplus a$

$a \oplus (b \oplus c) = (a \oplus b) \oplus c$

$a \oplus b = c$ , then $a \oplus c = b$

變量交換

$a = a \oplus b$, $b = a \oplus b$, $a = a \oplus b$

排除重復(fù)里面的不重復(fù)（唯一一個(gè)不重復(fù)的）

對(duì)于任意的$arr[i]$, 進(jìn)行異或，最終得到的結(jié)果便是唯一不重復(fù)的數(shù)字

二分

// 區(qū)間[l, r]被劃分成 [l, mid] 和 [mid + 1, r] 時(shí)
int bsearch(int x) {
  while (l < r) {
    int mid = l + r >> 1;
    if (check(mid)) r = mid;
    else l = mid + 1;
  }
}

// l = mid時(shí)，補(bǔ)上  + 1 （l + r + 1 >> 1)
// 補(bǔ)上加以等同于四舍五入，保證了mid不會(huì)等于l,從而導(dǎo)致l被重復(fù)賦值為l造成死循環(huán)

// 區(qū)間[l, r]被劃分成 [l, mid - 1] 和 [mid, r] 時(shí)
int bsearch(int x) {
  while (l < r) [
    int mid = l + r + 1 >> 1;
    if (check(mid)) l = mid;
    else r = mid - 1;
  ]
}

// 浮點(diǎn)數(shù)二分
const double EPS = 1e-8;

dobule b_search(double n) {
	double l = -1000, r = 1000;
	while (r - l >= EPS) {
		double mid = (l + r) / 2;
		if (mid * mid * mid >= n) r = mid;
		else l = mid;
	}
}

// 也可以直接迭代指定次數(shù)
for (int i = 1; i <= 100; i ++) {
  double mid = (l + r) / 2;
  if (check(mid)) r =  mid;
  else l = mid;
}

Some suffixes

1. Qucikly read for const numbers

#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; i ++)
#define per(i, j, k) for(int i = j; i >= k; i --)
#define lc p<<1
#define rc p<<1|1
#define f first
#define s second
#define pb(x) push_back(x)
#define ll long long
using namespace std;
const int N = 1e7 + 10;
char buf[1 << 21], *p1 = buf, *p2 = buf;
// p1 means start point and p2 means end point
inline char gc(){
    if (p1 == p2){
        // fread return real count
        p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin);
    }
    return *p1 ++;
}
// gc can be replaced by function getchar.
inline int read(){
    int s = 0, w = 1;
    char ch = gc();
    while (ch < '0' || ch > '9'){
        if (ch == '-') w *= - 1;
        ch = gc();
    }
    while ('0' <= ch && ch <= '9'){
        s = (s << 1) + (s << 3) + (ch ^ 48);
        ch = gc();
        return s * w;
    }
}
int main()
{
    int n, t;
    ll sum = 0;
    cin >> n;
    rep (i, 1, n){
        t = read();
        if (i > 1){
            sum ^= t;
        }else{
            sum = t;
        }
    }
    cout << sum;
}

2. Header

#include <iostream>
#include <cstring>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
#include <unordered_set>
#include <unordered_map>
#define INF 0x3f3f3f3f
#define siz(x) (int)x.size()
#define IOS ios::sync_with_stdio(false);
#define rep(i, j, k) for(int i = j; i <= k; ++ i)
#define per(i, j, k) for(int i = j; i >= k; -- i)
#define dbg1(a) cout << a << endl;
#define dbg2(a, b) cout << a << " " <<  b << endl;
#define dbg3(a, b, c) cout << a << " " << b << " " << c << endl;
#define pb(x) push_back(x)
#define eb(x) emplace_back(x)
#define all(x) x.begin(), x.end()
#define f first
#define s second
#define FASTIO                \
    std::ios ::sync_with_stdio(0); \
    std::cin.tie(0);               \
    std::cout.tie(0);
#define lc p<<1
#define rc p<<1|1
using namespace std;
typedef long long LL;
typedef priority_queue<int, vector<int>, greater<int>> S_HEAP;
typedef priority_queue<int> B_HEAP; 
typedef pair<string, int> PSI;
typedef pair<int, int> PII;

const int N = 1e5 + 10;

First : Tree

1. Heap

## Insert Establish
void PushUp(int i){
    if (i == 1) return;
    while (i != 1){
        if (heap[i] < heap[i / 2]) swap(heap[i], heap[i / 2]), i /= 2;
        else break;
    }
}
int n;
for (int i = 1; i <= n; i ++){
	PushUp(i);
}
## Establish via binary tree
void AdjustHeap(int a[], int i, int n){
    for (i = i * 2; i <=n; i *= 2){
        if (i < n && a[i + 1] < a[i]) i ++;
        if (a[i] < a[i / 2]) swap(a[i], a[i / 2]);
        else break;
    }
}
void build(int a[], int p, int n){
    for (int i = n / 2; i >= p; i --){
        AdjustHeap(a, i, n);
    }
}
## Delete root Elements
sawp(a[1], a[len + 1]);
AdjustHeap(a, 1, n - 1)

2. Segment Tree

#include <bits/stdc++.h>
#define rep(i, j, k) for (int i = j; i <= k; i ++)
#define per(i, j, k) for (int i = j; i >= k; i --)
#define ll long long
#define lc p<<1
#define rc p<<1|1
using namespace std;
const int N = 1e5 + 10; 
ll w[N];
struct node{
	ll l, r, sum, add;
}tr[4 * N];
void pushup(int p){
	tr[p].sum = tr[rc].sum + tr[lc].sum;
}
void pushdown(int p){
	if (tr[p].add){
		tr[rc].sum += (tr[rc].r - tr[rc].l + 1) * tr[p].add;
		tr[lc].sum += (tr[lc].r - tr[lc].l + 1) * tr[p].add;
		tr[lc].add += tr[p].add;
		tr[rc].add += tr[p].add;
		tr[p].add = 0;
	}
}
void build(int p, int l, int r){
	tr[p] = {l, r, w[l], 0};
	if (l == r) return;
	int m = l + r >> 1;
	build(lc, l, m);
	build(rc, m + 1, r);
	pushup(p);
}
void update(int p, int l, int r, int k){
	if (tr[p].l >= l && tr[p].r <= r){
		tr[p].sum += (tr[p].r - tr[p].l + 1) * k;
		tr[p].add += k;
		return;
	}
	int m = tr[p].l + tr[p].r >> 1;
	pushdown(p);
	if (l <= m) update(lc, l, r, k);
	if (r > m) update(rc, l, r, k);
	pushup(p);
}
ll query(int p, int l, int r){
	if (tr[p].l >= l && tr[p].r <= r)
		return tr[p].sum;
	int m = tr[p].l + tr[p].r >> 1;
	ll sum = 0;
	pushdown(p);
	if (l <= m) sum += query(lc, l, r);
	if (r > m) sum += query(rc, l, r);
	return sum;
}
int main()
{
	int n, m;
	cin >> n >> m;
	rep (i, 1, n){
		cin >> w[i];
	}
	build(1, 1, n);
	rep (i, 1, m){
		int c, x, y, z;
		cin >> c;
		if (c == 1){
			cin >> x >> y >> z;
			update(1, x, y, z);
		}
		else{
			cin >> x >> y;
			cout << query(1, x, y) << endl;
		}
	}
}
## lazytag

3. Cartesian Tree

For the best description about Cartesian Tree. The first time I read about it was sophisticated to understand.

Cartesian Tree is a tree defined by the BST and the Heap(min), so if the tree is BST and Heap(min), that is a Cartesian Tree.

What about the algorithm?

Look it at OIWIKI.

#include <bits/stdc++.h>
#include <cmath>
#define f first
#define s second
#define pb(x) push_back(x)
#define ll long long
#define pii pair<int, int>  
#define psi pair<string, int>
#define rep(i, j, k) for (int i = j; i <= k; ++ i)
#define per(i, j, k) for (int i = j; i >= k; -- i)
#define lc p<<1
#define rc p<<1|1
using namespace std;
const int N = 100;
int st[N], ls[N], rs[N], q[N], tt, n, a[N];
bool has_fa[N];
void bfs(int root){
	int hh, tt;
	hh = tt = 0;
	q[0] = root;
	while (hh <= tt){
		int t = q[hh ++];
		if (ls[t]) q[ ++ tt] = ls[t];
		if (rs[t]) q[ ++ tt] = rs[t];
		cout << a[t] << " ";
	}
}
int main()
{
	int n;
	cin >> n;
	rep (i, 1, n) cin >> a[i];
	rep (i, 1, n){
		int k = tt;
		while (k > 0 && a[st[k]] > a[i]) k --;
		if (k) rs[st[k]] = i, has_fa[i] = true;
		if (k < tt) ls[i] = st[k + 1], has_fa[st[k + 1]] = true;
		st[++k] = i;
		tt = k;
	}
	int root = 1;
	while (has_fa[root]) root ++;
	bfs(root);
}

Graph

1. Topological sort (Kath)

bool toposort(){
	queue<int> q;
	rep (i, 1, n)
		if (!din[i]) q.push(i);
	while (q.size()){
		int x = q.front(), cnt = 0, tmp[N]; q.pop();
		tp.push_back(x);
		for (auto y : v[x]){
			if (-- din[y] == 0) q.push(y);
		}
	}
	if (tp.size() == n) return 1;
	else return 0;
}

2. Topological sort (DFS)

bool dfs(int x){
	c[x] = -1;
	for (int y : e[x]){
		if (c[y] < 0) return 0;
		else if (!c[y])
			if (!dfs[y]) return 0;
	}
	c[x] = 1;
	tp.push_back(x);
	return 1;
}
bool toposort(){
	memset(c, 0, sizeof(c));
	rep (x, 1, n){
		if (!c[x])
			if (!dfs(x)) return 0;
	}
	reverse(tp.begin(), tp.end());
	return 1;
}

3. Dijkstra (normal)


#include <iostream>
#include <cstring>
#include <vector>
#define f first
#define s second
#define pb(x) push_back(x)
#define rep(i, j, k) for (int i = j; i <= k; ++ i)
#define Inf 0x3f3f3f3f
using namespace std;
const int N = 1e4 + 10;
struct edge{int v, w;};
bool st[N];
int dist[N], pre[N], n, m, s;
vector<edge> g[N];
void dijkstra(int s){
	memset(dist, 0x3f, sizeof(dist));
	dist[s] = 0;
	rep (i, 1, n - 1){
		int u = -1;
		rep (j, 1, n)
			if (!st[j] && (u == -1 || dist[j] < dist[u])) u = j;
		st[u] = 1; 
		for (auto x : g[u]){
			int v = x.v, w = x.w;
			if (dist[v] > dist[u] + w)
				pre[v] = u;
				dist[v] = dist[u] + w;
		}
	}
}
void dfs_path(int u){
	if (u == 1){
		printf("%d", u);
	}
	dfs_path(pre[u]);
	printf("->%d", u);
}
int main()
{
	cin >> n >> m >> s;
	rep(i, 1, m){
		int u, v, w;
		cin >> u  >> v >> w;
		g[u].push_back({v, w});
	}
	dijkstra(s);
	rep (i, 1, n){
		if (dist[i] == Inf) cout << (1<<31) - 1 << " ";
		else cout << dist[i] << " ";
	}
}

4. Dijkstra (Heap)

#include <bits/stdc++.h>
#define pii pair<int, int>
#define f first
#define s second
#define pb(x) push_back(x)
#define rep(i, j, k) for (int i = j; i <= k; ++ i)
#define Inf 0x3f3f3f3f
using namespace std;
const int N = 1e5 + 10;
struct edge{int v, w;};
bool st[N];
int dist[N], pre[N], n, m, s;
vector<edge> g[N];
priority_queue<pii> q;

void dijkstra(int s){
	memset(dist, 0x3f, sizeof(dist));
	dist[s] = 0, q.push({0, s});
	while (q.size()){
		auto t = q.top(); q.pop();
		int u = t.s;
		if (st[u]) continue;
		st[u] = 1;
		for (auto x : g[u]){
			int  v = x.v, w= x.w;
			if (dist[v] > dist[u] + w){
				pre[v] = u;
				dist[v] = dist[u] + w;
				q.push({-dist[v], v});
			}
		}
	}
}
void dfs_path(int u){
	if (u == 1){
		printf("%d", u);
		return;
	}
	dfs_path(pre[u]);
	printf("->%d", u);
}
int main()
{
	cin >> n >> m >> s;
	rep(i, 1, m){
		int u, v, w;
		cin >> u  >> v >> w;
		g[u].push_back({v, w});
	}
	dijkstra(s);
	rep (i, 1, n){
		if (dist[i] == Inf) cout << (1<<31) - 1 << " ";
		else cout << dist[i] << " ";
	}
}

5. Bellman-ford


int bellman_ford(){
	memset(dist, 0x3f, sizeof(dist)); // init data
	dist[1] = 0;
	bool flag;
	rep (i, 1, n){               // n times loop
		flag = false;
		rep (j, 0, m - 1){  	 // then travese all the vertex in the graph
			int a = edges[j].a, b = edges[j].b, w = edges[j].w;
			if (dist[b] < dist[a] + w)          // realex the edge by the other edge
				dist[b] = dist[a] + w, flag = true;
		}
	}
	if (flag) cout << "The graph has negative circle!"; // judge the negative circle
	if (dist[n] > 0x3f3f3f3 / 2) return -1;           // if the vertex can't be reach from source point
	return dist[n];											
}

6. SPFA

dfs_path(int u){
  if (u == 1) {
  	printf("%d", u);
  	return;
  }
  dfs_path(pre[u]);
  printf("->%d", u);
}

bool spfa(int s){
	queue<int> q;
	d[s] = 0, q.push(s), st[s] = 1;
	while (q.size()){
		int x = q.front();
		q.pop(), st[x] = 0;
		for (auto y : e[x]){
			int v = y.v, w = y.w;
			if (d[v] > d[x] + w){
				d[v] = d[x] + w;
				pre[v] = x;
				cnt[v] = cnt[x] + 1;
				if (cnt[v] >= n) return true;  // if the graph has negative circle the func will return true value
				if (!st[v]) q.push(v), st[v] = 1;
			}
		}
	} 
	return false;
}

// if you the source vertex can't reach the negative circle, you should put all the vertex to queue
bool spfa(){
	memset(d, 0x3f, sizeof(d));
    rep(i, 1, n) q.push(i), st[i] = 1;
	while (q.size()){
		int x = q.front();
		q.pop(), st[x] = 0;
		for (auto y : e[x]){
			int v = y.v, w = y.w;
			if (d[v] > d[x] + w){
				d[v] = d[x] + w;
				cnt[v] = cnt[x] + 1;
				if (cnt[v] >= n) return true; // the negative circle is true
				if (!st[v]) q.push(v), st[v] = 1;
			}
		}
	}
	return false; // not have any negative circle
}

7. Floyd

#include <bits/stdc++.h>
#define rep(i, j, k) for (int i = j; i <= k; ++ i)
#define pii pair<int, int>
#define Inf 0x3f3f3f3f
using namespace std;
const int N = 201, M = 1e4 + 10;
int d[N][N], p[N][N], n, m, k;
void floyd(){
	rep (k, 1, n)
		rep (i, 1, n)
			rep (j, 1, n)
				if (d[i][j] < d[i][k] + d[k][j])
					d[i][h] = d[i][k] + d[k][j], path[i][j] = k;
}
void path(int i, int j){
	if (p[i][j] == 0) return;
	int k = p[i][j];
	path(i, k);
	printf("%d->", k);
	path(k, j);
}
int main(){
    cin >> n >> m >> k;
	rep (i, 1, n)
			rep (j, 1, n)
				if (i == j) d[i][j] = 0;
				else d[i][j] = Inf;
	rep (i, 1, m){
		int a, b, c;
		cin >> a >> b >> c;
		d[a][b] = min(d[a][b], c);
	}
	floyd();
	while (k --){
	    int a, b;
		cin >> a >> b;
		if (d[a][b] > Inf / 2) cout << "impossible" << endl;
		else cout << d[a][b] << endl;
	}
	// print the most shortest path
	int a, b;
	cin >> a >> b;
	cout << a << "->";
	path(a, b);
	cout << b << endl;
}

8. Kruskal

#include <bits/stdc++.h>
#define rep(i, j, k) for (int i = j; i <= k; ++ i)
#define pii pair<int, int>
#define Inf 0x3f3f3f3f
using namespace std;
const int N = 5010, M = 1e5 + 10;
int p[N], cnt, n, m, ans;
struct edge{
	int u, v, w;
	bool operator<(const edge &t) const{
		return w < t.w;
	}
}e[4 * M];
int find(int x){
	if (p[x] != x) p[x] = find(p[x]);
	return p[x];
}
bool kruskal(){
	sort(e, e + m);
	rep(i, 1, n) p[i] = i;
	rep (i, 0, m - 1){
		int fa = find(e[i].u), fb = find(e[i].v);
		if (fa != fb){
			p[fa] = fb;
			ans += e[i].w;
			cnt ++;
		}
	}
	return cnt == n - 1;
}
int main(){
	cin >> n >> m;
	int num = 0;
	rep (i, 0, m - 1){
		int a, b, c;
		cin >> a >> b >> c;
		e[num ++] = {a, b, c};
		e[num ++] = {b, a, c};
	}
	m = num;
	if (kruskal()) cout << ans;
	else cout << "orz";
}

9. Prim (normal)

#include <bits/stdc++.h>
#define rep(i, j, k) for (int i = j; i <= k; ++ i)
#define pii pair<int, int>
#define Inf 0x3f3f3f3f
using namespace std;
const int N = 5010, M = 1e5 + 10;
int d[N], st[N], ans, cnt, n, m;
struct edge{int v, w;};
vector<edge> e[N];
bool prim(int s){
	memset(d, 0x3f, sizeof(d));
	d[s] = 0;
	rep (i, 1, n){
		int u = 0;
		rep (j, 1, n)
			if (!st[j] && d[j] < d[u]) u = j;
		st[u] = 1;
		ans += d[u];
		if (d[u] != Inf) cnt ++;
		for (auto y : e[u]){
			int v = y.v, w = y.w;
			if (d[v] > w) d[v] = w;
		}
	}
	return cnt == n;
}
int main(){
	int num = 0;
	cin >> n >> m;
	rep (i, 1, m){
		int a, b, c;
		cin >> a >> b >> c;
		e[a].push_back({b, c});
		e[b].push_back({a, c});
	}
	if (prim(1)) cout << ans;
	else cout << "impossible";
}

10. Prim(Heap)

#include <bits/stdc++.h>
#define s second
#define f first
#define rep(i, j, k) for (int i = j; i <= k; ++ i)
#define pii pair<int, int>
#define Inf 0x3f3f3f3f
using namespace std;
const int N = 5010, M = 1e5 + 10;
int d[N], st[N], ans, cnt, n, m;
struct edge{int v, w;};
vector<edge> e[N];
priority_queue<pii> q;
bool prim(int s){
	memset(d, 0x3f, sizeof(d));
	d[s] = 0, q.push({0, s});
	while (q.size()){
		int u = q.top().s; q.pop();
		if (st[u]) continue;
		st[u] = 1, ans += d[u], cnt ++;
		for (auto y : e[u]){
			int v = y.v, w = y.w;
			if (d[v] > w){
				d[v] = w;
				q.push({-d[v], v});
			}
		}
	}
	return cnt == n;
}
int main(){
	int num = 0;
	cin >> n >> m;
	rep (i, 1, m){
		int a, b, c;
		cin >> a >> b >> c;
		e[a].push_back({b, c});
		e[b].push_back({a, c});
	}
	if (prim(1)) cout << ans;
	else cout << "impossible";
}

11. Dyeing about Bipartite Graph

#include <bits/stdc++.h>
#define s second
#define f first
#define rep(i, j, k) for (int i = j; i <= k; ++ i)
#define pii pair<int, int>
#define Inf 0x3f3f3f3f
using namespace std;
const int N = 1e5 + 10, M = 2 * (1e5 + 10);
int h[N], e[M], ne[M], idx, n, color[N], m;
void add(int a, int b){
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
inline bool dfs(int u, int c){
	color[u] = c;
	for (int i = h[u]; i != -1; i = ne[i]){
		int j = e[i];
		if (color[j] == -1){
			if (!dfs(j, !c)) return false;
		}
		else if (color[j] == c) return false;
	}
	return true;
}
inline bool check(){
	memset(color, -1, sizeof(color));
	bool flag = true;
	rep (i, 1, n){
		if (color[i] == -1){
			if (!dfs(i, 0)){
				flag = false;
				break;
			}
		}
	}
	return flag;
}
int main(){
	memset(h, -1, sizeof(h));
	cin >> n >> m;
	rep (i, 1, m){
		int a, b;
		cin >> a >> b;
		add(a, b);
		add(b, a);
	}
	if (check()) puts("Yes");
	else puts("No");
}

12. Hungarian algorithm

#include <bits/stdc++.h>
#define s second
#define f first
#define rep(i, j, k) for (int i = j; i <= k; ++ i)
#define pii pair<int, int>
#define Inf 0x3f3f3f3f
using namespace std;
const int N = 1e5 + 10, M = 1e5 + 10;
int h[N], e[M], ne[M], match[N], idx, n, m, k, ans;
bool st[N];
void add(int a, int b){
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
bool dfs(int u){
	for (int i = h[u]; i != -1; i = ne[i]){
		int j = e[i];
		if (!st[j]){
			st[j] = true;
			if (!match[j] || dfs(match[j])){
				match[j] = u;
				return true;
			}
		}
	}
	return false;
}
int main(){
	memset(h, -1, sizeof(h));
	cin >> n >> m >> k;
	rep (i, 0, k - 1){
		int a, b;
		cin >> a >> b;
		add(a, b);
	}
	rep (i, 1, n){
		memset(st, 0, sizeof(st));
		if (dfs(i)) ans ++;
	}
	cout << ans;
}

13.DSU

/* DSU + 維護(hù)size + 權(quán)值 */

// init

for(int i = 1; i <= n; i ++) p[i] = i, siz[i] = 1;

// find fuc

int find(int x) {

 if(x != p[x]) {

  int t = find(p[x]);

  d[x] += d[p[x]];

  p[x] = t;

 }

}

// add fuc

void add(int x, int y, int k) {

 if(find(x) != find(y))

  siz[find(y)] += siz[find(x)];

 p[find(x)] = find(y);

 val[find(x)] += -val[x] + val[y] + s;

}

String

1. KMP

#include <bits/stdc++.h>
#include <cstring>
#include <cmath>
#define ll long long
#define f first
#define s second
#define Inf 0x3f3f3f3f
#define NInf -0x3f3f3f3f
#define pii pair<int, int>
#define rep(i, j, k) for(int i = j; i <= k; ++ i)
#define per(i, j, k) for(int i = j; i >= k; -- i)
using namespace std;
const int N = 1e6 + 10;
int ne[N];
void init_kmp(char p[], int m){
	ne[1] = 0;
	for (int i = 2, j = 0; i <= m; ++ i){
		while (j && p[i] != p[j + 1]) j = ne[j];
		if (p[j + 1] == p[i]) j ++;
		ne[i] = j;
	}
}
void kmp(char a[], char p[], int n, int m){
	for (int i = 1, j = 0; i <= n; ++ i){
		while (j && p[j + 1] != a[i]) j = ne[j];
		if (a[i] == p[j + 1]) j ++;
		if (j == m) cout << i - j + 1 << endl;  
	}
}
int getlen(char a[]){
	int i = 1;
	while (a[i]) i ++;
	return i - 1;
}
int main(){
	char a[N], p[N];
	cin >> a + 1 >> p + 1;
	int n = getlen(a), m = getlen(p);
	init_kmp(p, m);
	kmp(a, p, n, m);
	cout << ne[1];
	rep (i, 2, m) cout << " " << ne[i];
}

Math

基本定理

可看，唯一分解定理（算數(shù)基本定理）

$x = p^{a_1} \times p ^{a_2} \times ... \times p^{a_n}$ (p為x的素因子)，該分解式對(duì)于任意的正整數(shù)（$x\ge2$)唯一

約數(shù)個(gè)數(shù)：$\prod \limits_{i = 1}^n (a_i + 1)$

約數(shù)之和：$\prod \limits_{i=1}^n \sum \limits_{j=0}^{a_j} p_i^{j}$

完全平方數(shù)的約數(shù)個(gè)數(shù)為奇數(shù)個(gè)，因?yàn)榧s數(shù)成對(duì)存在，證畢

$[1, n]$的完全平方數(shù)為$\sqrt{n}$個(gè)，顯然這不用證明因?yàn)槊總€(gè)數(shù)都是完全平方數(shù)的約數(shù)

Basic operator

$a\mid b$ ： a能夠整除b， b能夠被a整除

$a \nmid b$ : a不能夠整除b， b不能夠被a整除

帶余數(shù)除法：若a,b時(shí)兩個(gè)整數(shù)，其中b>0，則存在兩個(gè)整數(shù)q及r，使得

$a=bq + r$ 且 $0 \leq r \textless b$ , 且q和r唯一，此處b時(shí)商，r是余數(shù)

(0除以任何不為0的數(shù)都等于0， 0不能作為除數(shù))

模運(yùn)算

$(a + b) \bmod m = (a \bmod m + b \bmod m) \bmod m $

$(a-b) \bmod m = (a \bmod m - b \bmod m) \bmod m$

$(a*b)\bmod m = ((a \bmod m) * (b \bmod m)) \bmod m$

通常為了規(guī)避減法異號(hào)的情況，我們通常這樣操作

$(a-b) \bmod m = ((a \bmod m) - (b \bmod m) + m) \bmod m$

除法的取模需要使用逆元

上取整與下取整

int x = 9, y = 3;
// 上取整
int res = (x - 1) / y ;

// 下取整
int res = x / y;

// 四舍五入
int res = (x + y / 2) / y;


也可以用cmath的庫函數(shù), 但是必須保證傳入為double即 小數(shù)

// 上取整
int res = ceil((x * 1.0) / y);
    
// 下取整
int res = floor((x * 1.0) / y);
    
// 四舍五入
int res = round((x * 1.0) / y);

向上取整證明

預(yù)處理MAXN之前的數(shù)的約數(shù)

void init() {
	for(int i = 1; i <= MAXN; i ++) {
		for(int j = i; j <= MAXN; j += i) {
			factors[j].push_back(i);
		}
	}
}

快速冪

$O(\sqrt{n})$ n為指數(shù)

分治

double fast_pow(double a, int n) {
	if (n == 1) return a;
	double t = fast_pow(a, n / 2);
	if (n % 2 == 1) return t * t * a;
	else return t * t;
}

Bit

$O(logn)$

int fast_pow(double a, int b) {
	double ans = 1;
	while (b) {
		if (b & 1) ans *= a;
		a *= a;
		b>>=1;
	}
	return ans;
}

康托展開

GCD-最大公因數(shù)

GCD and LCM properties

更相損減術(shù)：$\gcd(a,b) = \gcd(b, a-b)$

輾轉(zhuǎn)相除法：$\gcd(a,b) = \gcd(b,a \bmod b)$

證明：$d\mid a, d \mid b$等價(jià)于$d\mid(a-b)$, $d|b$（充要條件）

LCM最小公倍數(shù)： $lcm(a,b) = \frac{a*b}{\gcd(a,b)}$ 常記為 $[a,b]$

可重復(fù)貢獻(xiàn)

$\gcd(a, b, c) = \gcd(\gcd(a, b), c) = \gcd(a, \gcd(b, c))$ （可以推廣到n個(gè)數(shù)的情況）
$\gcd(a, 0) = a$

$\gcd(a, b) = \gcd(a, -b)$
$\gcd(x, x-1) = 1$

LCM的一些性質(zhì):

$lcm(a,b)$, 若a或b為質(zhì)數(shù)，則$lcm(a, b) = a * b$;
$lcm(a,b)$, 若$b \mid a$, 則$lcm(a,b) = a$
$lcm(x, x - 1) = x * (x - 1)$

常用構(gòu)造題:

對(duì)于給定的a, b在某個(gè)區(qū)間, 這里假設(shè)

$l \le a, b\le r$

$lcm(a,ka)$ 使lcm最小
$lcm(a,b)$, $gcd(a,b) = 1$, 使$lcm$最大

證明:

假定$a \le b$,

$b \bmod a = 0$，$lcm(a,b) = b$, $l \le b \le r$
$b \bmod a \ne 0$, $lcm(a,b) \ge 2 * b$ $ie. 2 * l \le lcm \le 2 * r$

輾轉(zhuǎn)相除法

輾轉(zhuǎn)相除法：$\gcd(a,b) = \gcd(b,a \bmod b)$

證明: 描述a與b的帶余數(shù)除法關(guān)系，$a = kb + r$

設(shè)d為a和b的因數(shù), 有$d \mid a$, $d \mid b$, 因?yàn)?span id="w0obha2h00" class="math inline">$r = a - kb$ , 所以 $d|r$,

因此d是$b, r$的公約數(shù)（為什么不寫成$a, r$, 因?yàn)?span id="w0obha2h00" class="math inline">$r = a - kb$ 的因子有可能超出b的因子范圍，如$6 * 5$ 此時(shí)6也可以作為因子，所以為了限制該條件我們用b來作為另一個(gè)數(shù))

因此$gcd(a,b) = gcd(b, a \bmod b)$

int gcd(int a, int b) {return b == 0?a:gcd(b, a % b);}

裴蜀定理

設(shè)a,b是不全為零的整數(shù)，則存在整數(shù)x,y使得 $ax + by = \gcd(a, b)$

（可以理解為，該方程有解，且為最小正元）

LuogP4549

#include <iostream>
#include <vector>
using namespace std;

int gcd(int a, int b) {
	return b == 0?a:gcd(b, a % b);
}

int main() {
	int n, last; cin >> n;
	vector<int> a(n);
	last = 0;
	for (int i = 0; i < a.size(); i ++) {
		cin >> a[i];
		if (a[i]<0) a[i]*=-1;
		last = gcd(last, a[i]);
	}
	cout << last;
}

OIWIKI

Wikipedia

類歐幾里得算法

類似于歐幾里得形式的算法，需要求出f(a,b), 通過變換形式，使問題規(guī)模越來越小，最終求得解。

擴(kuò)展歐幾里得算法

考慮一個(gè)二元一次不定方程: $ax + by = c$ (a, b, c為整數(shù)且a, b都不為0)

定理1: 設(shè)它有整數(shù)解$x = x_0, y = y_0,$則一切整數(shù)解可以寫成$x = x_0 - b_1t, y = y_0 + a_1t,\space(t = 0, 1, -1, 2, -2, ...)$ 其中$b_1 = \frac{a}{\gcd(a, b)}$, $a_1 = $$\frac{\gcd(a,b)}$

證明:

充分性: 已知$ax_0 + by_0 = c,$ 可得$a(x_0 - b_1t) + b(y_0 + a_1t) = ax_0 + by_0 + t(ba_1-ab_1) = ax_0 + by_0 = c$

必要性: 設(shè)$x', y'$是$ax+by=c$的任意解, 則$ax' + by' = c$已知$ax_0 + by_0 =c$兩式相減,得$a(x' - x_0) + b(y' - y_0) = 0$, 除公因數(shù)，得$a_1(x'-x0) = -b_1(y' - y_0)$, 觀察式子, 既然$a_1$與$b_1$互質(zhì)，那么$ a_1 \mid (y'-y_0) $. 可得$y'=y_0 + a_1t$. 同理可得$x'=x_0-b_1t$

定理2：一般式$ax+by = c$ 有整數(shù)解的充要條件是$\gcd(a, b) | c$

證明：

必要性：若有整數(shù)解則$\gcd(a,b)|(ax + by)$, 故$\gcd(a,b)|c$

充分性：若$\gcd(a,b)|c$則由裴蜀定理 $ax+by=\gcd(a,b)$ 一定存在解，則對(duì)其解乘以$\frac{c}{\gcd(a,b)}$ 便為$ax+by=c$的解

因此對(duì)于任給的$ax+by=c$ 且 $\gcd(a,b) \mid c$，則找到了一組特解，便可以得到所有解.

求 $ax_1 + by_1 = \gcd(a, b)$

思路：

求$ax_1+by_1=\gcd(a,b)$, 由于$\gcd(a,b)==\gcd(b, a \bmod b)$,我們可以先求出$bx_2 +(a \bmod b)y_2=\gcd(b, a \bmod b)$的解，再通過找到這兩條式子的解的關(guān)系而得出原式子的解。

關(guān)系：$x_1 = y_2, y_1 = x_2 - \lfloor a/b \rfloor * y_2$

證明：$ax_1 + by_1 = \gcd(a,b) = \gcd(a, a \bmod b) = bx_2 + (a \bmod b)y_2 = bx_2 + (a - \lfloor a / b \rfloor * b)y_2=ay_2+b(x_2 - \lfloor a / b \rfloor y_2)$

在通過類歐幾里得算法得到該特解后，那么我們根據(jù)定理1 即可求得所有解。

擴(kuò)展歐幾里得也可以用來求線性同余式。

CODE:

int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0; // 得到一組解返回，然后通過解的關(guān)系得到通解
        return a;
    }
    int d = exgcd(b, a % b, x ,y);
    int tmp = x;
    x = y,y = tmp - a / b * y;
    return d;
}

同余和逆元

同余

定義：給定一個(gè)正整數(shù)m，把他叫做模，如果用m對(duì)任意兩個(gè)正整數(shù)a,b取模所得余數(shù)相同，我們就說a,b對(duì)模m同余，記作$a \equiv b \pmod m$,取模所得余數(shù)不同記作$a \not \equiv b \pmod m$

$a \bmod m = b \bmod m 等價(jià)于 a \equiv b (\bmod m) $

第二定義：若$m \mid a-b$, 則a,b叫做對(duì)模m同余

性質(zhì)1：若 $a \equiv b \pmod m$ , 則 $\gcd(a,m) = \gcd(b, m)$

性質(zhì)2：若 $a \equiv b \pmod m$, 則$ka \equiv kb \pmod m$

性質(zhì)3：若$a \equiv b \pmod m$，則$a = da_1, b = db_1, \gcd(d, m) = 1$ 則 $a_1 \equiv b_1 \pmod m$

同余式

定義：若用$f(x)$表示系數(shù)為整數(shù)的多項(xiàng)式；又設(shè)m是一個(gè)正整數(shù)，則$f(x) \equiv 0 \pmod m$ 叫做模m的同余式。一次同余式：$ax \equiv b \pmod m, a \not \equiv 0 \pmod m$

使同余式成立的x叫做該式的一個(gè)解。

定理：一次同余式（又叫線性同余方程）由解的充要條件是$\gcd(a, m) \mid b$

證：一次同余式可以寫成$ax=my+b$. 移項(xiàng)，得$ax-my=b$, 因$y$無關(guān)緊要, 令$y = -y$,得$ax+my=b$.一條二元一次不定方程。由定理2，證畢。

逆元

方程$ax \equiv 1 \pmod m$的一個(gè)解$x$，稱$x$為a模m的逆元。其中$\gcd(a,m)=1$

由同余性質(zhì)，因?yàn)?span id="w0obha2h00" class="math inline">$\gcd(a, m) = 1$ 上述等式可以寫成 $x \equiv \frac{1}{a} \pmod m$

逆元的一個(gè)重要應(yīng)用就是求除法的模 (k為b的逆元)

$\because (kb \bmod m) = 1$

$\frac{a} \bmod m = ((\frac{a} \bmod m)(kb \bmod m)) \bmod m = ak \bmod m$

逆元求法：

擴(kuò)展歐幾里得定理解方程
費(fèi)馬小定理

直接用快速冪求$a^{p-2}$, 注意$p$是質(zhì)數(shù)，另外$a \bmod p = 0$時(shí)無解。

費(fèi)馬小定理

若p是素?cái)?shù)，則$a^p \equiv a \pmod p$

因?yàn)?$\gcd(a, p) = 1$, 由同余性質(zhì)，上述式子也可以寫成$a^{p-1} \equiv 1 \pmod p$

定理證明：

集合$\left\{ 1,2,3...p-1 \right\}$中的每一個(gè)數(shù)模p的值互不相同。有一個(gè)數(shù)a不是p的倍數(shù)，集合$\left \{a,2a,3a,4a,...a(p-1) \right \}$中每一個(gè)數(shù)模p的值也互不相同（1），是$1,2,3,...,p-1$的一種排列。

那么$(p-1)! \equiv a * 2 * a * 3 ... * (p-1)*a \pmod b$, 左右除以$(p-1)!$（2）。

得到 $1 \equiv a^{p-1} \bmod p$.左右同乘一個(gè)a，得證。

1）證明：若$x \not \equiv y \pmod p$, $ax \equiv ay \bmod p$

2） $\gcd(p, (p-1)!) = 1$, （按照前所述性質(zhì)）可以直接除。

應(yīng)用： 求逆元，可以得到 $\frac{1}{a} \equiv a^{p-2} \pmod p$ 所以a的一個(gè)逆元就是 $a^{p-2} \bmod p$ (這里可以用快速冪來求)

Loj-P3811

fast_pow

#include <iostream>
typedef long long bl;
using namespace std;

const int N = 600;

int n, p;

bl fast_pow(bl a, bl n) {
	bl ans = 1;
	while(n) {
		if (n & 1) ans *= a % p, ans %= p;
		a *= a % p, a %= p;
		n >>= 1;
	}
	return ans;
}

int main() {
	cin >> n >> p;
	for (int i = 1; i <= n; i ++) {
		cout << fast_pow(i, p - 2) << "\n";
	}
}

ex_gcd

#include <iostream>
typedef long long bl;
using namespace std;

const int N = 600;

int n, p;

int ex_gcd(bl a, bl b, bl &x, bl &y) {
	if (!b) {
		x = 1, y = 0;
		return a;
	}
	int d = ex_gcd(b, a%b, x, y);
	int tmp = x;
	x = y, y = tmp - a / b * y;
	return d;
}

int main() {
	cin >> n >> p;
	for (int i = 1; i <= n; i ++) {
		bl x, y;
		ex_gcd(i, p, x, y);
		x = (x % p + p) % p;
		cout << x << "\n";
	}
}

唯一分解定理

任意一個(gè)大于1的整數(shù)都可以表示為質(zhì)數(shù)的乘積，即任一大于1的整數(shù)

$a=p_1p_2p_3...p_n , p_1 \leq p_2 \leq ... \leq p_n$

我們也可以將相同質(zhì)數(shù)寫在一起： $a=p_1^{a^1}p_2^{a^2}..p_n^{a^n}$, $a_i \textgreater 0, i=1,2,3,...,k$ (標(biāo)準(zhǔn)分解式)

由唯一分解定理，也不難得到gcd和lcm的表達(dá)式：

$(a,b) = p_1^{min(a1,b1)}p_2^{min(a2,b2)}p_3^{min(a3,b3)}$

$[a,b] = p_1^{max(a1,b1)}p_2^{max(a2,b2)}p_3^{max(a3,b3)}$

有時(shí)候我們需要對(duì)gcd取模的時(shí)候，我們可以用上述方法來求.

試除法分解素因子 $\Theta(\sqrt{n})$

/*
    關(guān)于試除法的證明，每輪循環(huán)i可以保證，n當(dāng)中不包含2~i的質(zhì)因子，因此第i輪循環(huán)一定不包含2~i-1的質(zhì)因子，因此，如果n%i==0的i也一定不包含2~i-1的質(zhì)因子(i整除n)， 因此iy
*/ 
void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

一般做題時(shí)有更優(yōu)的方法，即預(yù)處理求出1~n素?cái)?shù)(篩法)，然后直接枚舉素?cái)?shù)約掉素因子。

試除法求約數(shù) $O(\sqrt{n})$

/*
    對(duì)于每個(gè)數(shù)x, 在1~n的約數(shù)，可以記為 n / x;
    所以求和 n + n/2 + n/3 + .. + 1 = nlogn
*/
vector<int> res;
void get_divisors(int n) {
  for(int i = 1; i <= n / i; i ++) {
    if(n % i == 0) {
      res.push_back(i);
      if(i != n / i) res.push_back(n / i);
    }
    sort(res.begin(), res.end());
  }
}

素?cái)?shù)篩

埃氏篩

埃氏篩中每個(gè)合數(shù)可能會(huì)被篩去多次,復(fù)雜度為$O(n\log \log n)$

/*
	埃氏篩基本原理：用當(dāng)前質(zhì)數(shù)去篩掉（2~n)的合數(shù)
	如果當(dāng)前枚舉的數(shù)是合數(shù)，因?yàn)槠渌匾蜃觩<n, 并且每次循環(huán)保證p的所有倍數(shù)（kp <= n)都被篩掉，所以一定能夠篩掉當(dāng)前的數(shù)
*/

int primes[N], cnt;     // primes[]存儲(chǔ)所有素?cái)?shù)
bool st[N];         // st[x]存儲(chǔ)x是否被篩掉

void get_primes(int n) {
    for (int i = 2; i <= n; i ++ ) {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

線性篩（歐拉篩）

線性篩彌補(bǔ)了上述缺點(diǎn)，保證所有數(shù)只被篩去一次，復(fù)雜度為$O(N)$

/*
	線性篩基本原理： （用i的最小質(zhì)因子篩取i，保證了復(fù)雜度為O(N)
		枚舉2 ~ n / i的質(zhì)數(shù)，如果我們枚舉到質(zhì)數(shù)且當(dāng)前質(zhì)數(shù)pj % i == 0， 對(duì)于(1~j)的質(zhì)數(shù)一定滿足p是p*i的最小的質(zhì)因子
	因?yàn)槲覀兦蟮臅r(shí)1~n的素?cái)?shù)所以保證上界pj <= n / i
*/
void get_primes(int n) {
    for (int i = 2; i <= n; i ++ ) {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ ) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

歐拉函數(shù)

定義：

$\varphi(n)$表示的是小于等于n并且和n互質(zhì)的數(shù)的個(gè)數(shù)。 $\varphi(1)=1$, $\varphi(p) = p - 1$(p為質(zhì)數(shù))

性質(zhì)：積性函數(shù)（如果$\gcd(a,b)=1$,那么$\varphi(a*b)=\varphi(a)*\varphi(b)$)

公式：

證明：

這里給出自己的理解, 歐拉函數(shù)就求1~n以內(nèi)的與n互質(zhì)的數(shù)的個(gè)數(shù)，我們用篩取n的質(zhì)數(shù)的倍數(shù)的方法來求，即為篩取$k \times p_i$, 由于同一個(gè)數(shù)被篩去多次，那么問題轉(zhuǎn)化為容斥原理，下面不求證了直接用公式

CODE(Acwing): $O(\sqrt{n})$

int phi(int x)
{
    int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res = res / i * (i - 1); // 這里原公式時(shí) 1 - 1 / pi 由于浮點(diǎn)數(shù)問題，我們先整除后乘
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);

    return res;
}

篩法 $O(N)$ 求1~n的每個(gè)數(shù)的歐拉函數(shù)值

int primes[N], cnt;     // primes[]存儲(chǔ)所有素?cái)?shù)
int euler[N];           // 存儲(chǔ)每個(gè)數(shù)的歐拉函數(shù)
bool st[N];         // st[x]存儲(chǔ)x是否被篩掉


void get_eulers(int n)
{
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            euler[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
                euler[t] = euler[i] * primes[j]; // 互質(zhì)包含了1-p_i 直接在n位置加一個(gè)相乘即可
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1); // 不包含 p_i* （1- 1 / p_i) = p_i - 1
        }
    }
}

歐拉定理

若$a$ 與 $m$ 互質(zhì)，則$a^{\phi(m)} \equiv 1 (\bmod m)$. $\phi(m)為歐拉函數(shù)$

證明：

設(shè)$x_1, x_2, ... , x_{\phi(n)}$ 為1~n中與n互質(zhì)的數(shù)

設(shè)序列 $p_1 = ax_1, p_2 = ax_2 ... p_{\phi(n)} = ax_{\phi(n)}$

Lemma1: $p \bmod m$ 兩兩不同余

Lemma2: $p \bmod n$的每個(gè)結(jié)果都與m互質(zhì)

Lemma3: 若$(r_1 * r_2) \bmod m = r_2, 其中r_1,r_2均與m互質(zhì), 則 r_1 = 1$

由兩個(gè)引理1， 2得， $p \bmod m$ 是對(duì)$x_1, x_2, ... x_{\phi(m)}$的映射

所以有

$(\prod \limits^{\phi(m)}_{i = 1} p_i) \bmod m = (\prod \limits^{\phi(m)}_{i = 1} x_i) \bmod m$

=> $(a^{\phi(m)}\prod \limits^{\phi(m)}_{i = 1} x_i) \bmod m = (\prod \limits^{\phi(m)}_{i = 1} x_i) \bmod m$

由引理3

=> $a^{\phi(m)} \bmod m = 1$

對(duì)于歐拉定理，顯然費(fèi)馬小定理是歐拉定理的特例，即$m$為質(zhì)時(shí)， $\phi(m) = m - 1$, 帶入等式與費(fèi)馬小定理結(jié)果相同

關(guān)于引理的證明參考這個(gè)視頻

中國剩余定理

$m_1, m_2, ... m_n$兩兩互質(zhì)，求

$x \equiv a_1 (\bmod m), x \equiv a_2 (\bmod m), ... ,x\equiv a_n(\bmod m)$的一組解。

$M = m_1m_2...m_n$

$M_i = \frac{M}{m_i}$

$x = a_1 M_1 M_1^{-1} + a_2 M_2 M_2^{-1} + ... + a_n M_n M_n^{-1}$

求逆元可以用擴(kuò)歐

高斯消元

初等行列變換：

把某一行乘一個(gè)非零的數(shù)
交換某兩行
把某行的若干倍加到第三行

通過初等行列變換將方程換成上三角的形式。

結(jié)果分為三種：

完美階梯型唯一解
出現(xiàn)無解式如0 = 非零無解
0 = 0 無窮多組解

算法過程

枚舉每一列c

找到當(dāng)前列絕對(duì)值最大的一行
把這一行換到最上面
將該行的第一個(gè)數(shù)變成1（系數(shù)同時(shí)除）
把下面所有行的第c列消為0

通過消去可以得到階梯行列式

求組合數(shù)

遞推 $O(n^2)$

$C_a^b = C_{a-1}^b + C_{a-1}^{b-1}$

#include <iostream>

using i64 = long long;

const int N = 2010, mod = 1e9 + 7;

int c[N + 10][N + 10];

void init() {
    for(int i = 0; i < N; i ++) {
        for(int j = 0; j <= i; j ++) {
            if(!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
        }
    }
}

int main() {
    init();
    int n;
    std::cin >> n;
    while(n --) {
        int a, b;
        std::cin >> a >> b;
        std::cout << c[a][b] << "\n";
    }
}

逆元預(yù)處理 $O(nlogn)$

$C_a^b = \frac{a!}{(b-a)!b!} \bmod p = a! \times ((b-a)!)^{-1} \times (b!)^{-1}$ , 這里$-1$指$數(shù)論倒數(shù)$即$逆元$

所以預(yù)處理好上面的數(shù)即可求解, 逆元數(shù)組部分因?yàn)?span id="w0obha2h00" class="math inline">$ax \equiv 1(\bmod p), by \equiv 1(\bmod p) 則ax \times by \equiv 1(\bmod p)$

#include <iostream>
#include <algorithm>

using i64 = long long;

typedef long long LL;

const int N = 100010, mod = 1e9 + 7;

int fact[N], infact[N];

int fast_pow(int a, int b, int mod) {
    int res = 1;
    while(b) {
        if(b & 1) res = (LL)res * a % mod;
        a = (LL)a * a % mod;
        b >>= 1;
    }
    return res;
}

int main() {

    fact[0] = infact[0] = 1;
    for(int i = 1; i < N; i ++) {
        fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = (LL)infact[i - 1] * fast_pow(i, mod - 2, mod) % mod;
    }

    int n;
    std::cin >> n;
    while(n --) {
        int a, b;
        std::cin >> a >> b;
        std::cout << (LL)fact[a] * infact[b] % mod * infact[a- b] % mod << "\n";
    }
}

也有$O(n)$做法，需要線性預(yù)處理逆元

盧卡斯定理

$C_a^b \equiv C_{a \bmod p}^{a \bmod p} \times C_{a/p}^{b/p}(\bmod p)$

$O(p + Tlogp)$

#include <bits/stdc++.h>

using i64 = long long;

i64 p;

int fast_pow(int a, int k) {
    int res = 1;
    while(k){
        if(k & 1) res = (i64)res * a % p;
        a = (i64)a * a % p;
        k >>= 1;
    }
    return res;
}

int C(int a, int b) {
    int res = 1;
    for(int i = 1, j = a; i <= b; i ++, j --) {
        res = (i64)res * j % p;
        res = (i64)res * fast_pow(i, p - 2) % p;
    }
    return res;
}

int lucas(i64 a, i64 b) {
    if(a < p && b < p) return C(a, b);
    return (i64)C(a % p, b % p) * lucas(a / p, b / p) % p;
}

int main() {
    int n;
    std::cin >> n;
    while(n --) {
        i64 a, b;
        std::cin >> a >> b >> p;
        std::cout << lucas(a, b) << "\n";
    }
}

高精度-組合數(shù)

分解質(zhì)因數(shù)
寫高精度乘法

#include <iostream>
#include <algorithm>
#include <vector>
using i64 = long long;

const int N = 5010;

int primes[N], cnt;
int sum[N];
bool st[N];

void get_primes(int n) {
    for(int i = 2; i <= n; i ++) {
        
        if(!st[i]) primes[cnt ++] = i;
        
        for(int j = 0; primes[j] <= n / i; j ++) {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

int get(int n, int p) {
    int res = 0;
    while(n) {
        res += n / p;
        n /= p;
    }
    return res;
}

std::vector<int> mul(std::vector<int> a, int b) {
    std::vector<int> c;
    int t = 0;
    for(int i = 0; i < a.size(); i ++) {
        t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    while(t) {
        c.push_back(t % 10);
        t /= 10;
    }
    return c;
}

int main() {
    int a, b;
    std::cin >> a >> b;

    get_primes(a);

    for(int i = 0; i < cnt; i ++) {
        int p = primes[i];
        sum[i] = get(a, p) - get(a - b, p) - get(b, p);
    }

    std::vector<int> res;
    res.push_back(1);

    for(int i = 0; i < cnt; i ++)
        for(int j = 0; j < sum[i]; j ++)
            res = mul(res, primes[i]);

    for(int i = (int)res.size() - 1; i >= 0; i --) std::cout << res[i];
}

容斥原理

復(fù)雜度計(jì)算

$C_n^1 + C_n^2 + ... + C_n^3 + ... + C_n^n = 2^n - C_n^0 = 2^n - 1$

$O(2^n)$

$\abs{S_1 \cup S_2 \cup S_3 ... \cup S_n} = \sum \limits_i\abs{S_i} - \sum \limits_{i \cdot j}\abs{S_i \cup S_j} + \sum \limits_{i \cdot j \cdot k}\abs{S_i \cup S_j \cup S_k} - ...$

簡單證明：假設(shè)集合中的某個(gè)元素$x$，在上述等式中被算了$k$次，則

$C_k^1 - C_k^2 + C_k^3 - C_k^4 + ... + (-1)^{k - 1}C_k^k = 1$

能被整除的數(shù)

#include <bits/stdc++.h>

using i64 = long long;

const int N = 1e5 + 10;

int p[N], n, m, res = 0;

int main() {
    int n, m, ans = 0;
    std::cin >> n >> m;

    for(int i = 0; i < m; i ++) {
        std::cin >> p[i];
    }

    for(int i = 1; i < 1 << m; i ++) {
        int t = 1;
        int s = 0;

        for(int j = 0; j <= m - 1; j ++) {
            if(i >> j & 1) {
                if((i64)p[j] * t > n) {
                    s = -1;
                    break;
                }   
                s ++;
                t *= p[j];  
            }   
        }

        if(s == -1) continue;

        if(s & 1) ans += n / t;
        else ans -= n / t;
    }

    std::cout << ans << "\n";
}

勒讓那多定理

Legendre 定理

在正數(shù)$n!$的質(zhì)因數(shù)分解中, 質(zhì)數(shù)$p$ 的指數(shù)記作$v_p(n!)$,則有等式$v_p(n!)=\sum\limits_{j=1}^{\infty} \lfloor\frac{n}{p^k} \rfloor$

LL f(LL n, LL p) {
	if (n == 0) return 0;
	n /= p;
	return n + f(n, p);
}

博弈

對(duì)稱博弈

牛牛取石子

下模仿棋就不會(huì)吃虧

公平組合游戲 ICG

兩個(gè)玩家交替游戲，每個(gè)玩家可執(zhí)行操作相同，不能行動(dòng)玩家判負(fù)

有向圖游戲

給定有向無環(huán)圖，圖中有唯一起點(diǎn)，在起點(diǎn)放有一枚棋子。兩名玩家交替行動(dòng)，每次移動(dòng)一個(gè)邊，無法移動(dòng)玩家為負(fù)。任何公平組合游戲可以轉(zhuǎn)化為有向圖游戲。

Nim Game

$a_1 \oplus a_2 .. . \oplus ... a_n = 0$為必?cái)B(tài)，否則為必勝態(tài)

#include <bits/stdc++.h>

using i64 = long long;

const int N = 1e5 + 10;

int a[N];

int main() {
    int n, ok = 0;
    std::cin >> n;

    for(int i = 1; i <= n; i ++) {
        std::cin >> a[i];
        ok ^= a[i];
    }

    std::cout << (ok?"Yes":"No");
}

臺(tái)階NIM

集合NIM

指定取數(shù)集合$S$，進(jìn)行NIM游戲

單個(gè)$SG(a_i)$為0時(shí)為必?cái)?，否則必勝，對(duì)所有$i$轉(zhuǎn)為都為0時(shí)為必?cái)B(tài)，此時(shí)轉(zhuǎn)為NIM游戲問題

$SG(a_1) \oplus SG(a_2) \oplus ... SG(a_n) = 0$ 必勝，否則必?cái)?/p>

#include <bits/stdc++.h>
#include <cstring>
#define FOR(i, n) for(int i = 1; i <= n; i ++)
using i64 = long long;
const int N = 110, M = 10010;

int n, m;
int s[N], f[M];

int sg(int x) {
    if(f[x] != -1) return f[x];

    std::unordered_set<int> S;

    for(int i = 0; i < m; i ++) {
        int sum = s[i];
        if(x >= sum) S.insert(sg(x - sum));
    }

    for(int i = 0; ; i ++) {
        if(!S.count(i))
            return f[x] = i;
    }
}

int main() {
    std::cin >> m;
    for(int i = 0; i < m; i ++) std::cin >> s[i];
    std::cin >> n;

    memset(f, -1, sizeof f);

    int res = 0;

    for(int i = 0; i < n; i ++) {
        int x;
        std::cin >> x;
        res ^= sg(x);
    }
    
    std::cout << (res?"Yes":"No");
}

SG函數(shù)

有向圖游戲中，對(duì)于每個(gè)節(jié)點(diǎn)$x$,設(shè)從$x$出發(fā)共有$k$條有向邊，分別到達(dá)節(jié)點(diǎn)$y_1, y_2, ...,y_k$的SG函數(shù)構(gòu)成的集合在執(zhí)行$Mex(S)$運(yùn)算的結(jié)果即

$SG(x) = Mex({SG(y_1), SG(y_2), ..., SG(y_k)})$

特別地，整個(gè)有向圖游戲$G$的$SG$函數(shù)值被定義為有向圖的起點(diǎn)$s$的$SG$函數(shù)值，即$SG(G) = x$

有向圖游戲的某個(gè)局面必勝，當(dāng)且僅當(dāng)該局面對(duì)應(yīng)節(jié)點(diǎn)的SG函數(shù)值大于0

有向圖游戲的某個(gè)局面必?cái)?，?dāng)且僅當(dāng)該局面對(duì)應(yīng)節(jié)點(diǎn)的SG函數(shù)值等于0

Mex運(yùn)算

設(shè)$S$表示一個(gè)非負(fù)整數(shù)集合。定義$Mex(S)$為不屬于集合$S$的最小最非負(fù)整數(shù)運(yùn)算。

即 $Mex(S) = min(x)$, $x$屬于自然數(shù)，且$x$不屬于$S$

如$Mex(\{0, 1, 3\})$為$2$

卡特蘭特?cái)?shù)

給定 $n$ 個(gè) $0$ 和 $n$ 個(gè) $1$，它們將按照某種順序排成長度為 $2n$ 的序列，求它們能排列成的所有序列中，能夠滿足任意前綴序列中 $0$ 的個(gè)數(shù)都不少于 $1$ 的個(gè)數(shù)的序列有多少個(gè)。

$C_{2n}^{n} - C_{2n}^{n - 1} = \frac{C_{2n}^{n}}{n + 1}$

勒讓那多定理

Legendre 定理

在正數(shù)$n!$的質(zhì)因數(shù)分解中, 質(zhì)數(shù)$p$ 的指數(shù)記作$v_p(n!)$,則有等式$v_p(n!)=\sum\limits_{j=1}^{\infty} \lfloor\frac{n}{p^k} \rfloor$

LL f(LL n, LL p) {
    if (n == 0) return 0;
    n /= p;
    return n + f(n, p);
}

Geometry

二維幾何

坐標(biāo)旋轉(zhuǎn)

對(duì)于平面直角坐標(biāo)系下的坐標(biāo)$(x, y)$ 順時(shí)針旋轉(zhuǎn)$\theta°$ 后的坐標(biāo)

\[\begin{pmatrix} x & y \end{pmatrix} \times \begin{pmatrix} cos\theta & sin\theta \\ -sin\theta & cos\theta \\ \end{pmatrix}# This is my template for Algorithm Contest ```c++ // c11 編譯器選項(xiàng) -std=c++11 // 注意：當(dāng)設(shè)置為 false 時(shí)，cin 就不能和scanf，sscanf, getchar, fgets等同時(shí)使用。 // 取消cin和cout對(duì)于C語言的流同步（這時(shí)盡量不要將兩種輸入輸出混合） ios::sync_with_stdio(false); // 解除 cin 和 cout 運(yùn)行庫層面的對(duì)數(shù)據(jù)傳輸?shù)哪J(rèn)綁定。由于存在數(shù)據(jù)傳輸?shù)哪J(rèn)綁定， cin 和 cout 在每次操作的時(shí)候（也就是調(diào)用”<<”或者”>>”）都要刷新（調(diào)用flush），這樣增加了IO的負(fù)擔(dān)。通過解除綁定，可提高輸入輸出效率。 // cin構(gòu)造出來就會(huì)調(diào)用cin.tie() 與cout綁定每次格式化輸入都會(huì)調(diào)用cout.flush();導(dǎo)致效率低，可以使用該語句解綁 cin.tie(NULL); cout.tie(NULL); // 求最大值 auto it = max_element(std::begin(cloud), std::end(cloud)); // C++11 min_element同理表示圓周率：#define PI acos(-1.0) getline(cin, t) // 用C++讀取一行 string b = "chi1 huo1 guo1", a = "1chi1 huo1 guo1"; a.find(b); // 若找到字串返回位置(0開始的索引), 否則返回-1 priority_queue<int> s2; // 默認(rèn)大頂堆 priority_queue<int, vector<int>, greater<int>> s1; // 這里可以設(shè)置成小頂堆 // 底層哈希表（鍵有限制，只能int，string，double等，不能是自己定義的結(jié)構(gòu)體 // 查詢O(1) 修改O(logn) unordered_map<string, int> ump; // 底層紅黑樹（鍵無限制） // 查詢O(logn) 修改O(logn) map<node, int> mp; // cout 輸出較大小數(shù)或特別大的數(shù)可能會(huì)輸出科學(xué)計(jì)數(shù)法，這時(shí)前面需要加一個(gè)fixed cout << fixed << setprecision(6) << n; // lower表示等于 >= int r = lower_bound(v.begin(), v.end(), x) - v.end(); // upper表示大于 > int l = upper_bound(v.begin(), v.end(), y) - v.end(); // multiset 可以插入重復(fù)的數(shù)字，并且保證集合有序插入和刪除為O(logn), <set>庫 multiset /* 字符串處理 */ 注意C++的字符串末尾也會(huì)加\0,但是他會(huì)放在a.size()這個(gè)位置上，所以原則上可以越界到這個(gè)位置 string a; a = string("1234") // 字符串構(gòu)造函數(shù) a = string(cnt, '1') //賦值cnt個(gè)1構(gòu)成的字符串給a // i為起始坐標(biāo)（從0開始），len為長度，獲取字串 a.substr(i, len); // 找子串，存在返回下標(biāo)（0開始），不存在返回-1 a.find("haha"); // cctype中的東西 isalpha('a') // 判斷是否為字母包括大小寫 islower('a') // 判斷是否為小寫字母 isuppper('a') // 判斷是否為大寫字母 isalnum('a') // 判斷是否為大小寫字母或數(shù)字 isblank('a') // 判斷是否為空格或制表符\t isspace('a') // 判斷是否為 space, \t, \r, \n char t = tolower('A') // 轉(zhuǎn)換小寫 char t = toupper('a') // 轉(zhuǎn)換為大寫 string n = to_string(123) // 轉(zhuǎn)換為字符串可以是int float double 等 string str = "123"; int a = stoi(str); // 將字符串轉(zhuǎn)變?yōu)閿?shù)（注意若str是非法的，那么stoi將會(huì)讀取到非數(shù)字為止） string str2 = "123.4" double b = stod(str); // 將字符串轉(zhuǎn)變?yōu)閐ouble型，若非法，自動(dòng)截取前面的浮點(diǎn)數(shù)，非法為止，若前面不是數(shù)字或小數(shù)點(diǎn)發(fā)生運(yùn)行錯(cuò)誤，若前面是小數(shù)點(diǎn)會(huì)轉(zhuǎn)化后在前面自動(dòng)補(bǔ)0 // 類似的還有 stof (string to float) stold (string to long double) stol (string to long) stoll (string to long long) stoul (string to unsigned long) stoull (string to unsigned long long) ``` # Basic algorithm ## 前綴異或由異或性質(zhì)（結(jié)合律）$a \oplus (b \oplus c) = (a \oplus b) \oplus c$, $a \oplus a = 0$, 因此對(duì)于給定的區(qū)間異或假設(shè)我們有一個(gè)前綴異或函數(shù)$f(i)$, 那么對(duì)于區(qū)間$[l, r]$的異或，我們可以得到$Xor(i, j) =f(j) \oplus f(i - 1)$ ## 前綴和 O(1) 對(duì)矩陣求和 ```c++ #include <iostream> #include <cstring> using namespace std; const int N = 1e3 + 5; int main() { int n, m, q, a[N][N], sum[N][N]; cin >> n >> m >> q; for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) { cin >> a[i][j]; sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j]; } while(q --) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; cout << sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1] << endl; } } ``` ## 差分 O(1) 對(duì)矩陣操作 + - * / ```C++ #include <iostream> #include <cstring> #include <iostream> using namespace std; const int N = 1e3 + 5; int diff[N][N]; // 差分矩陣主要記住insert就行了，相當(dāng)于輸入打標(biāo)記，區(qū)間打標(biāo)記 void insert(int x1, int y1, int x2, int y2, int c) { diff[x1][y1] += c, diff[x1][y2 + 1] -= c, diff[x2 + 1][y1] -= c, diff[x2 + 1][y2 + 1] += c; } int main() { int n, m, q, a[N][N]; cin >> n >> m >> q; for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) { cin >> a[i][j], insert(i, j, i, j, a[i][j]); } while(q --) { int x1, y1, x2, y2, c; cin >> x1 >> y1 >> x2 >> y2 >> c; insert(x1, y1, x2, y2, c); } for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) cout << (diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1]) << "\0 \n "[2 * (i != n) + (j != m)]; } ``` ## 位運(yùn)算 ### 異或 $a \oplus a = 0$ $0 \oplus a = a$ $a \oplus b = b \oplus a$ $a \oplus (b \oplus c) = (a \oplus b) \oplus c$ $a \oplus b = c$ , then $a \oplus c = b$ **變量交換** $a = a \oplus b$, $b = a \oplus b$, $a = a \oplus b$ **排除重復(fù)里面的不重復(fù)（唯一一個(gè)不重復(fù)的）** 對(duì)于任意的$arr[i]$, 進(jìn)行異或，最終得到的結(jié)果便是唯一不重復(fù)的數(shù)字 ## 二分 ```C++ // 區(qū)間[l, r]被劃分成 [l, mid] 和 [mid + 1, r] 時(shí) int bsearch(int x) { while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } } // l = mid時(shí)，補(bǔ)上 + 1 （l + r + 1 >> 1) // 補(bǔ)上加以等同于四舍五入，保證了mid不會(huì)等于l,從而導(dǎo)致l被重復(fù)賦值為l造成死循環(huán) // 區(qū)間[l, r]被劃分成 [l, mid - 1] 和 [mid, r] 時(shí) int bsearch(int x) { while (l < r) [ int mid = l + r + 1 >> 1; if (check(mid)) l = mid; else r = mid - 1; ] } // 浮點(diǎn)數(shù)二分 const double EPS = 1e-8; dobule b_search(double n) { double l = -1000, r = 1000; while (r - l >= EPS) { double mid = (l + r) / 2; if (mid * mid * mid >= n) r = mid; else l = mid; } } // 也可以直接迭代指定次數(shù) for (int i = 1; i <= 100; i ++) { double mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; } ``` # Some suffixes ## 1. Qucikly read for const numbers ```C++ #include <bits/stdc++.h> #define rep(i, j, k) for(int i = j; i <= k; i ++) #define per(i, j, k) for(int i = j; i >= k; i --) #define lc p<<1 #define rc p<<1|1 #define f first #define s second #define pb(x) push_back(x) #define ll long long using namespace std; const int N = 1e7 + 10; char buf[1 << 21], *p1 = buf, *p2 = buf; // p1 means start point and p2 means end point inline char gc(){ if (p1 == p2){ // fread return real count p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin); } return *p1 ++; } // gc can be replaced by function getchar. inline int read(){ int s = 0, w = 1; char ch = gc(); while (ch < '0' || ch > '9'){ if (ch == '-') w *= - 1; ch = gc(); } while ('0' <= ch && ch <= '9'){ s = (s << 1) + (s << 3) + (ch ^ 48); ch = gc(); return s * w; } } int main() { int n, t; ll sum = 0; cin >> n; rep (i, 1, n){ t = read(); if (i > 1){ sum ^= t; }else{ sum = t; } } cout << sum; } ``` ## 2. Header ```C++ #include <iostream> #include <cstring> #include <cmath> #include <stack> #include <queue> #include <map> #include <set> #include <bitset> #include <algorithm> #include <functional> #include <utility> #include <unordered_set> #include <unordered_map> #define INF 0x3f3f3f3f #define siz(x) (int)x.size() #define IOS ios::sync_with_stdio(false); #define rep(i, j, k) for(int i = j; i <= k; ++ i) #define per(i, j, k) for(int i = j; i >= k; -- i) #define dbg1(a) cout << a << endl; #define dbg2(a, b) cout << a << " " << b << endl; #define dbg3(a, b, c) cout << a << " " << b << " " << c << endl; #define pb(x) push_back(x) #define eb(x) emplace_back(x) #define all(x) x.begin(), x.end() #define f first #define s second #define FASTIO \ std::ios ::sync_with_stdio(0); \ std::cin.tie(0); \ std::cout.tie(0); #define lc p<<1 #define rc p<<1|1 using namespace std; typedef long long LL; typedef priority_queue<int, vector<int>, greater<int>> S_HEAP; typedef priority_queue<int> B_HEAP; typedef pair<string, int> PSI; typedef pair<int, int> PII; const int N = 1e5 + 10; ``` # First : Tree ## 1. Heap ```C++ ## Insert Establish void PushUp(int i){ if (i == 1) return; while (i != 1){ if (heap[i] < heap[i / 2]) swap(heap[i], heap[i / 2]), i /= 2; else break; } } int n; for (int i = 1; i <= n; i ++){ PushUp(i); } ## Establish via binary tree void AdjustHeap(int a[], int i, int n){ for (i = i * 2; i <=n; i *= 2){ if (i < n && a[i + 1] < a[i]) i ++; if (a[i] < a[i / 2]) swap(a[i], a[i / 2]); else break; } } void build(int a[], int p, int n){ for (int i = n / 2; i >= p; i --){ AdjustHeap(a, i, n); } } ## Delete root Elements sawp(a[1], a[len + 1]); AdjustHeap(a, 1, n - 1) ``` ## 2. Segment Tree ```C++ #include <bits/stdc++.h> #define rep(i, j, k) for (int i = j; i <= k; i ++) #define per(i, j, k) for (int i = j; i >= k; i --) #define ll long long #define lc p<<1 #define rc p<<1|1 using namespace std; const int N = 1e5 + 10; ll w[N]; struct node{ ll l, r, sum, add; }tr[4 * N]; void pushup(int p){ tr[p].sum = tr[rc].sum + tr[lc].sum; } void pushdown(int p){ if (tr[p].add){ tr[rc].sum += (tr[rc].r - tr[rc].l + 1) * tr[p].add; tr[lc].sum += (tr[lc].r - tr[lc].l + 1) * tr[p].add; tr[lc].add += tr[p].add; tr[rc].add += tr[p].add; tr[p].add = 0; } } void build(int p, int l, int r){ tr[p] = {l, r, w[l], 0}; if (l == r) return; int m = l + r >> 1; build(lc, l, m); build(rc, m + 1, r); pushup(p); } void update(int p, int l, int r, int k){ if (tr[p].l >= l && tr[p].r <= r){ tr[p].sum += (tr[p].r - tr[p].l + 1) * k; tr[p].add += k; return; } int m = tr[p].l + tr[p].r >> 1; pushdown(p); if (l <= m) update(lc, l, r, k); if (r > m) update(rc, l, r, k); pushup(p); } ll query(int p, int l, int r){ if (tr[p].l >= l && tr[p].r <= r) return tr[p].sum; int m = tr[p].l + tr[p].r >> 1; ll sum = 0; pushdown(p); if (l <= m) sum += query(lc, l, r); if (r > m) sum += query(rc, l, r); return sum; } int main() { int n, m; cin >> n >> m; rep (i, 1, n){ cin >> w[i]; } build(1, 1, n); rep (i, 1, m){ int c, x, y, z; cin >> c; if (c == 1){ cin >> x >> y >> z; update(1, x, y, z); } else{ cin >> x >> y; cout << query(1, x, y) << endl; } } } ## lazytag ``` ## 3. Cartesian Tree For the best description about Cartesian Tree. The first time I read about it was sophisticated to understand. Cartesian Tree is a tree defined by the BST and the Heap(min), so if the tree is BST and Heap(min), that is a Cartesian Tree. What about the algorithm? Look it at [OIWIKI](https://oiwiki.org/ds/cartesian-tree/). ```C++ #include <bits/stdc++.h> #include <cmath> #define f first #define s second #define pb(x) push_back(x) #define ll long long #define pii pair<int, int> #define psi pair<string, int> #define rep(i, j, k) for (int i = j; i <= k; ++ i) #define per(i, j, k) for (int i = j; i >= k; -- i) #define lc p<<1 #define rc p<<1|1 using namespace std; const int N = 100; int st[N], ls[N], rs[N], q[N], tt, n, a[N]; bool has_fa[N]; void bfs(int root){ int hh, tt; hh = tt = 0; q[0] = root; while (hh <= tt){ int t = q[hh ++]; if (ls[t]) q[ ++ tt] = ls[t]; if (rs[t]) q[ ++ tt] = rs[t]; cout << a[t] << " "; } } int main() { int n; cin >> n; rep (i, 1, n) cin >> a[i]; rep (i, 1, n){ int k = tt; while (k > 0 && a[st[k]] > a[i]) k --; if (k) rs[st[k]] = i, has_fa[i] = true; if (k < tt) ls[i] = st[k + 1], has_fa[st[k + 1]] = true; st[++k] = i; tt = k; } int root = 1; while (has_fa[root]) root ++; bfs(root); } ``` # Graph ## 1. Topological sort (Kath) ```C++ bool toposort(){ queue<int> q; rep (i, 1, n) if (!din[i]) q.push(i); while (q.size()){ int x = q.front(), cnt = 0, tmp[N]; q.pop(); tp.push_back(x); for (auto y : v[x]){ if (-- din[y] == 0) q.push(y); } } if (tp.size() == n) return 1; else return 0; } ``` ## 2. Topological sort (DFS) ```C++ bool dfs(int x){ c[x] = -1; for (int y : e[x]){ if (c[y] < 0) return 0; else if (!c[y]) if (!dfs[y]) return 0; } c[x] = 1; tp.push_back(x); return 1; } bool toposort(){ memset(c, 0, sizeof(c)); rep (x, 1, n){ if (!c[x]) if (!dfs(x)) return 0; } reverse(tp.begin(), tp.end()); return 1; } ``` ## 3. Dijkstra (normal) ```C++ #include <iostream> #include <cstring> #include <vector> #define f first #define s second #define pb(x) push_back(x) #define rep(i, j, k) for (int i = j; i <= k; ++ i) #define Inf 0x3f3f3f3f using namespace std; const int N = 1e4 + 10; struct edge{int v, w;}; bool st[N]; int dist[N], pre[N], n, m, s; vector<edge> g[N]; void dijkstra(int s){ memset(dist, 0x3f, sizeof(dist)); dist[s] = 0; rep (i, 1, n - 1){ int u = -1; rep (j, 1, n) if (!st[j] && (u == -1 || dist[j] < dist[u])) u = j; st[u] = 1; for (auto x : g[u]){ int v = x.v, w = x.w; if (dist[v] > dist[u] + w) pre[v] = u; dist[v] = dist[u] + w; } } } void dfs_path(int u){ if (u == 1){ printf("%d", u); } dfs_path(pre[u]); printf("->%d", u); } int main() { cin >> n >> m >> s; rep(i, 1, m){ int u, v, w; cin >> u >> v >> w; g[u].push_back({v, w}); } dijkstra(s); rep (i, 1, n){ if (dist[i] == Inf) cout << (1<<31) - 1 << " "; else cout << dist[i] << " "; } } ``` ## 4. Dijkstra (Heap) ```C++ #include <bits/stdc++.h> #define pii pair<int, int> #define f first #define s second #define pb(x) push_back(x) #define rep(i, j, k) for (int i = j; i <= k; ++ i) #define Inf 0x3f3f3f3f using namespace std; const int N = 1e5 + 10; struct edge{int v, w;}; bool st[N]; int dist[N], pre[N], n, m, s; vector<edge> g[N]; priority_queue<pii> q; void dijkstra(int s){ memset(dist, 0x3f, sizeof(dist)); dist[s] = 0, q.push({0, s}); while (q.size()){ auto t = q.top(); q.pop(); int u = t.s; if (st[u]) continue; st[u] = 1; for (auto x : g[u]){ int v = x.v, w= x.w; if (dist[v] > dist[u] + w){ pre[v] = u; dist[v] = dist[u] + w; q.push({-dist[v], v}); } } } } void dfs_path(int u){ if (u == 1){ printf("%d", u); return; } dfs_path(pre[u]); printf("->%d", u); } int main() { cin >> n >> m >> s; rep(i, 1, m){ int u, v, w; cin >> u >> v >> w; g[u].push_back({v, w}); } dijkstra(s); rep (i, 1, n){ if (dist[i] == Inf) cout << (1<<31) - 1 << " "; else cout << dist[i] << " "; } } ``` ## 5. Bellman-ford ```C++ int bellman_ford(){ memset(dist, 0x3f, sizeof(dist)); // init data dist[1] = 0; bool flag; rep (i, 1, n){ // n times loop flag = false; rep (j, 0, m - 1){ // then travese all the vertex in the graph int a = edges[j].a, b = edges[j].b, w = edges[j].w; if (dist[b] < dist[a] + w) // realex the edge by the other edge dist[b] = dist[a] + w, flag = true; } } if (flag) cout << "The graph has negative circle!"; // judge the negative circle if (dist[n] > 0x3f3f3f3 / 2) return -1; // if the vertex can't be reach from source point return dist[n]; } ``` ## 6. SPFA ```C++ dfs_path(int u){ if (u == 1) { printf("%d", u); return; } dfs_path(pre[u]); printf("->%d", u); } bool spfa(int s){ queue<int> q; d[s] = 0, q.push(s), st[s] = 1; while (q.size()){ int x = q.front(); q.pop(), st[x] = 0; for (auto y : e[x]){ int v = y.v, w = y.w; if (d[v] > d[x] + w){ d[v] = d[x] + w; pre[v] = x; cnt[v] = cnt[x] + 1; if (cnt[v] >= n) return true; // if the graph has negative circle the func will return true value if (!st[v]) q.push(v), st[v] = 1; } } } return false; } // if you the source vertex can't reach the negative circle, you should put all the vertex to queue bool spfa(){ memset(d, 0x3f, sizeof(d)); rep(i, 1, n) q.push(i), st[i] = 1; while (q.size()){ int x = q.front(); q.pop(), st[x] = 0; for (auto y : e[x]){ int v = y.v, w = y.w; if (d[v] > d[x] + w){ d[v] = d[x] + w; cnt[v] = cnt[x] + 1; if (cnt[v] >= n) return true; // the negative circle is true if (!st[v]) q.push(v), st[v] = 1; } } } return false; // not have any negative circle } ``` ## 7. Floyd ```C++ #include <bits/stdc++.h> #define rep(i, j, k) for (int i = j; i <= k; ++ i) #define pii pair<int, int> #define Inf 0x3f3f3f3f using namespace std; const int N = 201, M = 1e4 + 10; int d[N][N], p[N][N], n, m, k; void floyd(){ rep (k, 1, n) rep (i, 1, n) rep (j, 1, n) if (d[i][j] < d[i][k] + d[k][j]) d[i][h] = d[i][k] + d[k][j], path[i][j] = k; } void path(int i, int j){ if (p[i][j] == 0) return; int k = p[i][j]; path(i, k); printf("%d->", k); path(k, j); } int main(){ cin >> n >> m >> k; rep (i, 1, n) rep (j, 1, n) if (i == j) d[i][j] = 0; else d[i][j] = Inf; rep (i, 1, m){ int a, b, c; cin >> a >> b >> c; d[a][b] = min(d[a][b], c); } floyd(); while (k --){ int a, b; cin >> a >> b; if (d[a][b] > Inf / 2) cout << "impossible" << endl; else cout << d[a][b] << endl; } // print the most shortest path int a, b; cin >> a >> b; cout << a << "->"; path(a, b); cout << b << endl; } ``` ## 8. Kruskal ``` C++ #include <bits/stdc++.h> #define rep(i, j, k) for (int i = j; i <= k; ++ i) #define pii pair<int, int> #define Inf 0x3f3f3f3f using namespace std; const int N = 5010, M = 1e5 + 10; int p[N], cnt, n, m, ans; struct edge{ int u, v, w; bool operator<(const edge &t) const{ return w < t.w; } }e[4 * M]; int find(int x){ if (p[x] != x) p[x] = find(p[x]); return p[x]; } bool kruskal(){ sort(e, e + m); rep(i, 1, n) p[i] = i; rep (i, 0, m - 1){ int fa = find(e[i].u), fb = find(e[i].v); if (fa != fb){ p[fa] = fb; ans += e[i].w; cnt ++; } } return cnt == n - 1; } int main(){ cin >> n >> m; int num = 0; rep (i, 0, m - 1){ int a, b, c; cin >> a >> b >> c; e[num ++] = {a, b, c}; e[num ++] = {b, a, c}; } m = num; if (kruskal()) cout << ans; else cout << "orz"; } ``` ## 9. Prim (normal) ``` C++ #include <bits/stdc++.h> #define rep(i, j, k) for (int i = j; i <= k; ++ i) #define pii pair<int, int> #define Inf 0x3f3f3f3f using namespace std; const int N = 5010, M = 1e5 + 10; int d[N], st[N], ans, cnt, n, m; struct edge{int v, w;}; vector<edge> e[N]; bool prim(int s){ memset(d, 0x3f, sizeof(d)); d[s] = 0; rep (i, 1, n){ int u = 0; rep (j, 1, n) if (!st[j] && d[j] < d[u]) u = j; st[u] = 1; ans += d[u]; if (d[u] != Inf) cnt ++; for (auto y : e[u]){ int v = y.v, w = y.w; if (d[v] > w) d[v] = w; } } return cnt == n; } int main(){ int num = 0; cin >> n >> m; rep (i, 1, m){ int a, b, c; cin >> a >> b >> c; e[a].push_back({b, c}); e[b].push_back({a, c}); } if (prim(1)) cout << ans; else cout << "impossible"; } ``` ## 10. Prim(Heap) ```C++ #include <bits/stdc++.h> #define s second #define f first #define rep(i, j, k) for (int i = j; i <= k; ++ i) #define pii pair<int, int> #define Inf 0x3f3f3f3f using namespace std; const int N = 5010, M = 1e5 + 10; int d[N], st[N], ans, cnt, n, m; struct edge{int v, w;}; vector<edge> e[N]; priority_queue<pii> q; bool prim(int s){ memset(d, 0x3f, sizeof(d)); d[s] = 0, q.push({0, s}); while (q.size()){ int u = q.top().s; q.pop(); if (st[u]) continue; st[u] = 1, ans += d[u], cnt ++; for (auto y : e[u]){ int v = y.v, w = y.w; if (d[v] > w){ d[v] = w; q.push({-d[v], v}); } } } return cnt == n; } int main(){ int num = 0; cin >> n >> m; rep (i, 1, m){ int a, b, c; cin >> a >> b >> c; e[a].push_back({b, c}); e[b].push_back({a, c}); } if (prim(1)) cout << ans; else cout << "impossible"; } ``` ## 11. Dyeing about Bipartite Graph ```C++ #include <bits/stdc++.h> #define s second #define f first #define rep(i, j, k) for (int i = j; i <= k; ++ i) #define pii pair<int, int> #define Inf 0x3f3f3f3f using namespace std; const int N = 1e5 + 10, M = 2 * (1e5 + 10); int h[N], e[M], ne[M], idx, n, color[N], m; void add(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++; } inline bool dfs(int u, int c){ color[u] = c; for (int i = h[u]; i != -1; i = ne[i]){ int j = e[i]; if (color[j] == -1){ if (!dfs(j, !c)) return false; } else if (color[j] == c) return false; } return true; } inline bool check(){ memset(color, -1, sizeof(color)); bool flag = true; rep (i, 1, n){ if (color[i] == -1){ if (!dfs(i, 0)){ flag = false; break; } } } return flag; } int main(){ memset(h, -1, sizeof(h)); cin >> n >> m; rep (i, 1, m){ int a, b; cin >> a >> b; add(a, b); add(b, a); } if (check()) puts("Yes"); else puts("No"); } ``` ## 12. Hungarian algorithm ```C++ #include <bits/stdc++.h> #define s second #define f first #define rep(i, j, k) for (int i = j; i <= k; ++ i) #define pii pair<int, int> #define Inf 0x3f3f3f3f using namespace std; const int N = 1e5 + 10, M = 1e5 + 10; int h[N], e[M], ne[M], match[N], idx, n, m, k, ans; bool st[N]; void add(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++; } bool dfs(int u){ for (int i = h[u]; i != -1; i = ne[i]){ int j = e[i]; if (!st[j]){ st[j] = true; if (!match[j] || dfs(match[j])){ match[j] = u; return true; } } } return false; } int main(){ memset(h, -1, sizeof(h)); cin >> n >> m >> k; rep (i, 0, k - 1){ int a, b; cin >> a >> b; add(a, b); } rep (i, 1, n){ memset(st, 0, sizeof(st)); if (dfs(i)) ans ++; } cout << ans; } ``` ## 13.DSU ```C++ /* DSU + 維護(hù)size + 權(quán)值 */ // init for(int i = 1; i <= n; i ++) p[i] = i, siz[i] = 1; // find fuc int find(int x) { if(x != p[x]) { int t = find(p[x]); d[x] += d[p[x]]; p[x] = t; } } // add fuc void add(int x, int y, int k) { if(find(x) != find(y)) siz[find(y)] += siz[find(x)]; p[find(x)] = find(y); val[find(x)] += -val[x] + val[y] + s; } ``` # String ## 1. KMP ```C++ #include <bits/stdc++.h> #include <cstring> #include <cmath> #define ll long long #define f first #define s second #define Inf 0x3f3f3f3f #define NInf -0x3f3f3f3f #define pii pair<int, int> #define rep(i, j, k) for(int i = j; i <= k; ++ i) #define per(i, j, k) for(int i = j; i >= k; -- i) using namespace std; const int N = 1e6 + 10; int ne[N]; void init_kmp(char p[], int m){ ne[1] = 0; for (int i = 2, j = 0; i <= m; ++ i){ while (j && p[i] != p[j + 1]) j = ne[j]; if (p[j + 1] == p[i]) j ++; ne[i] = j; } } void kmp(char a[], char p[], int n, int m){ for (int i = 1, j = 0; i <= n; ++ i){ while (j && p[j + 1] != a[i]) j = ne[j]; if (a[i] == p[j + 1]) j ++; if (j == m) cout << i - j + 1 << endl; } } int getlen(char a[]){ int i = 1; while (a[i]) i ++; return i - 1; } int main(){ char a[N], p[N]; cin >> a + 1 >> p + 1; int n = getlen(a), m = getlen(p); init_kmp(p, m); kmp(a, p, n, m); cout << ne[1]; rep (i, 2, m) cout << " " << ne[i]; } ``` # Math ## 基本定理可看，唯一分解定理（**算數(shù)基本定理**） $x = p^{a_1} \times p ^{a_2} \times ... \times p^{a_n}$ (p為x的素因子)，該分解式對(duì)于任意的正整數(shù)（$x\ge2$)唯一 **約數(shù)個(gè)數(shù)：**$\prod \limits_{i = 1}^n (a_i + 1)$ **約數(shù)之和：**$\prod \limits_{i=1}^n \sum \limits_{j=0}^{a_j} p_i^{j}$ **完全平方數(shù)的約數(shù)個(gè)數(shù)為奇數(shù)個(gè)，因?yàn)榧s數(shù)成對(duì)存在，證畢** **$[1, n]$的完全平方數(shù)為$\sqrt{n}$個(gè)，顯然這不用證明因?yàn)槊總€(gè)數(shù)都是完全平方數(shù)的約數(shù)** ## Basic operator $a\mid b$ ： a能夠整除b， b能夠被a整除 $a \nmid b$ : a不能夠整除b， b不能夠被a整除帶余數(shù)除法：若a,b時(shí)兩個(gè)整數(shù)，其中b>0，則存在兩個(gè)整數(shù)q及r，使得 $a=bq + r$ 且 $0 \leq r \textless b$ , 且q和r唯一，此處b時(shí)商，r是余數(shù) (0除以任何不為0的數(shù)都等于0， 0不能作為除數(shù)) ### 模運(yùn)算 $(a + b) \bmod m = (a \bmod m + b \bmod m) \bmod m $ $(a-b) \bmod m = (a \bmod m - b \bmod m) \bmod m$ $(a*b)\bmod m = ((a \bmod m) * (b \bmod m)) \bmod m$ 通常為了**規(guī)避減法異號(hào)**的情況，我們通常這樣操作 $(a-b) \bmod m = ((a \bmod m) - (b \bmod m) + m) \bmod m$ **除法的取模需要使用逆元** ### 上取整與下取整 ```C++ int x = 9, y = 3; // 上取整 int res = (x - 1) / y ; // 下取整 int res = x / y; // 四舍五入 int res = (x + y / 2) / y; 也可以用cmath的庫函數(shù), 但是必須保證傳入為double即小數(shù) // 上取整 int res = ceil((x * 1.0) / y); // 下取整 int res = floor((x * 1.0) / y); // 四舍五入 int res = round((x * 1.0) / y); ``` #### 向上取整證明 ![image-20221221183520292](https://cdn.jsdelivr.net/gh/JackLee404/typora/images/image-20221221183520292.png) 預(yù)處理MAXN之前的數(shù)的約數(shù) ```c++ void init() { for(int i = 1; i <= MAXN; i ++) { for(int j = i; j <= MAXN; j += i) { factors[j].push_back(i); } } } ``` ## 快速冪 $O(\sqrt{n})$ n為指數(shù) ### 分治 ```c++ double fast_pow(double a, int n) { if (n == 1) return a; double t = fast_pow(a, n / 2); if (n % 2 == 1) return t * t * a; else return t * t; } ``` ### Bit $O(logn)$ ```C++ int fast_pow(double a, int b) { double ans = 1; while (b) { if (b & 1) ans *= a; a *= a; b>>=1; } return ans; } ``` ## 康托展開 ```C++ ``` ## GCD-最大公因數(shù) ### GCD and LCM properties 更相損減術(shù)：$\gcd(a,b) = \gcd(b, a-b)$ 輾轉(zhuǎn)相除法：$\gcd(a,b) = \gcd(b,a \bmod b)$ 證明：$d\mid a, d \mid b$等價(jià)于$d\mid(a-b)$, $d|b$（充要條件） LCM最小公倍數(shù)： $lcm(a,b) = \frac{a*b}{\gcd(a,b)}$ 常記為 $[a,b]$ 1) 可重復(fù)貢獻(xiàn) $\gcd(a, b, c) = \gcd(\gcd(a, b), c) = \gcd(a, \gcd(b, c))$ （可以推廣到n個(gè)數(shù)的情況） 2) $\gcd(a, 0) = a$ 3. $\gcd(a, b) = \gcd(a, -b)$ 4. $\gcd(x, x-1) = 1$ LCM的一些性質(zhì): 1. $lcm(a,b)$, 若a或b為質(zhì)數(shù)，則$lcm(a, b) = a * b$; 2. $lcm(a,b)$, 若$b \mid a$, 則$lcm(a,b) = a$ 3. $lcm(x, x - 1) = x * (x - 1)$ 常用構(gòu)造題: 對(duì)于給定的a, b在某個(gè)區(qū)間, 這里假設(shè) $l \le a, b\le r$ 1. $lcm(a,ka)$ 使lcm最小 2. $lcm(a,b)$, $gcd(a,b) = 1$, 使$lcm$最大證明: 假定$a \le b$, 1. $b \bmod a = 0$，$lcm(a,b) = b$, $l \le b \le r$ 2. $b \bmod a \ne 0$, $lcm(a,b) \ge 2 * b$ $ie. 2 * l \le lcm \le 2 * r$ ## 輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法：$\gcd(a,b) = \gcd(b,a \bmod b)$ 證明: 描述a與b的帶余數(shù)除法關(guān)系，$a = kb + r$ 設(shè)d為a和b的因數(shù), 有$d \mid a$, $d \mid b$, 因?yàn)?r = a - kb$ , 所以 $d|r$, 因此d是$b, r$的公約數(shù)（為什么不寫成$a, r$, 因?yàn)?r = a - kb$ 的因子有可能超出b的因子范圍，如$6 * 5$ 此時(shí)6也可以作為因子，所以為了限制該條件我們用b來作為另一個(gè)數(shù)) 因此$gcd(a,b) = gcd(b, a \bmod b)$ ```c++ int gcd(int a, int b) {return b == 0?a:gcd(b, a % b);} ``` ## 裴蜀定理設(shè)a,b是不全為零的整數(shù)，則存在整數(shù)x,y使得 $ax + by = \gcd(a, b)$ （可以理解為，該方程有解，且為最小正元） [LuogP4549](https://www.luogu.com.cn/problem/P4549) ```c++ #include <iostream> #include <vector> using namespace std; int gcd(int a, int b) { return b == 0?a:gcd(b, a % b); } int main() { int n, last; cin >> n; vector<int> a(n); last = 0; for (int i = 0; i < a.size(); i ++) { cin >> a[i]; if (a[i]<0) a[i]*=-1; last = gcd(last, a[i]); } cout << last; } ``` [OIWIKI](https://oiwiki.org/math/number-theory/bezouts/) [Wikipedia](https://zh.wikipedia.org/zh-cn/%E8%B2%9D%E7%A5%96%E7%AD%89%E5%BC%8F) ## 類歐幾里得算法類似于歐幾里得形式的算法，需要求出f(a,b), 通過變換形式，使問題規(guī)模越來越小，最終求得解。 ## 擴(kuò)展歐幾里得算法考慮一個(gè)二元一次不定方程: $ax + by = c$ (a, b, c為整數(shù)且a, b都不為0) 定理1: 設(shè)它有整數(shù)解$x = x_0, y = y_0,$則一切整數(shù)解可以寫成$x = x_0 - b_1t, y = y_0 + a_1t,\space(t = 0, 1, -1, 2, -2, ...)$ 其中$b_1 = \frac{a}{\gcd(a, b)}$, $a_1 = $$\frac{\gcd(a,b)}$ > 證明: >充分性: 已知$ax_0 + by_0 = c,$ 可得$a(x_0 - b_1t) + b(y_0 + a_1t) = ax_0 + by_0 + t(ba_1-ab_1) = ax_0 + by_0 = c$ > 必要性: 設(shè)$x', y'$是$ax+by=c$的任意解, 則$ax' + by' = c$已知$ax_0 + by_0 =c$兩式相減,得$a(x' - x_0) + b(y' - y_0) = 0$, 除公因數(shù)，得$a_1(x'-x0) = -b_1(y' - y_0)$, 觀察式子, 既然$a_1$與$b_1$互質(zhì)，那么$ a_1 \mid (y'-y_0) $. 可得$y'=y_0 + a_1t$. 同理可得$x'=x_0-b_1t$ 定理2：一般式$ax+by = c$ 有整數(shù)解的充要條件是$\gcd(a, b) | c$ > 證明： > 必要性：若有整數(shù)解則$\gcd(a,b)|(ax + by)$, 故$\gcd(a,b)|c$ > 充分性：若$\gcd(a,b)|c$則由裴蜀定理 $ax+by=\gcd(a,b)$ 一定存在解，則對(duì)其解乘以$\frac{c}{\gcd(a,b)}$ 便為$ax+by=c$的解 > 因此對(duì)于任給的$ax+by=c$ 且 $\gcd(a,b) \mid c$，則找到了一組特解，便可以得到所有解. 求 $ax_1 + by_1 = \gcd(a, b)$ > 思路： > 求$ax_1+by_1=\gcd(a,b)$, 由于$\gcd(a,b)==\gcd(b, a \bmod b)$,我們可以先求出$bx_2 +(a \bmod b)y_2=\gcd(b, a \bmod b)$的解，再通過找到這兩條式子的解的關(guān)系而得出原式子的解。關(guān)系：$x_1 = y_2, y_1 = x_2 - \lfloor a/b \rfloor * y_2$ > 證明：$ax_1 + by_1 = \gcd(a,b) = \gcd(a, a \bmod b) = bx_2 + (a \bmod b)y_2 = bx_2 + (a - \lfloor a / b \rfloor * b)y_2=ay_2+b(x_2 - \lfloor a / b \rfloor y_2)$ 在通過類歐幾里得算法得到該特解后，那么我們根據(jù)**定理1** 即可求得所有解。擴(kuò)展歐幾里得也可以用來求線性同余式。 CODE: ```C++ int exgcd(int a, int b, int &x, int &y) { if (b == 0) { x = 1, y = 0; // 得到一組解返回，然后通過解的關(guān)系得到通解 return a; } int d = exgcd(b, a % b, x ,y); int tmp = x; x = y,y = tmp - a / b * y; return d; } ``` ## 同余和逆元 ### 同余定義：給定一個(gè)正整數(shù)m，把他叫做模，如果用m對(duì)任意兩個(gè)正整數(shù)a,b取模所得余數(shù)相同，我們就說a,b對(duì)模m同余，記作$a \equiv b \pmod m$,取模所得余數(shù)不同記作$a \not \equiv b \pmod m$ $a \bmod m = b \bmod m 等價(jià)于 a \equiv b (\bmod m) $ 第二定義：若$m \mid a-b$, 則a,b叫做對(duì)模m同余性質(zhì)1：若 $a \equiv b \pmod m$ , 則 $\gcd(a,m) = \gcd(b, m)$ 性質(zhì)2：若 $a \equiv b \pmod m$, 則$ka \equiv kb \pmod m$ 性質(zhì)3：若$a \equiv b \pmod m$，則$a = da_1, b = db_1, \gcd(d, m) = 1$ 則 $a_1 \equiv b_1 \pmod m$ ### 同余式定義：若用$f(x)$表示系數(shù)為整數(shù)的多項(xiàng)式；又設(shè)m是一個(gè)正整數(shù)，則$f(x) \equiv 0 \pmod m$ 叫做模m的同余式。一次同余式：$ax \equiv b \pmod m, a \not \equiv 0 \pmod m$ 使同余式成立的x叫做該式的一個(gè)解。定理：一次同余式（又叫線性同余方程）由解的充要條件是$\gcd(a, m) \mid b$ > 證：一次同余式可以寫成$ax=my+b$. 移項(xiàng)，得$ax-my=b$, 因$y$無關(guān)緊要, 令$y = -y$,得$ax+my=b$.一條二元一次不定方程。由定理2，證畢。 ### 逆元方程$ax \equiv 1 \pmod m$的一個(gè)解$x$，**稱$x$為a模m的逆元**。其中$\gcd(a,m)=1$ 由同余性質(zhì)，因?yàn)?\gcd(a, m) = 1$ 上述等式可以寫成 $x \equiv \frac{1}{a} \pmod m$ 逆元的一個(gè)重要應(yīng)用就是求除法的模 (k為b的逆元) $\because (kb \bmod m) = 1$ $\frac{a} \bmod m = ((\frac{a} \bmod m)(kb \bmod m)) \bmod m = ak \bmod m$ 逆元求法： 1. 擴(kuò)展歐幾里得定理解方程 2. 費(fèi)馬小定理直接用快速冪求$a^{p-2}$, 注意$p$是質(zhì)數(shù)，另外$a \bmod p = 0$時(shí)無解。 ## 費(fèi)馬小定理若p是素?cái)?shù)，則$a^p \equiv a \pmod p$ 因?yàn)?$\gcd(a, p) = 1$, 由同余性質(zhì)，上述式子也可以寫成$a^{p-1} \equiv 1 \pmod p$ > 定理證明： > > 集合$\left\{ 1,2,3...p-1 \right\}$中的每一個(gè)數(shù)模p的值互不相同。有一個(gè)數(shù)a不是p的倍數(shù)，集合$\left \{a,2a,3a,4a,...a(p-1) \right \}$中每一個(gè)數(shù)模p的值也互不相同（1），是$1,2,3,...,p-1$的一種排列。 > > 那么$(p-1)! \equiv a * 2 * a * 3 ... * (p-1)*a \pmod b$, 左右除以$(p-1)!$（2）。 > > 得到 $1 \equiv a^{p-1} \bmod p$.左右同乘一個(gè)a，得證。 > > 1）證明：若$x \not \equiv y \pmod p$, $ax \equiv ay \bmod p$ > > 2） $\gcd(p, (p-1)!) = 1$, （按照前所述性質(zhì)）可以直接除。應(yīng)用： **求逆元**，可以得到 $\frac{1}{a} \equiv a^{p-2} \pmod p$ 所以a的一個(gè)逆元就是 $a^{p-2} \bmod p$ (這里可以用快速冪來求) [Loj-P3811](https://www.luogu.com.cn/problem/P3811) fast_pow ```C++ #include <iostream> typedef long long bl; using namespace std; const int N = 600; int n, p; bl fast_pow(bl a, bl n) { bl ans = 1; while(n) { if (n & 1) ans *= a % p, ans %= p; a *= a % p, a %= p; n >>= 1; } return ans; } int main() { cin >> n >> p; for (int i = 1; i <= n; i ++) { cout << fast_pow(i, p - 2) << "\n"; } } ``` ex_gcd ```c++ #include <iostream> typedef long long bl; using namespace std; const int N = 600; int n, p; int ex_gcd(bl a, bl b, bl &x, bl &y) { if (!b) { x = 1, y = 0; return a; } int d = ex_gcd(b, a%b, x, y); int tmp = x; x = y, y = tmp - a / b * y; return d; } int main() { cin >> n >> p; for (int i = 1; i <= n; i ++) { bl x, y; ex_gcd(i, p, x, y); x = (x % p + p) % p; cout << x << "\n"; } } ``` ## 唯一分解定理任意一個(gè)大于1的整數(shù)都可以表示為質(zhì)數(shù)的乘積，即任一大于1的整數(shù) $a=p_1p_2p_3...p_n , p_1 \leq p_2 \leq ... \leq p_n$ 我們也可以將相同質(zhì)數(shù)寫在一起： $a=p_1^{a^1}p_2^{a^2}..p_n^{a^n}$, $a_i \textgreater 0, i=1,2,3,...,k$ (標(biāo)準(zhǔn)分解式) 由唯一分解定理，也不難得到gcd和lcm的表達(dá)式： $(a,b) = p_1^{min(a1,b1)}p_2^{min(a2,b2)}p_3^{min(a3,b3)}$ $[a,b] = p_1^{max(a1,b1)}p_2^{max(a2,b2)}p_3^{max(a3,b3)}$ 有時(shí)候我們需要對(duì)gcd取模的時(shí)候，我們可以用上述方法來求. 試除法分解素因子 $\Theta(\sqrt{n})$ ```C++ /* 關(guān)于試除法的證明，每輪循環(huán)i可以保證，n當(dāng)中不包含2~i的質(zhì)因子，因此第i輪循環(huán)一定不包含2~i-1的質(zhì)因子，因此，如果n%i==0的i也一定不包含2~i-1的質(zhì)因子(i整除n)，因此iy */ void divide(int x) { for (int i = 2; i <= x / i; i ++ ) if (x % i == 0) { int s = 0; while (x % i == 0) x /= i, s ++ ; cout << i << ' ' << s << endl; } if (x > 1) cout << x << ' ' << 1 << endl; cout << endl; } ``` 一般做題時(shí)有更優(yōu)的方法，即預(yù)處理求出1~n素?cái)?shù)(篩法)，然后直接枚舉素?cái)?shù)約掉素因子。試除法求約數(shù) $O(\sqrt{n})$ ```c++ /* 對(duì)于每個(gè)數(shù)x, 在1~n的約數(shù)，可以記為 n / x; 所以求和 n + n/2 + n/3 + .. + 1 = nlogn */ vector<int> res; void get_divisors(int n) { for(int i = 1; i <= n / i; i ++) { if(n % i == 0) { res.push_back(i); if(i != n / i) res.push_back(n / i); } sort(res.begin(), res.end()); } } ``` ## 素?cái)?shù)篩 ### 埃氏篩埃氏篩中每個(gè)合數(shù)可能會(huì)被篩去多次,復(fù)雜度為$O(n\log \log n)$ ```c++ /* 埃氏篩基本原理：用當(dāng)前質(zhì)數(shù)去篩掉（2~n)的合數(shù) 如果當(dāng)前枚舉的數(shù)是合數(shù)，因?yàn)槠渌匾蜃觩<n, 并且每次循環(huán)保證p的所有倍數(shù)（kp <= n)都被篩掉，所以一定能夠篩掉當(dāng)前的數(shù) */ int primes[N], cnt; // primes[]存儲(chǔ)所有素?cái)?shù) bool st[N]; // st[x]存儲(chǔ)x是否被篩掉 void get_primes(int n) { for (int i = 2; i <= n; i ++ ) { if (st[i]) continue; primes[cnt ++ ] = i; for (int j = i + i; j <= n; j += i) st[j] = true; } } ``` ### 線性篩（歐拉篩）線性篩彌補(bǔ)了上述缺點(diǎn)，保證所有數(shù)只被篩去一次，復(fù)雜度為$O(N)$ ```C++ /* 線性篩基本原理：（用i的最小質(zhì)因子篩取i，保證了復(fù)雜度為O(N) 枚舉2 ~ n / i的質(zhì)數(shù)，如果我們枚舉到質(zhì)數(shù)且當(dāng)前質(zhì)數(shù)pj % i == 0，對(duì)于(1~j)的質(zhì)數(shù)一定滿足p是p*i的最小的質(zhì)因子因?yàn)槲覀兦蟮臅r(shí)1~n的素?cái)?shù)所以保證上界pj <= n / i */ void get_primes(int n) { for (int i = 2; i <= n; i ++ ) { if (!st[i]) primes[cnt ++ ] = i; for (int j = 0; primes[j] <= n / i; j ++ ) { st[primes[j] * i] = true; if (i % primes[j] == 0) break; } } } ``` ## 歐拉函數(shù) > 定義： > > $\varphi(n)$表示的是小于等于n并且和n互質(zhì)的數(shù)的個(gè)數(shù)。 $\varphi(1)=1$, $\varphi(p) = p - 1$(p為質(zhì)數(shù)) > > 性質(zhì)：積性函數(shù)（如果$\gcd(a,b)=1$,那么$\varphi(a*b)=\varphi(a)*\varphi(b)$) > > 公式： > > ![image-20230101214307428](https://cdn.jsdelivr.net/gh/JackLee404/typora/images/image-20230101214307428.png) > > > 證明：![image-20221203195608016](https://cdn.jsdelivr.net/gh/JackLee404/typora/images/image-20221203195608016.png) > > 這里給出自己的理解, 歐拉函數(shù)就求1~n以內(nèi)的與n互質(zhì)的數(shù)的個(gè)數(shù)，我們用篩取n的質(zhì)數(shù)的倍數(shù)的方法來求，即為篩取$k \times p_i$, 由于同一個(gè)數(shù)被篩去多次，那么問題轉(zhuǎn)化為容斥原理，下面不求證了直接用公式 **CODE(Acwing):** $O(\sqrt{n})$ ```c++ int phi(int x) { int res = x; for (int i = 2; i <= x / i; i ++ ) if (x % i == 0) { res = res / i * (i - 1); // 這里原公式時(shí) 1 - 1 / pi 由于浮點(diǎn)數(shù)問題，我們先整除后乘 while (x % i == 0) x /= i; } if (x > 1) res = res / x * (x - 1); return res; } ``` 篩法 $O(N)$ 求1~n的每個(gè)數(shù)的歐拉函數(shù)值 ```c++ int primes[N], cnt; // primes[]存儲(chǔ)所有素?cái)?shù) int euler[N]; // 存儲(chǔ)每個(gè)數(shù)的歐拉函數(shù) bool st[N]; // st[x]存儲(chǔ)x是否被篩掉 void get_eulers(int n) { euler[1] = 1; for (int i = 2; i <= n; i ++ ) { if (!st[i]) { primes[cnt ++ ] = i; euler[i] = i - 1; } for (int j = 0; primes[j] <= n / i; j ++ ) { int t = primes[j] * i; st[t] = true; if (i % primes[j] == 0) { euler[t] = euler[i] * primes[j]; // 互質(zhì)包含了1-p_i 直接在n位置加一個(gè)相乘即可 break; } euler[t] = euler[i] * (primes[j] - 1); // 不包含 p_i* （1- 1 / p_i) = p_i - 1 } } } ``` ## 歐拉定理若a與n互質(zhì)，則$a^{\phi(m)} \equiv 1 (\bmod m)$. $\phi(n)為歐拉函數(shù)$ > 證明： > > 設(shè)$x_1, x_2, ... , x_{\phi(n)}$ 為1~n中與n互質(zhì)的數(shù) > > 設(shè)序列 $p_1 = ax_1, p_2 = ax_2 ... p_{\phi(n)} = ax_{\phi(n)}$ > > Lemma1: $p \bmod m$ 兩兩不同余 > > Lemma2: $p \bmod n$的每個(gè)結(jié)果都與m互質(zhì) > > Lemma3: 若$(r_1 * r_2) \bmod m = r_2, 其中r_1,r_2均與m互質(zhì), 則 r_1 = 1$ > > 由兩個(gè)引理1， 2得， $p \bmod m$ 是對(duì)$x_1, x_2, ... x_{\phi(m)}$的映射 > > 所以有 > > $(\prod \limits^{\phi(m)}_{i = 1} p_i) \bmod m = (\prod \limits^{\phi(m)}_{i = 1} x_i) \bmod m$ > > => $(a^{\phi(m)}\prod \limits^{\phi(m)}_{i = 1} x_i) \bmod m = (\prod \limits^{\phi(m)}_{i = 1} x_i) \bmod m$ > > 由引理3 > > => $a^{\phi(m)} \bmod m = 1$ 對(duì)于歐拉定理，顯然費(fèi)馬小定理是歐拉定理的特例，即$m$為質(zhì)時(shí)， $\phi(m) = m - 1$, 帶入等式與費(fèi)馬小定理結(jié)果相同關(guān)于引理的證明參考這個(gè)[視頻](https://www.bilibili.com/video/BV1tK411f78z/?spm_id_from=333.999.0.0) ## 中國剩余定理 $m_1, m_2, ... m_n$兩兩互質(zhì)，求 $x \equiv a_1 (\bmod m), x \equiv a_2 (\bmod m), ... ,x\equiv a_n(\bmod m)$的一組解。 $M = m_1m_2...m_n$ $M_i = \frac{M}{m_i}$ $x = a_1 M_1 M_1^{-1} + a_2 M_2 M_2^{-1} + ... + a_n M_n M_n^{-1}$ 求逆元可以用擴(kuò)歐 ## 高斯消元初等行列變換： 1. 把某一行乘一個(gè)非零的數(shù) 2. 交換某兩行 3. 把某行的若干倍加到第三行通過初等行列變換將方程換成上三角的形式。結(jié)果分為三種： 1. 完美階梯型唯一解 2. 出現(xiàn)無解式如0 = 非零無解 3. 0 = 0 無窮多組解算法過程枚舉每一列c 1. 找到當(dāng)前列絕對(duì)值最大的一行 2. 把這一行換到最上面 3. 將該行的第一個(gè)數(shù)變成1（系數(shù)同時(shí)除） 4. 把下面所有行的第c列消為0 通過消去可以得到階梯行列式 ![image-20230124215605816](https://cdn.jsdelivr.net/gh/JackLee404/typora/images/image-20230124215605816.png) ## 求組合數(shù) ### 遞推 $O(n^2)$ $C_a^b = C_{a-1}^b + C_{a-1}^{b-1}$ ```c++ #include <iostream> using i64 = long long; const int N = 2010, mod = 1e9 + 7; int c[N + 10][N + 10]; void init() { for(int i = 0; i < N; i ++) { for(int j = 0; j <= i; j ++) { if(!j) c[i][j] = 1; else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod; } } } int main() { init(); int n; std::cin >> n; while(n --) { int a, b; std::cin >> a >> b; std::cout << c[a][b] << "\n"; } } ``` ### 逆元預(yù)處理 $O(nlogn)$ $C_a^b = \frac{a!}{(b-a)!b!} \bmod p = a! \times ((b-a)!)^{-1} \times (b!)^{-1}$ , 這里$-1$指$數(shù)論倒數(shù)$即$逆元$ 所以預(yù)處理好上面的數(shù)即可求解, 逆元數(shù)組部分因?yàn)?ax \equiv 1(\bmod p), by \equiv 1(\bmod p) 則ax \times by \equiv 1(\bmod p)$ ```c++ #include <iostream> #include <algorithm> using i64 = long long; typedef long long LL; const int N = 100010, mod = 1e9 + 7; int fact[N], infact[N]; int fast_pow(int a, int b, int mod) { int res = 1; while(b) { if(b & 1) res = (LL)res * a % mod; a = (LL)a * a % mod; b >>= 1; } return res; } int main() { fact[0] = infact[0] = 1; for(int i = 1; i < N; i ++) { fact[i] = (LL)fact[i - 1] * i % mod; infact[i] = (LL)infact[i - 1] * fast_pow(i, mod - 2, mod) % mod; } int n; std::cin >> n; while(n --) { int a, b; std::cin >> a >> b; std::cout << (LL)fact[a] * infact[b] % mod * infact[a- b] % mod << "\n"; } } ``` 也有$O(n)$做法，需要線性預(yù)處理逆元 ### 盧卡斯定理 $C_a^b \equiv C_{a \bmod p}^{a \bmod p} \times C_{a/p}^{b/p}(\bmod p)$ $O(p + Tlogp)$ ![image-20230127201803872](https://cdn.jsdelivr.net/gh/JackLee404/typora/images/image-20230127201803872.png) ```C++ #include <bits/stdc++.h> using i64 = long long; i64 p; int fast_pow(int a, int k) { int res = 1; while(k){ if(k & 1) res = (i64)res * a % p; a = (i64)a * a % p; k >>= 1; } return res; } int C(int a, int b) { int res = 1; for(int i = 1, j = a; i <= b; i ++, j --) { res = (i64)res * j % p; res = (i64)res * fast_pow(i, p - 2) % p; } return res; } int lucas(i64 a, i64 b) { if(a < p && b < p) return C(a, b); return (i64)C(a % p, b % p) * lucas(a / p, b / p) % p; } int main() { int n; std::cin >> n; while(n --) { i64 a, b; std::cin >> a >> b >> p; std::cout << lucas(a, b) << "\n"; } } ``` ### 高精度-組合數(shù) 1. 分解質(zhì)因數(shù) 2. 寫高精度乘法 ```C++ #include <iostream> #include <algorithm> #include <vector> using i64 = long long; const int N = 5010; int primes[N], cnt; int sum[N]; bool st[N]; void get_primes(int n) { for(int i = 2; i <= n; i ++) { if(!st[i]) primes[cnt ++] = i; for(int j = 0; primes[j] <= n / i; j ++) { st[primes[j] * i] = true; if(i % primes[j] == 0) break; } } } int get(int n, int p) { int res = 0; while(n) { res += n / p; n /= p; } return res; } std::vector<int> mul(std::vector<int> a, int b) { std::vector<int> c; int t = 0; for(int i = 0; i < a.size(); i ++) { t += a[i] * b; c.push_back(t % 10); t /= 10; } while(t) { c.push_back(t % 10); t /= 10; } return c; } int main() { int a, b; std::cin >> a >> b; get_primes(a); for(int i = 0; i < cnt; i ++) { int p = primes[i]; sum[i] = get(a, p) - get(a - b, p) - get(b, p); } std::vector<int> res; res.push_back(1); for(int i = 0; i < cnt; i ++) for(int j = 0; j < sum[i]; j ++) res = mul(res, primes[i]); for(int i = (int)res.size() - 1; i >= 0; i --) std::cout << res[i]; } ``` ## 容斥原理復(fù)雜度計(jì)算 $C_n^1 + C_n^2 + ... + C_n^3 + ... + C_n^n = 2^n - C_n^0 = 2^n - 1$ $O(2^n)$ $\abs{S_1 \cup S_2 \cup S_3 ... \cup S_n} = \sum \limits_i\abs{S_i} - \sum \limits_{i \cdot j}\abs{S_i \cup S_j} + \sum \limits_{i \cdot j \cdot k}\abs{S_i \cup S_j \cup S_k} - ...$ > 簡單證明：假設(shè)集合中的某個(gè)元素$x$，在上述等式中被算了$k$次，則 > > $C_k^1 - C_k^2 + C_k^3 - C_k^4 + ... + (-1)^{k - 1}C_k^k = 1$ [能被整除的數(shù)](https://www.acwing.com/problem/content/892/) ```c++ #include <bits/stdc++.h> using i64 = long long; const int N = 1e5 + 10; int p[N], n, m, res = 0; int main() { int n, m, ans = 0; std::cin >> n >> m; for(int i = 0; i < m; i ++) { std::cin >> p[i]; } for(int i = 1; i < 1 << m; i ++) { int t = 1; int s = 0; for(int j = 0; j <= m - 1; j ++) { if(i >> j & 1) { if((i64)p[j] * t > n) { s = -1; break; } s ++; t *= p[j]; } } if(s == -1) continue; if(s & 1) ans += n / t; else ans -= n / t; } std::cout << ans << "\n"; } ``` ## 勒讓那多定理 Legendre 定理在正數(shù)$n!$的質(zhì)因數(shù)分解中, 質(zhì)數(shù)$p$ 的指數(shù)記作$v_p(n!)$,則有等式$v_p(n!)=\sum\limits_{j=1}^{\infty} \lfloor\frac{n}{p^k} \rfloor$ ```C++ LL f(LL n, LL p) { if (n == 0) return 0; n /= p; return n + f(n, p); } ``` ## 博弈 ### 對(duì)稱博弈 [牛牛取石子](http://www.rzrgm.cn/jacklee404/articles/17053387.html) 下模仿棋就不會(huì)吃虧 ### 公平組合游戲 ICG 兩個(gè)玩家交替游戲，每個(gè)玩家可執(zhí)行操作相同，不能行動(dòng)玩家判負(fù) ### 有向圖游戲給定有向無環(huán)圖，圖中有唯一起點(diǎn)，在起點(diǎn)放有一枚棋子。兩名玩家交替行動(dòng)，每次移動(dòng)一個(gè)邊，無法移動(dòng)玩家為負(fù)。任何公平組合游戲可以轉(zhuǎn)化為有向圖游戲。 ### Nim Game $a_1 \oplus a_2 .. . \oplus ... a_n = 0$為必?cái)B(tài)，否則為必勝態(tài) ```C++ #include <bits/stdc++.h> using i64 = long long; const int N = 1e5 + 10; int a[N]; int main() { int n, ok = 0; std::cin >> n; for(int i = 1; i <= n; i ++) { std::cin >> a[i]; ok ^= a[i]; } std::cout << (ok?"Yes":"No"); } ``` ### 臺(tái)階NIM ### 集合NIM 指定取數(shù)集合$S$，進(jìn)行NIM游戲單個(gè)$SG(a_i)$為0時(shí)為必?cái)?，否則必勝，對(duì)所有$i$轉(zhuǎn)為都為0時(shí)為必?cái)B(tài)，此時(shí)轉(zhuǎn)為NIM游戲問題 $SG(a_1) \oplus SG(a_2) \oplus ... SG(a_n) = 0$ 必勝，否則必?cái)? ```C++ #include <bits/stdc++.h> #include <cstring> #define FOR(i, n) for(int i = 1; i <= n; i ++) using i64 = long long; const int N = 110, M = 10010; int n, m; int s[N], f[M]; int sg(int x) { if(f[x] != -1) return f[x]; std::unordered_set<int> S; for(int i = 0; i < m; i ++) { int sum = s[i]; if(x >= sum) S.insert(sg(x - sum)); } for(int i = 0; ; i ++) { if(!S.count(i)) return f[x] = i; } } int main() { std::cin >> m; for(int i = 0; i < m; i ++) std::cin >> s[i]; std::cin >> n; memset(f, -1, sizeof f); int res = 0; for(int i = 0; i < n; i ++) { int x; std::cin >> x; res ^= sg(x); } std::cout << (res?"Yes":"No"); } ``` ### SG函數(shù) 有向圖游戲中，對(duì)于每個(gè)節(jié)點(diǎn)$x$,設(shè)從$x$出發(fā)共有$k$條有向邊，分別到達(dá)節(jié)點(diǎn)$y_1, y_2, ...,y_k$的SG函數(shù)構(gòu)成的集合在執(zhí)行$Mex(S)$運(yùn)算的結(jié)果即 $SG(x) = Mex({SG(y_1), SG(y_2), ..., SG(y_k)})$ 特別地，整個(gè)有向圖游戲$G$的$SG$函數(shù)值被定義為有向圖的起點(diǎn)$s$的$SG$函數(shù)值，即$SG(G) = x$ >有向圖游戲的某個(gè)局面必勝，當(dāng)且僅當(dāng)該局面對(duì)應(yīng)節(jié)點(diǎn)的SG函數(shù)值大于0 > >有向圖游戲的某個(gè)局面必?cái)。?dāng)且僅當(dāng)該局面對(duì)應(yīng)節(jié)點(diǎn)的SG函數(shù)值等于0 ### Mex運(yùn)算設(shè)$S$表示一個(gè)非負(fù)整數(shù)集合。定義$Mex(S)$為不屬于集合$S$的最小最非負(fù)整數(shù)運(yùn)算。即 $Mex(S) = min(x)$, $x$屬于自然數(shù)，且$x$不屬于$S$ 如$Mex(\{0, 1, 3\})$為$2$ ## 卡特蘭特?cái)?shù) 給定 $n$ 個(gè) $0$ 和 $n$ 個(gè) $1$，它們將按照某種順序排成長度為 $2n$ 的序列，求它們能排列成的所有序列中，能夠滿足任意前綴序列中 $0$ 的個(gè)數(shù)都不少于 $1$ 的個(gè)數(shù)的序列有多少個(gè)。 $C_{2n}^{n} - C_{2n}^{n - 1} = \frac{C_{2n}^{n}}{n + 1}$ ## 勒讓那多定理 Legendre 定理在正數(shù)$n!$的質(zhì)因數(shù)分解中, 質(zhì)數(shù)$p$ 的指數(shù)記作$v_p(n!)$,則有等式$v_p(n!)=\sum\limits_{j=1}^{\infty} \lfloor\frac{n}{p^k} \rfloor$ ```C++ LL f(LL n, LL p) { if (n == 0) return 0; n /= p; return n + f(n, p); } ``` # Geometry ## 二維幾何 ### 坐標(biāo)旋轉(zhuǎn) 對(duì)于平面直角坐標(biāo)系下的坐標(biāo)$(x, y)$ 順時(shí)針旋轉(zhuǎn)$\theta°$ 后的坐標(biāo) \\]

\begin{pmatrix}
x & y
\end{pmatrix}
\times
\begin{pmatrix}
cos\theta & sin\theta \
-sin\theta & cos\theta \
\end{pmatrix}

\[\]

posted on 2022-06-24 11:37 Jack404 閱讀(109) 評(píng)論(0) 收藏舉報(bào)

刷新頁面返回頂部

This is my template for Algorithm Contest

Basic algorithm

前綴異或

前綴和

差分

位運(yùn)算

異或

二分

Some suffixes

1. Qucikly read for const numbers

2. Header

First : Tree

1. Heap

2. Segment Tree

3. Cartesian Tree

Graph

1. Topological sort (Kath)

2. Topological sort (DFS)

3. Dijkstra (normal)

4. Dijkstra (Heap)

5. Bellman-ford

6. SPFA

7. Floyd

8. Kruskal

9. Prim (normal)

10. Prim(Heap)

11. Dyeing about Bipartite Graph

12. Hungarian algorithm

13.DSU

String

1. KMP

Math

基本定理

Basic operator

模運(yùn)算

上取整與下取整

向上取整證明

快速冪

分治

Bit

康托展開

GCD-最大公因數(shù)

GCD and LCM properties

輾轉(zhuǎn)相除法

裴蜀定理

類歐幾里得算法

擴(kuò)展歐幾里得算法

同余和逆元

同余

同余式

逆元

費(fèi)馬小定理

唯一分解定理

素?cái)?shù)篩

埃氏篩

線性篩（歐拉篩）

歐拉函數(shù)

歐拉定理

中國剩余定理

高斯消元

求組合數(shù)

遞推 \(O(n^2)\)

逆元預(yù)處理 \(O(nlogn)\)

盧卡斯定理

高精度-組合數(shù)

容斥原理

勒讓那多定理

博弈

對(duì)稱博弈

公平組合游戲 ICG

有向圖游戲

Nim Game

臺(tái)階NIM

集合NIM

SG函數(shù)

Mex運(yùn)算

卡特蘭特?cái)?shù)

勒讓那多定理

Geometry

二維幾何