模板整理

jiangly算法模板收集 - hh2048 - 博客园

常用技巧

快读

用的比较少

//1.
inline int read() {
    bool sym = false; int res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}
//2.
char *p1, *p2, buf[100000];
#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++)
int read() {
    int x = 0, f = 1;
    char ch = nc();
    while (ch < 48 || ch > 57) {
        if (ch == '-')
            f = -1;
        ch = nc();
    }
    while (ch >= 48 && ch <= 57)
        x = x * 10 + ch - 48, ch = nc();
    return x * f;
}

对拍

前提需要一个暴力正解

对于以下新建的. cpp 文件全部都需要先编译再使用。

新建 BaoLi.cpp 文件存放暴力且正确的代码，Curr.cpp 存放现在不确定正确性/不知道哪里错误的代码。

对于 BaoLi.cpp 文件开头加上：

freopen("data.in", "r", stdin);
freopen("BaoLi.out", "w", stdout);

对于 Curr.cpp 文件开头加上：

freopen("data.in", "r", stdin);
freopen("Curr.out", "w", stdout);

新建 rand.cpp 文件写入随机数方便对拍，现给出示例：

#include<bits/stdc++.h>
using namespace std;
int main() {
    struct _timeb T;
    _ftime(&T);
    srand(T.millitm);
    //生成随机数种子，利用 timeb 生成毫秒级别随机数

    // freopen("in.txt", "w", stdout);
    freopen("data.in", "w", stdout);                        //注意：该程序生成的数据到data.in中
    // int t = rand() % 5;//若为多组数据
    // cout << t << "\n";
    // while (t--) {
	// 	//Random opration ... 
    // }
}

新建.cpp 文件或者.bat 文件进行对拍：

对于 Duipai.bat 文件：

@echo off
:loop
rand.exe
Curr.exe
BaoLi.exe
fc Curr.out BaoLi.out
if not errorlevel 1 goto loop
pause
:end

对于 Duipai.cpp 文件：

#include<bits/stdc++.h>
using namespace std;
int main() {
    while (1)
    {
        system("rand.exe > in.txt");
        system("BaoLi.exe < in.txt > BaoLi.txt");
        system("Curr.exe < in.txt > Curr.txt");
        if (system("fc Curr.txt BaoLi.txt")) //当 fc 返回 1 时，说明这时数据不一样
            break;                          //不一样就跳出循环
    }
}

若对拍停止，说明出现了不一样的输出

data.in 文件为输入数据，BaoLi.out 为暴力的输出数据，Curr.out 为现在代码的输出数据。

关于 `__int128`

表示范围为： $- 2^{127} \sim 2^{127} - 1 > 10^{38}$

这个类型不能直接输出，且在这个范围内进行位运算需要：((__int128_t)1 << m)

配套输入输出详见：long long 不够用？详解 __int128 - FReQuenter - 博客园

输出：

void print(__int128 x) {
    if (x > 9)print(x / 10);// if (x < 0)putchar('-'), x = -x;//负数使用
    putchar(x % 10 + '0');
}

gcc __gnu 私货

pbds：Policy-Based Data Structures

在命名空间__gnu_pbds 中，使用这个库的函数比手写和 STL 更快

浅析C++gnu pbds库 - FBIWZH - 博客园

一般使用 PBDS 库是使用平衡树和 hash

__pbds 在 c++11 gcc4.60 就支持了，c++11 及其以上肯定能用

_pbds 中的平衡树

和 STL 中的 set 相比：(即换为高级版 set)

都能始终保持集合有序，快速增加删除元素，快速查找某个数是否存在（一个元素也都只能出现一次）
但是 pbds 还能快速获取某个数的排名，快速索引第 $k$ 位数 (相当于给 set 加入了下标功能)

声明平衡树：tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> s，

template<typename T>
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

成员函数：

插入：s.insert(val) 这个函数还有返回值 pair 类型。

pair<iterator, bool> 第一个位置代表返回插入值的迭代器，第二个值代表是否插入成功

删除：s.erase(val) 或 s.erase(s.lower_bound(val)) (推荐)

查找：

find_by_order(k): 返回下标为 $k$ 的对象的指针

order_of_key (val) 返回小于 val 的个数

lower_bound/upper_bound(val) 和 STL 同理

empty() 返回是否为空

size() 返回大小

join (x)：将 x 树并入当前树，前提是两棵树的类型一样，x 树被删除。

split (x, b)：以 Cmp_Fn 比较，小于等于 x 的属于当前树，其余的属于 b 树。

和 STL 中的 multiset 相比：(即换为高级版 multiset)

声明平衡树：tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> s

将 less<int> 修改为 less_equal<int> 即可。

template<typename T>
using ordered_multiset = tree<int, null_type, less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>;

注意： 换为 less_equal 后，lower_bound/upper_bound 功能互换了，且删除元素必须删除其迭代器

其他函数相同。

对于自定义数据类型的平衡树：：需要自己添加比较规则

将 less_equal<int> 位置替换为 cmp 即可。

题目：洛谷题单平衡树部分：P3369 【模板】普通平衡树 - 洛谷 | 计算机科学教育新生态

代码：

void solve() {
    ordered_multiset<int> s;
    int n;cin >> n;
    while (n--) {
        int op;cin >> op;
        int x;cin >> x;
        if (op == 1) { //插入x
            s.insert(x);
        } else if (op == 2) { //删除一个x
            s.erase(s.upper_bound(x));
        } else if (op == 3) { //输出排名={比当前数小的个数+1}
            cout << s.order_of_key(x) + 1 << '\n';
        } else if (op == 4) { //查询排名为x的数
            cout << *s.find_by_order(x - 1) << '\n';
        } else if (op == 5) { //求前驱：小于x最大的数
            cout << *(--s.upper_bound(x)) << '\n';
        } else {//求后继：大于x最小的数
            cout << *(s.lowerx_bound(x)) << '\n';
        }
    }
}

_pbds 中的字典树

声明：trie<string,null_type,trie_string_access_traits<>,pat_trie_tag,trie_prefix_search_node_update>

using tr = trie<string,null_type,trie_string_access_traits<>,pat_trie_tag,trie_prefix_search_node_update>;
//第一个参数必须为字符串类型，tag也有别的tag，但pat最快，与tree相同，node_update支持自定义

tr.insert(s); //插入s 
tr.erase(s); //删除s 
tr.join(b); //将b并入tr 
pair//pair的使用如下：
pair<tr::iterator,tr::iterator> range=base.prefix_range(x);
foriterator it=range.first;it!=range.second;it++
	cout<<*it<<' '<<endl;
//pair中第一个是起始迭代器，第二个是终止迭代器，遍历过去就可以找到所有字符串了。

题目： 1414. Astronomical Database @ Timus Online Judge 或洛谷题单字符串字典树部分

代码：

void solve() {
    pref_trie tr;
    tr.insert("sun");
    char ch;
    while (cin >> ch) {
        string s;cin >> s;
        if (ch == '+') {
            tr.insert(s);
        } else {
            cout << s << '\n';
            auto range = tr.prefix_range(s);
            int t = 0;
            for (auto it = range.first;t < 20 && it != range.second;it++, t++) {
                cout << "  " << *it << '\n';
            }
        }
    }
}

PS：在字典树模板题中正常写 TLE 了，目前还不知道如何解决。

_pbds 中的 hash

堆和 hash 一样，在 stl 中都有对应的函数，跑的比 STL 要快，不被卡的情况下使用 STL 足够。

视作 map/unordered_map 使用，且常数小，很快

分为 gp_hash_table 和 cc_hash_table，但是 gp_hash_table 性能要好一些(但是都要好于 map/unordered_map)。gp_hash_table 和 unordered_map 一样容易被卡。

gp_hash_table 在 CF 上防止被卡的方法：

#include<chrono>
#include<ext/pb_ds/assoc_container.hpp>//hash_table的库，如果嫌麻烦可以换成pbds万能头
const int RANDOM = std::chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
    inline int operator()(int x) const {
        return x ^RANDOM;
    }
};
__gnu_pbds::gp_hash_table
        < /* <key类型名> */ int, 
          /* <value类型名> */ int, 
          chash >table;

这里与 map 的不同点：

这里无 count() 函数，只能 {c++}find(x)==end() 查询是否存在

_cxx 中的 rope

在命名空间 __gnu_cxx 中

(<-先挖坑->)

【可持久化线段树？！】rope史上最全详解 - 大本营 - 博客园

rope test;

test.push_back(x);//在末尾添加x

test.insert(pos,x);//在pos插入x　　

test.erase(pos,x);//从pos开始删除x个

test.copy(pos,len,x);//从pos开始到pos+len为止用x代替

test.replace(pos,x);//从pos开始换成x

test.substr(pos,x);//提取pos开始x个

test.at(x)/[x];//访问第x个元素

题目： P3919 【模板】可持久化线段树 1（可持久化数组）

代码：

#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;
const int MAXM = 1e6;
int N, M;
rope<int>* S[MAXM + 10];
int readint() {
    int f = 1, r = 0;char c = getchar();
    while (!isdigit(c)) { if (c == '-')f = -1; c = getchar(); }
    while (isdigit(c)) { r = r * 10 + c - '0';c = getchar(); }
    return f * r;
}
int main() {
    N = readint();M = readint();
    S[0] = new rope<int>();
    S[0]->append(0);
    for (int i = 1;i <= N;i++)
        S[0]->append(readint());
    for (int i = 1;i <= M;i++) {
        int v, k, a, b;
        v = readint();k = readint();
        S[i] = new rope<int>(*S[v]);//从指定版本生成新版本（只换根）
        if (k == 1) {
            a = readint();b = readint();
            S[i]->replace(a, b);
        } else {
            a = readint();
            printf("%d\n", S[i]->at(a));
        }
    }
}

常用算法

先更新一些最常用的算法模板，若变形多有必要说明。

更多详见 oi.wiki

基础算法 & Trick

对于基础算法/trick对于部分进行简要说明即可：

离散化
单调队列：
单调栈
常用函数及其作用：bitset，iota，
位运算技巧

离散化：(vector)

// std::vector<int> arr;
vector<int> tmp(arr);  // tmp 是 arr 的一个副本
sort(tmp.begin(), tmp.end());
tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
for (int i = 0; i < n; ++i)
  arr[i] = lower_bound(tmp.begin(), tmp.end(), arr[i]) - tmp.begin();
// rank[i] = arr[i] + 1

普通数组

// arr[i] 为初始数组,下标范围为 [1, n]

for (int i = 1; i <= n; ++i)  // step 1
  tmp[i] = arr[i];
std::sort(tmp + 1, tmp + n + 1);                          // step 2
int len = std::unique(tmp + 1, tmp + n + 1) - (tmp + 1);  // step 3
for (int i = 1; i <= n; ++i)                              // step 4
  arr[i] = std::lower_bound(tmp + 1, tmp + len + 1, arr[i]) - tmp;

单调队列

用于求滑动窗口或与其他算法连用

以滑动窗口求窗口最小/大值为例子：

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)
        cin >> a[i];

    deque<int> maxq, minq;

    for (int i = 1;i <= n;i++) {
        while (!minq.empty() && a[i] <= a[minq.back()])
            minq.pop_back();
        minq.push_back(i);

        if (i >= k) {
            while (!minq.empty() && minq.front() < i - k + 1)
                minq.pop_front();
            cout << a[minq.front()] << ' ';
        }
    }
    cout << '\n';

    for (int i = 1;i <= n;i++) {
        while (!maxq.empty() && a[i] >= a[maxq.back()])
            maxq.pop_back();
        maxq.push_back(i);

        if (i >= k) {
            while (!maxq.empty() && maxq.front() < i - k + 1)
                maxq.pop_front();
            cout << a[maxq.front()] << ' ';
        }
    }
    cout << '\n';
}

单调栈

在实际比赛中用的较多

求解的是对于下标 $i$ 后面第一个大于 $a_{i}$ 的下标(若有变形只需要变 > 和 for 循环的遍历顺序即可)

void solve() {
    int n;cin >> n;
    vector<int> a(n + 1), f(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    vector<int> stk;
    for (int i = 1;i <= n;i++) {
        while (stk.size() && a[i] > a[stk.back()])f[stk.back()] = i, stk.pop_back();
        stk.push_back(i);
    }
    for (int i = 1;i <= n;i++)cout << f[i] << " ";
}

Trick//

....

循环的一些 trick： C++ - SWPUACM Wiki - 一些常用的循环

搜索 & DP

搜索 (双向搜索，记忆化)(主要随题目而定)

搜索//

...

最长上升子序列

最长上升子序列：lower
最长不下降子序列：upper
最长下降子序列：lower,greater
最长不上升子序列：upper, greater

void solve() {
	vector<int> d;
    for (auto x : inputArray) {
        auto it = lower_bound(d.begin(), d.end(), x);
        if (it == d.end()){
	        d.push_back(x);
        } else {
	        *it = x;
        }
    }
    cout << d.size() << '\n';
}

背包 DP

01 背包：对于每一种物品只有选 (1 次)或不选

for (int i = 1;i <= n;i++) {
	for (int j = m;j >= v[i];j--) {
		f[j] = max(f[j], f[j - v[i]] + a[i]);
	}
}

完全背包：每种物品可以选择任意次 $[0, \infty)$

for (int i = 1;i <= n;i++) {
	for (int j = v[i];j <= m;j++) {
		f[j] = max(f[j], f[j - v[i]] + a[i]);
	}
}

多重背包：每种物品可以选择 $[0, s_{i}]$ 件

P1776 宝物筛选 - 洛谷 | 计算机科学教育新生态
朴素算法： $O (N M \sum k_{i})$

for (int i = 1;i <= n;i++) {
	for (int j = m;j >= v[i];j--) {
		for (int k = 0;k <= s[i] and k * v[i] <= j;k++) {
			f[j] = max(f[j], f[j - k * v[i]] + k * a[i]);
		}
	}
}

二进制优化： $O (N M \sum \log k_{i})$
转化为 01 背包解决问题

int f[M], v[N * (lenK)_2], w[N * (lenK)_2];
void solve() {
    int n, m;cin >> n >> m;
    int cnt = 0;
    for (int i = 1;i <= n;i++) {
        int b, a, k;cin >> b >> a >> k;
        for (int j = 1;j <= k;j <<= 1) {
            v[++cnt] = j * a;w[cnt] = j * b;k -= j;
        }
        if (k)v[++cnt] = k * a, w[cnt] = k * b;
    }
    for (int i = 1;i <= cnt;i++) {
        for (int j = m;j >= v[i];j--) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    cout << f[m] << '\n';
}

单调队列优化： $O (N M)$

int f[40010], g[40010];
int main() {
    int n, W;cin >> n >> W;       //宝物种数,最大载重
    for (int i = 1;i <= n;i++) {  //枚举宝物
        memcpy(g, f, sizeof(f));  //f备份到g       
        int v, w, m;cin >> v >> w >> m;        //价值 重量 数量
        for (int j = 0;j < w;j++) {  //分拆成w个类 
            deque<int> q;            //单调队列
            for (int k = j;k <= W;k += w) { //滑动窗口[k-m*w,k-w]
                while (!q.empty() && q.front() < k - m * w) q.pop_front();
                while (!q.empty() && g[k] >= g[q.back()] + (k - q.back()) / w * v) q.pop_back();
                q.push_back(k);
                if (!q.empty()) f[k] = max(g[k], g[q.front()] + (k - q.front()) / w * v);
            }
        }
    }
    cout << f[W] << '\n';
}

混合背包：01 背包+完全背包+分组背包

遇到混合背包问题，可以将多重背包和 01 背包用二进制优化一起处理，而完全背包单独处理。

分组背包：所有物品分为若干组，对于每组背包中的物品，最多只能选择一个

分组背包不能使用二进制/单调队列优化

for (int i = 1;i <= n;i++) {  
    for (int j = m;j >= 1;j--) 
        for (int k = 0;k <= s[i];k++) 
            if (j >= v[i][k]) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);//v[i][k]代表第i组第k个
}

或在线读入

for (int i = 1;i <= n;i++) { 
    // 对于每一组的物品
    cin >> s;
    for (int j = 1;j <= s;j++) cin >> v[j] >> w[j];
    for (int j = m;j >= 1;j--) 
        for (int k = 0;k <= s;k++) 
            if (j >= v[k]) f[j] = max(f[j], f[j - v[k]] + w[k]);
}

求背包方案数：

01 背包：

int f[N], c[N];
// f[i]表示背包容量为i时最优选法的总价值
// c[i]表示背包容量为i时最优选法的方案数

void solve() {
    int n, m, v, w;
    cin >> n >> m;
    for (int i = 0;i <= m;i++) c[i] = 1;

    for (int i = 1; i <= n; i++) {    //枚举物品
        cin >> v >> w;
        for (int j = m; j >= v; j--) {  //枚举体积
            if (f[j - v] + w > f[j]) {      //装新物品总价值更大
                f[j] = f[j - v] + w;
                c[j] = c[j - v];
            } else if (f[j - v] + w == f[j]) //装新物品总价值相等
                c[j] = (c[j] + c[j - v]) % mod;
        }
    }
    cout << c[m] << '\n';
}

恰好装满的 01 背包

int f[N], c[N];
// f[i]表示背包容量为i时最优选法的总价值
// c[i]表示背包容量为i时最优选法的方案数

void solve() {
    int n, m, v, w;
    cin >> n >> m;
    for (int i = 0;i <= m;i++) f[i] = -1000;
    f[0] = 0;c[0] = 1;

    for (int i = 1; i <= n; i++) {    //枚举物品
        cin >> v >> w;
        for (int j = m; j >= v; j--) {  //枚举体积
            if (f[j - v] + w > f[j]) {      //装新物品总价值更大
                f[j] = f[j - v] + w;
                c[j] = c[j - v];
            } else if (f[j - v] + w == f[j]) //装新物品总价值相等
                c[j] = (c[j] + c[j - v]) % mod;
        }
    }
    cout << c[m] << '\n';
}

区间 DP//

...

状压 DP//

...

树形类专题//

数位DP，概率 DP，轮廓线DP 待学

(插头 DP 不学)

TODO: 将后面的东西整理到上面去，将学过的东西巩固好，将没有学的知识点整理好(能弄懂如何使用即可)

数据结构：

链表
并查集(还有启发式合并)
堆：对顶堆，配对堆，左偏树等(还未学习)
单调栈，单调队列
ST 表 (解决可重复贡献问题)
树状数组，线段树及其变形 (需要详细介绍，大篇幅，尽可能例举多的例子)
分块，可持久化...，树链剖分， (暂不总结)
搜索树与平衡树 (暂不总结)

链表

以 ABC344 E 为例

两种查询：

1 x y：在 $A$ 中元素 $x$ 后面紧接着插入 $y$ 。当给出此查询时，保证 $x$ 存在于 $A$ 中。
2 x：从 $A$ 中删除元素 $x$ 。当给出此查询时，保证 $x$ 存在于 $A$ 中。

void solve() {
    int n;cin >> n;
    list<int> a;
    map<int, list<int>::iterator> mp;
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;a.push_back(x);mp[x] = prev(a.end());
    }
    int q;cin >> q;
    while (q--) {
        int op;cin >> op;
        if (op == 1) {
            int x, y;cin >> x >> y;
            mp[y] = a.insert(next(mp[x]), y);
        } else {
            int x;cin >> x;
            a.erase(mp[x]);
        }
    }
    for (auto i : a)cout << i << " ";
}

并查集

jiangly 的板子：

注：这个板子是以 0 为起点下标的，若想要 1 为起点下标只需将 init 函数的 $n$ 修改为 $n + 1$ 或声明 $d s u (n + 1)$ 。

struct DSU {
    vector<int> f, siz;

    DSU() {}
    DSU(int n) {
        init(n);
    }

    void init(int n) {
        f.resize(n);
        iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }

    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }

    int size(int x) {
        return siz[find(x)];
    }
};

若是扩展域/带权/可持久化/可撤销 并查集视具体情况处理。

ST 表

jiangly 板子

ST 表能解决的问题也可以使用线段树解决，但线段树常数较大，且 ST 表每次 $O (1)$ 查询

struct ST {
    const int n, k;
    vector<int> in1, in2;
    vector<vector<int>> Max, Min;
    ST(int n) : n(n), in1(n + 1), in2(n + 1), k(__lg(n)) {
        Max.resize(k + 1, vector<int>(n + 1));
        Min.resize(k + 1, vector<int>(n + 1));
    }
    void init() {
        for (int i = 1; i <= n; i++) {
            Max[0][i] = in1[i];
            Min[0][i] = in2[i];
        }
        for (int i = 0, t = 1; i < k; i++, t <<= 1) {
            const int T = n - (t << 1) + 1;
            for (int j = 1; j <= T; j++) {
                Max[i + 1][j] = max(Max[i][j], Max[i][j + t]);
                Min[i + 1][j] = min(Min[i][j], Min[i][j + t]);
            }
        }
    }
    int getMax(int l, int r) {
        if (l > r) {
            swap(l, r);
        }
        int k = __lg(r - l + 1);
        return max(Max[k][l], Max[k][r - (1 << k) + 1]);
    }
    int getMin(int l, int r) {
        if (l > r) {
            swap(l, r);
        }
        int k = __lg(r - l + 1);
        return min(Min[k][l], Min[k][r - (1 << k) + 1]);
    }
};

记得 st.init()

线段树//

树状数组//

图论：

最短路：dijkstra，spfa，johnson 全源最短路等
最小生成树：kruskal，prim
拓扑排序
二分图
求强连通分量等连通性相关
2-SAT
树上问题：树的直径，重心，LCA，树链剖分，树上启发式合并，虚树，换根DP等
欧拉图

字符串：

hash
字典树 (trie)
KMP 算法
Z 函数 (扩展 KMP)
Manacher(马拉车)
AC 自动机
后缀数组
后缀自动机 (SAM)
后缀树等等

数学：

筛法，逆元 (几种方式)
~~高精度...
快速幂&矩阵快速幂
gcd & exgcd
同余方程
威尔逊定理
欧拉定理
裴蜀定理
中国剩余定理

(数学相关知识非常多，其他未学的暂时不总结)

筛法

线性筛： $O (n)$

minp[i] 代表 $i$ 的最小质因数，primes[i] 代表质数

vector<int> minp, primes;

void sieve(int n) {
    minp.assign(n + 1, 0);
    primes.clear();
    
    for (int i = 2; i <= n; i++) {
        if (minp[i] == 0) {
            minp[i] = i;
            primes.push_back(i);
        }
        
        for (auto p : primes) {
            if (i * p > n) break;
            minp[i * p] = p;
            if (p == minp[i]) break;
        }
    }
}

求欧拉函数：

phi[i] 代表 $φ (x)$

vector<int> minp, primes, phi;

void sieve(int n) {
    minp.assign(n + 1, 0);
    phi.assign(n + 1, 0);
    primes.clear();
    phi[1] = 1;

    for (int i = 2; i <= n; i++) {
        if (minp[i] == 0) {
            minp[i] = i;
            primes.push_back(i);
            phi[i] = i - 1;
        }

        for (auto p : primes) {
            if (i * p > n) break;
            minp[i * p] = p;
            if (p == minp[i]) {
                phi[i * p] = phi[i] * p;
                break;
            } 
            phi[i * p] = phi[i] * phi[p];
        }
    }
}

求莫比乌斯函数

vector<int> minp, primes, mu;

void sieve(int n) {
    minp.assign(n + 1, 0);
    mu.assign(n + 1, 0);
    primes.clear();

    for (int i = 2; i <= n; i++) {
        if (minp[i] == 0) {
            minp[i] = i;
            primes.push_back(i);
            mu[i] = -1;
        }

        for (auto p : primes) {
            if (i * p > n) break;
            minp[i * p] = p;
            if (p == minp[i]) {
                mu[i * p] = 0;
                break;
            }
            mu[i * p] = -mu[i];
        }
    }
}

求约数个数

(约数： $a | b \to a$ 是 $b$ 的约数) d[i] 是约数个数，num[i] 是最小质因子的次数

vector<int> minp, primes, d, num;

void sieve(int n) {
    minp.assign(n + 1, 0);
    d.assign(n + 1, 0);
    num.assign(n + 1, 0);
    primes.clear();

    for (int i = 2; i <= n; i++) {
        if (minp[i] == 0) {
            minp[i] = i;
            primes.push_back(i);
            d[i] = 2;num[i] = 1;
        }

        for (auto p : primes) {
            if (i * p > n) break;
            minp[i * p] = p;
            if (p == minp[i]) {
                num[i * p] = num[i] + 1;
                d[i * p] = d[i] / num[i * p] * (num[i * p] + 1);
                break;
            }
            num[i * p] = 1;
            d[i * p] = d[i] * 2;
        }
    }
}

求约数和

f[i] 代表约数和，g[i] 代表最小质因子的 $p^{0} + p^{1} + \dots + p^{k}$

vector<int> minp, primes, g, f;

void sieve(int n) {
    minp.assign(n + 1, 0);
    g.assign(n + 1, 0);
    f.assign(n + 1, 0);
    primes.clear();

    for (int i = 2; i <= n; i++) {
        if (minp[i] == 0) {
            minp[i] = i;
            primes.push_back(i);
            g[i] = i + 1;
            f[i] = i + 1;
        }

        for (auto p : primes) {
            if (i * p > n) break;
            minp[i * p] = p;
            if (p == minp[i]) {
                g[i * p] = g[i] * p + 1;
                f[i * p] = f[i] / g[i] * g[i * p];
                break;
            }
            g[i * p] = 1 + p;
            f[i * p] = f[i] * f[p];
        }
    }
}

乘法逆元

费马小定理： $x \equiv a^{b - 2} (\mod b)$ 。 $p$ 为质数才成立

扩展欧几里得算法的应用场景(要求： $gcd (a, b) = 1$ )

void exgcd(int a, int b, int& x, int& y) {//x 是a在膜b意义下的逆元
  if (b == 0) {
    x = 1, y = 0;
    return;
  }
  exgcd(b, a % b, y, x);
  y -= a / b * x;
}

扩展欧几里得算法，给定一个整数对 $(a, b)$ 作为输入，找到一个整数对 $(x, y)$ ，使得 $a x + b y = \pm \gcd (a, b)$ ，时间复杂度为 $O (\log min (| a |, | b |))$ 。（这里，整数对 $x, y$ 保证是满足 $max (| x |, | y |) \leq max (| a |, | b |)$ 的整数。）

线性递推求逆元(对 $p$ 不是质数也适用)

//开ll
int inv[1000000];
void find_inv(int last, int p)
//求1~last所有数模p意义下的逆元
{
    inv[1] = 1;//1的逆元就是1本身
    for (int i = 2;i <= last;i++)
        inv[i] = (p - p / i) * (inv[p % i]) % p;
}

求任意 $n$ 个数的逆元

s[0] = 1;
for (int i = 1; i <= n; ++i) s[i] = s[i - 1] * a[i] % p;
sv[n] = qpow(s[n], p - 2);
// 当然这里也可以用 exgcd 来求逆元,视个人喜好而定.
for (int i = n; i >= 1; --i) sv[i - 1] = sv[i] * a[i] % p;
for (int i = 1; i <= n; ++i) inv[i] = sv[i] * s[i - 1] % p;

高斯消元

加法方程组

auto gauss = [&](int n)->void {//作为模板，后续不再说明
	for (int i = 1;i <= n;i++) {
		int mx = i;
		for (int j = 1;j <= n;j++) {
			if (j < i && abs(a[j][j]) >= eps)continue;
			if (abs(a[j][i]) > abs(a[mx][i])) {
				mx = j;
			}
		}
		swap(a[i], a[mx]);
		if (abs(a[i][i]) < eps)continue;
		double tmp = a[i][i];
		for (int j = i;j <= n + 1;j++) {
			a[i][j] /= tmp;
		}
		for (int j = 1;j <= n;j++) {
			if (i == j)continue;
			double rate = a[j][i] / a[i][i];
			for (int k = i;k <= n + 1;k++) {
				a[j][k] -= a[i][k] * rate;
			}
		}
	}
	};
gauss(n);

异或方程组

可以使用 bitset 优化

        // 高斯消元解决异或方程组模版
    auto gauss = [&](int n)->void {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (j < i && a[j][j] == 1) continue;
                if (a[j][i] == 1) {
                    swap(a[i], a[j]);
                    break;
                }
            }
            if (a[i][i] == 0)continue;
            for (int j = 1; j <= n; j++) {
                if (i == j || a[j][i] == 0)continue;
                for (int k = i; k <= n + 1; k++) {
                    a[j][k] ^= a[i][k];
                }
                //a[j] ^= a[i] //bitset优化
            }
        }
        };

同余方程组

    auto gauss = [&](int n) {
        for (int i = 1;i <= n;i++) {
            for (int j = 1;j <= n;j++) {
                if (j < i && a[j][j] != 0)continue;
                if (a[j][i] != 0) {
                    swap(a[i], a[j]);break;
                }
            }
            if (a[i][i] == 0)continue;
            for (int j = 1;j <= n;j++) {
                if (i == j || a[j][i] == 0)continue;
                int d = __gcd(a[j][i], a[i][i]);
                int x = a[i][i] / d, y = a[j][i] / d;
                if (j < i && a[j][j] != 0) {
                    a[j][j] = (a[j][j] * x) % mod;
                }
                for (int k = i;k <= n + 1;k++) {
                    a[j][k] = ((a[j][k] * x - a[i][k] * y) % mod + mod) % mod;
                }
            }
        }
        for (int i = 1;i <= n;i++) {
            if (a[i][i] != 0) {
                int ok = 0;
                for (int j = i + 1;j <= n;j++) {
                    if (a[i][i] != 0) {
                        ok = 1;break;
                    }
                }
                if (!ok) {
                    a[i][n + 1] = a[i][n + 1] * inv(a[i][i]) % mod;
                    a[i][i] = 1;
                }
            }
        }
        };

线性基

贪心法

    auto insert = [&](int x) {//模板类型
        for (int i = 63;i >= 0;i--) {
            if (x >> i & 1) {
                if (bsc[i] == 0) {
                    bsc[i] = x;return 1;//插入成功
                }
                x ^= bsc[i];
            }
        }
        return 0;
        };
    // for (int i = 1;i <= n;i++)insert(a[i]);

对于贪心法来说，若要排序，则需要在这基础上再次消元

    for (int i = 63;i >= 0;i--) {//在原来的基础上再次消元
        for (int j = i - 1;j >= 0;j--) {
            if (bsc[i] >> j & 1)bsc[i] ^= bsc[j];
        }
    }
    // for (int i = 0;i <= 63;i++) {
    //     if (bsc[i])a.push_back(bsc[i]); //从小到大排序后的bac[i]
    // }
    // int zero = a.size() != n;

高斯消元法

注：数组 $a$ 需要开大些

从大到小排序

    int len = 1;
    for (int i = 50;i >= 0;i--) {
        for (int j = len;j <= n;j++) {
            if (a[j] >> i & 1) {
                swap(a[j], a[len]);break;
            }
        }
        if ((a[len] >> i & 1) ^ 1)continue;//这一步若开vector(n+1) 则会出错
        for (int j = 1;j <= n;j++) {
            if (j == len || (a[j] >> i & 1 ^ 1))continue;
            a[j] ^= a[len];
        }
        len++;
    }
    len--;

    int zero = len != n;

矩阵快速幂 & 矩阵乘法

只需要推出矩阵对应关系即可

struct Matrix {
    int n, m;
    int v[maxn][maxn] = {};
    void init() {
        for (int i = 1;i <= n;i++)
            for (int j = 1;j <= m;j++) {
                if (i == j)v[i][j] = 1;
                else v[i][j] = 0;
            }
    }
    Matrix(int n, int m) :n(n), m(m) {}
    Matrix operator* (const Matrix B) const {
        Matrix C(n, B.m);
        for (int i = 1;i <= n;i++)
            for (int j = 1;j <= B.m;j++)
                for (int k = 1;k <= m;k++)
                    C.v[i][j] += v[i][k] * B.v[k][j], C.v[i][j] %= mod;
        return C;
    }
    // void print() {
    //     for (int i = 1;i <= n;i++)
    //         for (int j = 1;j <= m;j++)
    //             cout << v[i][j] << " \n"[j == m];
    // }
};

对于斐波那契数列：

    Matrix A(2, 1), B(2, 2);
    A.v[1][1] = A.v[2][1] = 1;
    B.v[1][2] = B.v[2][1] = B.v[2][2] = 1;

    auto qpow = [&](int b) {
        while (b) {
            if (b & 1) A = B * A;
            B = B * B;b >>= 1;
        }
        };
    qpow(n - 2);
    cout << A.v[2][1] << '\n';

裴蜀定理：

设 $a, b$ 是不全为零的整数，则存在整数 $x, y$ , 使得 $a x + b y = g c d (a, b)$ .
()设 $a, b$ 是不全为零的整数，若 $d > 0$ 是 $a, b$ 的公因数，且存在整数 $x, y$ , 使得 $a x + b y = d$ ，则 $d = g c d (a, b)$

特殊地，设 $a, b$ 是不全为零的整数，若存在整数 $x, y$ , 使得 $a x + b y = 1$ ，则 $a, b$ 互质。

对自然数 $a$ 、 $b$ 和整数 $n$ ， $a$ 与 $b$ 互素，考察不定方程： $a x + b y = n$
可表示的数与不可表示的数在区间 $[0, C]$ 对称（关于 $C$ 的一半对称）。 $0$ 可被表示， $C$ 不可被表示；负数不可被表示，大于 $C$ 的数可被表示。

中国剩余定理

用于求解线性同余方程组的最小非负整数解 (要求 $m_{i}$ 为两两互质的整数)

计算所有模数乘积： $M = Π m_{i}$
对于第 $i$ 个方程，计算 $c_{i} = \frac{M}{m_{i}}$
计算 $c_{i}$ 在摸 $m_{i}$ 意义下的乘法逆元 $c_{i}^{- 1}$
$x = \sum_{i = 1}^{n} r_{i} c_{i} c_{i}^{- 1}$

若不一定为两两互质的整数则中国剩余定理不可用，需要扩展中国剩余定理。

扩展中国剩余定理:......

TODO：

字符串

DP

图论

gcd 和 exgcd 相关问题

计算几何：

还未学(但需要学习)

其他的算法遇到再总结。

其他：

01 分数规划+其他算法结合

杂/暂时不管

最短路

dijkstra：邻接表:

void solve() {
    int n, m, s;cin >> n >> m >> s;
    vector<pair<int, int>> g[n + 1];
    while (m--) {
        int u, v, w;cin >> u >> v >> w;
        g[u].push_back({v,w});
    }
    vector<int> dis(n + 1, INT_MAX), vis(n + 1);dis[s] = 0;
    priority_queue<pair<int, int>>q;q.push({0,s});
    while (q.size()) {
        auto [p, u] = q.top();q.pop();
        if (vis[u])continue;
        vis[u] = 1;
        for (auto [v, w] : g[u]) {
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;q.push({-dis[v],v});
            }
        }
    }
    for (int i = 1; i <= n; i++)
        cout << dis[i] << " ";
}

链式前向星：()

SPFA：

struct edge {
  int v, w;
};

vector<edge> e[maxn];
int dis[maxn], cnt[maxn], vis[maxn];
queue<int> q;

bool spfa(int n, int s) {
  memset(dis, 63, sizeof(dis));
  dis[s] = 0, vis[s] = 1;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop(), vis[u] = 0;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        cnt[v] = cnt[u] + 1;  // 记录最短路经过的边数
        if (cnt[v] >= n) return false;
        // 在不经过负环的情况下，最短路至多经过 n - 1 条边
        // 因此如果经过了多于 n 条边，一定说明经过了负环
        if (!vis[v]) q.push(v), vis[v] = 1;
      }
    }
  }
  return true;
}

拓扑排序相关

// deg 是入度，在存图的时候需要录入数据
// A 是排序后的数组
int deg[MAXN], A[MAXN];
bool toposort (int n)
{
    int cnt = 0;
    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (!deg[i])
            q.push (i);
    while (!q.empty ())
    {
        int t = q.front ();
        q.pop ();
        A[cnt++] = t;
        for (auto to : edges[t])
        {
            deg[to]--;
            if (!deg[to]) // 出现了新的入度为 0 的点
                q.push (to);
        }
    }
    return cnt == n;
}