DSU

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#define N 200005

struct DSU {
    int n;
    vector<int> par, h;

    explicit DSU(int _n) : n(_n + 1), par(_n + 1), h(_n + 1) {
        for (int i = 1; i <= _n; ++i)par[i] = i;
    };

    int find(int x) {
        return par[x] != x ? par[x] = find(par[x]) : par[x];
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y)return;
        if (h[x] == h[y]) {
            h[x]++;
            par[y] = x;
        } else h[x] < h[y] ? par[x] = y : par[y] = x;
    }

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

manacher

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// p数组存放
#define N 11000007
struct MLC {
    int n{}, p[2 * N + 2]{};
    char t[N * 2 + 3]{}, s[N + 2]{};

    void manacher() {
        n = (int) strlen(s + 1);
        int m = 0;
        t[++m] = '#';
        for (int i = 1; i <= n; ++i) t[++m] = s[i], t[++m] = '#';
        int mid = 0, r = 0;
        for (int i = 1; i <= m; ++i) {
            if (i > r) p[i] = 1;
            else p[i] = min(p[2 * mid - i], r - i + 1);
            while (i - p[i] > 0 && i + p[i] <= m && t[i - p[i]] == t[i + p[i]]) ++p[i];
            if (i + p[i] - 1 > r) mid = i, r = i + p[i] - 1;
        }
    }
} manacher{};

// 判断一个子串是不是回文串
void checkSubPalindrome() {
	int l, r, len;
	cin >> l >> r;
	len = r - l + 1;
	int t = manacher.p[l + r];
	if (t >= len) cout << "YES" << endl;
    else cout<<"NO"<<endl;
}
// 用来求字符串中的最长回文串的长度
void getMaxPalindrome() {
	int ans = 0;
	for (int i = 1; i <= m; ++i) ans = max(ans, p[i]);
	cout << ans - 1;
}

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>

#define N 1000006
using namespace std;

int lps[N << 1];
char s[N], p[N << 1];


signed main() {
    cin.tie(nullptr), cout.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> (s + 1) >> (p + 1);
    int n = (int) strlen(s + 1), m = (int) strlen(p + 1);
    p[m + 1] = '#';
    for (int i = 1, j = m + 2; i <= n; ++i, ++j) p[j] = s[i];
    for (int i = 2, j = 0; i <= n + m + 1; ++i) {
        while (j && p[i] ^ p[j + 1]) j = lps[j];
        j += p[i] == p[j + 1];
        if ((lps[i] = j) == m) cout << (i - 2 * m) << '\n';
    }
    for (int i = 1; i <= m; ++i) cout << lps[i] << ' ';
    return 0;
}

exkmp

用于解决在线性复杂度的限制下统计s中每一位字符开始最多可以匹配多少位p中的字符，或者求一个字符串s和它任意后缀的最长公共前后缀的长度，与KMP算法的next数组的区别是，一个是到s[i]结束，一个是从字符s[i]开始。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
#define int long long
#define N 20000007
using namespace std;

int n,m,z[N*2];
char s[N],p[N*2];

void exkmp(){
    n = (int)strlen(s+1);
    m = (int)strlen(p+1);
    p[m+1] = '~';
    for(int i = m+2,j = 1;j<=n;++i,++j) p[i] = s[j];
    int l = 1,r = 0;
    for(int i = 2;i<=n+m+1;++i){
        if(i<=r) z[i] = min(z[i-l+1],r-i+1);
        while(i+z[i]<=n+m+1 && p[z[i]+1] == p[z[i] + i]) ++z[i];
        if(i + z[i] - 1 > r) l = i,r = i + z[i] - 1;
    }
    z[1] = m;
    int Z = 0,P = 0;
    //for(int i = 0;i<=m+n+1;++i)cout<<z[i]<<' ';
    for(int i = 1;i<=m;++i) z[i] = i*(z[i]+1),Z ^= z[i];
    for(int i = m+2;i<=m+n+1;++i) z[i] = (i - m - 1) * (z[i] + 1), P ^= z[i];
    cout<<Z<<endl<<P;
}

signed main(){
    scanf("%s%s",s+1,p+1);
    exkmp();
    return 0;
}

Trie

给定 $n$ 个模式串 $s_1, s_2, \dots, s_n$ 和 $q$ 次询问，每次询问给定一个文本串 $t_i$，请回答 $s_1 \sim s_n$ 中有多少个字符串 $s_j$ 满足 $t_i$ 是 $s_j$ 的前缀。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>

//#define int long long
#define N 3000006
using namespace std;

int n, m, nxt[N][62], cnt;
int tot[N];
char str[N];

int getNum(char x) {
    if (x >= 'A' && x <= 'Z') return x - 'A';
    else if (x >= 'a' && x <= 'z') return x - 'a' + 26;
    else return x - '0' + 52;
}

void insert(char s[]) {
    int len = (int) strlen(s), now = 0;
    for (int i = 0, x; i < len; ++i) {
        x = getNum(s[i]);
        if (!nxt[now][x]) nxt[now][x] = ++cnt;
        now = nxt[now][x];
        ++tot[now];
    }
}

void find(char s[]) {
    int len = (int) strlen(s), now = 0;
    bool ok = true;
    for (int i = 0, x; i < len && ok; ++i) {
        x = getNum(s[i]);
        if (!nxt[now][x]) ok = false;
        else now = nxt[now][x];
    }
    if (!ok) cout << 0 << '\n';
    else cout << tot[now] << '\n';
}

void solve() {
    for (int i = 0; i <= cnt; ++i)
        for (int j = 0; j < 62; ++j)
            nxt[i][j] = 0;
    for (int i = 0; i <= cnt; ++i) tot[i] = 0;
    cnt = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> str, insert(str);
    for (int i = 1; i <= m; ++i)
        cin >> str, find(str);
}

signed main() {
    cin.tie(nullptr), cout.tie(nullptr);
    ios::sync_with_stdio(false);
    int T = 1;
    cin >> T;
    while (T--) solve();
    return 0;
}

Floyd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#define N 105

struct Floyd {
    const int INF = 1e9;
    int dp[N][N]{}, n{}, m{};

    void init(int _n, int _m) {
        n = _n, m = _m;
        for (int i = 1; i <= _n; ++i)
            for (int j = 1; j <= _n; ++j)
                if (i ^ j) dp[i][j] = INF;
    }

    void build() {
        for (int i = 1, u, v, w; i <= m; ++i)
            cin >> u >> v >> w, dp[u][v] = dp[v][u] = w;
    }

    void floyd() {
        for (int k = 1; k <= n; ++k)
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= n; ++j)
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
    }
} floyd{};

BIT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
template<class T>
struct BIT {
#define lowbit(x) ((x) & (-x))
	T n {}, m {};
//	int a[N] {}, tr[N] {};
	vector<T> a, tr;

	BIT(T _n): n(_n + 1), a(_n + 1), tr(_n + 1) {};

	void add(int u, int x) {
		for (int i = u; i <= n; i += lowbit(i)) tr[i] += x;
	}

	T query(int u) {
		return u ? query(u - lowbit(u)) + tr[u] : 0;
	}
// 二分找最大的前缀和满足小于等于x
	int findMax(T x) {
		int pos = 0;
		for (int i = 20; i >= 0; --i)
			if (pos + (1ll << i) <= n && tr[pos + (1 << i)] <= x) {
				pos += (1ll << i);
				x -= tr[pos];
			}
		return pos;
	}
};

// 区间修改+单点查询
// 	for (int i = 1, t, pre = 0; i <= n; ++i) cin >> t, bit.add(i, t - pre), pre = t;
// 	for (int i = 1, op, x, y, k; i <= m; ++i) {
// 		cin >> op ;
// 		if (op == 1) {
// 			cin >> x >> y >> k;
// 			bit.add(x, k), bit.add(y + 1, -k);
// 		} else cin >> x, cout << bit.query(x) << endl;
// 	}
// 单点修改+区间查询
// for (int i = 1, t; i <= n; ++i) cin >> t, bit.add(i, t);
// 	for (int i = 1, op, x, y; i <= m; ++i) {
// 		cin >> op >> x >> y;
// 		if (op == 1)bit.add(x, y);
// 		else cout << (bit.query(y) - bit.query(x - 1)) << endl;
// 	}



/*
高维树状数组，用的不多，单点修改+区间查询
int n, m;

LL tr[N][N];
#define lowbit(x) (x & -x)
void add(int x, int y, int d) {
    for (int i = x; i <= n; i += lowbit(i))
        for (int j = y; j <= m; j += lowbit(j))
            tr[i][j] += d;
}
LL query(int x, int y) {
    LL ret = 0;
    for (int i = x; i; i -= lowbit(i))
        for (int j = y; j; j -= lowbit(j))
            ret += tr[i][j];
    return ret;
}

int main() {
    //加快读入
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> m;
    int opt;
    while (cin >> opt) {
        if (opt == 1) {
            int x, y, d;
            cin >> x >> y >> d;
            add(x, y, d);
        } else {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            cout << query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1) << '\n';
        }
    }
    return 0;
}
区间修改加单点查询就是二维差分。

*/

Bellman-Ford

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#define N 100005
#define M 1003

struct SP {
    int n{}, m{}, s{}, t{};
    int dist[N]{}, pre[N]{};
    struct Edge {   // 边，a表示出点，b表示入点，w表示边的权重
        int a{}, b{}, w{};
    } edges[M]{};

    int bellman_ford() {
        memset(dist, 0x3f, sizeof dist);
        dist[s] = 0;

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                int a = edges[j].a, b = edges[j].b, w = edges[j].w;
                if (dist[b] > dist[a] + w) {
                    dist[b] = dist[a] + w;
                    pre[b] = a;
                }
            }
        }

        if (dist[t] > 0x3f3f3f3f / 2) return -1;
        return dist[t];
    }

    void printPath(int last) {
        if (last == s) return cout << s, void();
        printPath(pre[last]);
        cout << last;
    }
} sp{};

Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
struct SP {
	struct Edge {
		int to{};
		int w{};

		Edge(int a, int b) {
			to = a;
			w = b;
		}
	};

	typedef pair<int, int> PII;
	int n{}, s{}, t{};
	vector<vector<Edge>> edge;
	vector<int> dist;
	vector<bool> st;

	SP(int _n, int _s, int _t): n(_n), s(_s), t(_t), edge(_n + 1), dist(_n + 1), st(_n + 1) {};

	int dijkstra() {
		fill(all(dist), 1e9);
		dist[s] = 0;
		priority_queue<PII, vector<PII>, greater<>> heap;
		heap.emplace(0, s);
		while (!heap.empty()) {
			auto ver = heap.top().second;
			heap.pop();
			if (st[ver]) continue;
			st[ver] = true;
			for (auto &i : edge[ver]) {
				int j = i.to;
				if (dist[j] > dist[ver] + i.w) {
					dist[j] = dist[ver] + i.w;
					heap.emplace(dist[j], j);
				}
			}
		}
		return dist[t];
	}
};
//从t点开始遍历，求出s->t的所有最短路径包含的边所构成的DAG
// bitset<N> s;
// vector<int> g[N];
// void build(int u) {
//     if (s[u]) return;
//     for (auto i: sp.edge[u]) {
//         int j = i.to;
//         if (sp.dist[u] == sp.dist[j] + i.w) g[j].push_back(u), s[u] = true, build(j);
//     }
// }

LCA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
struct LCA {
	vector<int> edge[N];
	int n{},  m{}, s{}, fa[N][(int)log2(N) + 2] {}, dist[N] {}, k = (int)log2(N) + 1;

	void dfs(int u, int par) {
		fa[u][0] = par, dist[u] = dist[par] + 1;
		for (int i = 1; i <= log2(dist[u]); ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1];
		for (auto &it : edge[u])
			if (it ^ par) dfs(it, u);
	}

	int lca(int x, int y) {
		if (dist[x] < dist[y])swap(x, y);
		for (int i = k; i >= 0; --i)
			if (dist[x] - (1 << i) >= dist[y])x = fa[x][i];
		if (x == y) return x;
		for (int i = k; i >= 0; --i) {
			if (fa[x][i]^fa[y][i])
				x = fa[x][i], y = fa[y][i];
		}
		return fa[x][0];
	}

	int getDist(int x, int y) {
		return dist[x] + dist[y] - (dist[lca(x, y)] << 1);
	}
};

Tarjan

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//O(n+m)
struct Tarjan {
    vector<int> e[N];
    int n{}, m{}, idx{}, cnt{};
    int dfn[N]{}, low[N]{}, bel[N]{};
    bitset<N> ins{};
    stack<int> stk;
    vector<vector<int>> scc;

    void dfs(int u) {
        dfn[u] = low[u] = ++idx;
        ins[u] = true;
        stk.push(u);
        for (auto v: e[u]) {
//            if (!dfn[v]) {
//                dfs(v);
//                low[u] = min(low[u], low[v]);
//            } else {
//                if (ins[v]) low[u] = min(low[u], dfn[v]);
//            }
            if (!dfn[v]) dfs(v);
            if (ins[v]) low[u] = min(low[u], low[v]);
        }
        if (dfn[u] == low[u]) {
            ++cnt;
            vector<int> c;
            while (true) {
                int v = stk.top();
                c.push_back(v);
                ins[v] = false;
                bel[v] = cnt;
                stk.pop();
                if (v == u) break;
            }
            scc.push_back(c);
        }
    }
};

Tarjan tarjan;

void solve() {
    int n, m;
    cin >> n >> m;
    tarjan.n = n, tarjan.m = m;
    for (int i = 1, u, v; i <= m; ++i) {
        cin >> u >> v;
        tarjan.e[u].push_back(v);
    }
    for (int i = 1; i <= n; ++i)
        if (!tarjan.dfn[i]) tarjan.dfs(i);
    int ans = 0;
    for (auto &it: tarjan.scc)
        ans += it.size() > 1;
    cout << ans << endl;
}

Kosaraju

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
struct Kosaraju {
    vector<int> e[N],erev[N],out,c;
    int n{}, m{};
    bitset<N> vis{};
    stack<int> stk;
    vector<vector<int>> scc;

    void dfs(int u) {
        vis[u] = true;
        for (auto v: e[u])
            if (!vis[v]) dfs(v);
        out.push_back(u);
    }

    void dfs2(int u){
        vis[u] = true;
        for(auto v:erev[u])
            if(!vis[v]) dfs2(v);
        c.push_back(u);
    }

    void kosaraju(){
        for (int i = 1; i <= n; ++i)
            if (!vis[i]) dfs(i);
        reverse(out.begin(),out.end());
        vis.reset();
        for(auto u:out){
            if(!vis[u]){
                c.clear();
                dfs2(u);
                scc.push_back(c);
            }
        }
    }
};

Kosaraju scc;

void solve() {
    int n, m;
    cin >> n >> m;
    scc.n = n, scc.m = m;
    for (int i = 1, u, v; i <= m; ++i) {
        cin >> u >> v;
        scc.e[u].push_back(v),scc.erev[v].push_back(u);
    }
    scc.kosaraju();
    int ans = 0;
    for (auto &it: scc.scc)
        ans += it.size() > 1;
    cout << ans << endl;
}

ST表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>

#define N 100005
using namespace std;

int n, m, a[N], stTable[N][17];

void init() {
    for (int i = 1; i <= n; ++i) stTable[i][0] = a[i];
    int p = (int) (log(n) / log(2));
    for (int i = 1; i <= p; ++i) {
        for (int j = 1; j <= n + 1 - (1 << i); ++j) {
            stTable[j][i] = max(stTable[j][i - 1], stTable[j + (1 << (i - 1))][i - 1]);
        }
    }
}

int query(int l, int r) {
    int len = r - l + 1;
    int p = (int) (log(len) / log(2));
    return max(stTable[l][p], stTable[r - (1 << p) + 1][p]);
}

int main() {
    cin.tie(nullptr), cout.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    init();
    for (int i = 1, l, r; i <= m; ++i) {
        cin >> l >> r;
        cout << query(l, r) << '\n';
    }
    return 0;
}

快速幂

1
2
3
4
5
6
7
8
9
10
11
12
void qpow(long a1, long b1, long p1) {
	long base = a1;
	while (b1) {
		if (b1 & 1)
			ans *= base;
		ans %= p1;
		base *= base;
		base %= p1;
		b1 >>= 1;
	}
	ans %= p1;
}

拓扑排序

基于DFS的拓扑排序
递归有一个特点，就是输出的顺序是倒序，所以如果要正序输出则需要将它先存放进栈里面再输出。并且DFS也可以按照字典序输出所有的拓扑排序。poj 1270，P608

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
struct Topo {
	int n;
	vector<int> d, q;
	vector<vector<int>> edge;
	Topo(int _n): n(_n), d(_n + 1), q(_n), edge(_n + 1) {};
	
	void build(int u,int v){
		edge[u].push_back(v);
		d[v]++;
	}
	
	int toposort()	{
		int hh = 0, tt = 0;
		for (int i = 1; i <= n; i++)
			if (!d[i])
				q[tt++] = i;

		while (hh < tt) {
			int u = q[hh++];
			for (auto v : edge[u])
				if (--d[v] == 0)
					q[tt++] = v;
		}
		return tt;
	}
	
	bool isHavTopo(){
		return toposort() == n;
	}
	
	void printTopoSort(){
		for(auto i : q) cout<<i<<' ';
		cout<<endl;
	}
};

匈牙利算法

模板：P2756 飞行员配对方案问题
建议是直接全写在一个结构体里面，因为二分图往往要建边，边数不对就容易re，结构体可以在初始化的时候就申请所需要的空间并且不会浪费，注意与正常的模板相比初始化要改成-1，因为迭代的时候有时是从下标为0开始的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>

using namespace std;
namespace wr {}
using namespace wr;

struct NTR {
    int n;
    vector<int> vis, st;
    vector<vector<int>> edge;

    NTR(int n, int m) : n(n), vis(m), st(m), edge(n) {};

    void add(int l, int r) { edge[l].push_back(r); }

    bool find(int u) {
        return any_of(edge[u].begin(), edge[u].end(), [&](int v) {
            if (st[v]++ == 0 && (vis[v] == -1 || find(vis[v]))) {
                vis[v] = u;
                return true;
            }
            return false;
        });
    }

    int match() {
        int ans = 0;
        fill(vis.begin(), vis.end(), -1);
        for (int i = 0; i < n; ++i) {
            fill(st.begin(), st.end(), 0);
            ans += find(i);
        }
        return ans;
    }
};

int n, m;

int main() {
    read(n), read(m);
    //申请的时候要注意下标是从0开始还是1开始，如果是1开始那么点数还要加1
    NTR ntr(n + 1, m + 1);
    for (int a, b;;) {
        read(a), read(b);
        if (a == -1 && b == -1)break;
        ntr.add(a, b);
    }
    write(ntr.match(), '\n');
    for (int i = 1; i <= m; ++i)
        if (ntr.vis[i] != -1) write(ntr.vis[i], ' '), write(i, '\n');
    return 0;
}

exgcd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int exgcd(int a, int b, int &x, int &y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	int d = exgcd(b, a % b, y, x);
	y -= (a / b) * x;
	return d;
}
void solve() {
	int a, b, c;
	cin >> a >> b >> c ;
	int x, y;
	int d = exgcd(a, b, x, y);
	if (c % d) return cout << -1 << endl, void();
	a /= d;
	b /= d;
	c /= d;
	int xx = x * (c % b) % b;
	if (xx < 0) xx += b;
	int yy = (c - a * xx) / b;
    // xx yy 是一组特解，其中xx是最小的正数，如果yy不是大于0那么最小非负整数无解
}

欧拉筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
#define N 100000008
#define endl '\n'
using namespace std;

struct EulerSieve{
    bitset<N+5> isprime;
    vector<int> prime;

    void Euler() {
        for (int i = 2; i <= N; i++) {
            if (!isprime[i]) prime.push_back(i);
            for (int j = 0; j < prime.size() && i * prime[j] <= N; ++j) {
                isprime[i * prime[j]] = true;
                if (i % prime[j] == 0) break;
            }
        }
    }
}sieve;

void solve(){
    int n,q,t;
    cin>>n>>q;
    sieve.Euler();
    while(q--){
        cin>>t;
        cout<<sieve.prime[t-1]<<endl;
    }
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T = 1;
//    cin>>T;
    while (T--) solve();
    return 0;
}

素数逆元

模运算下除以一个整数，就相当于乘以这个整数的乘法逆元
因为$ax\equiv 1(mod\ b)$
费马小定理得$ax\equiv a^{b-1}(mod\ b)$
所以$x\equiv a^{b-2}(mod\ b)$

1
2
3
4
5
6
7
8
9
int modularInverse(long long a, int b) {
  int ans = 1;
  a = (a % p + p) % p;
  for (; b; b >>= 1) {
    if (b & 1) ans = (a * ans) % p;
    a = (a * a) % p;
  }
  return ans;
}

其中p必须是质数

欧拉函数/简化剩余系

欧拉函数：把对模m的简化剩余系的元素个数称为m的欧拉函数，记为Φ(m).
容斥原理

1
2
3
4
5
6
7
8
9
10
11
int n;
cin>>n;
int phin = n;
for(int d = 2;d*d<=n;++d)
	if(n%d == 0){
		phin = phin/d*(d-1);
		while(n%d == 0) n/=d;
	}
if(n!=1) phin = phin / n *(n-1);
cout<<phin<<endl;

二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
//返回有序数组（下标从1到n）中小于x的元素的个数
int calc(int x, int num) {
	int l = 0, r = num + 1;
	while (l + 1 < r) {
		int mid = (l + r) >> 1;
		if (a[mid] < x) l = mid;
		else r = mid;
	}
	return l;
}
//这种写法是将l和r考虑为找分界线的作用，在l的右边
//都是不满足条件的，r的左边都是满足条件的。最后的
//情况是分界线卡在l和r的中间，注意l和r的定义，所以
//l和r的初始化必须要这样设置
//lowerbound版
//后继
int bin_search1(int *a, int n, int x) {
	int left = 0, right = n;
	while (left < right) {
		int mid = (left + right) >> 1;//left + ((right - left) >> 1)（1）
		if (a[mid] >= x)
			right = mid;//（2）
		else
			left = mid + 1;//（3）
	}
	return left;//（4）
}
//前驱
int bin_search2(int *a, int n, int x) {
	int left = 0, right = n;
	while (left < right) {
		int mid = (left + right+1) >> 1;//mid = left + ((right - left + 1) >> 1)（1）
		if (a[mid] <= x)
			left = mid;//（2）
		else
			right = mid - 1;//（3）
	}
	return left;//（4）
}
//二分答案
//后继
int bin_search1(int n, int x) {
	int left = 0, right = n;
	while (check1()) {//left<right
		int mid = (left + right) >> 1;//left + ((right - left) >> 1)（1）
		if (check2(mid))
			right = mid;//（2）
		else
			left = mid + 1;//（3）
	}
	return left;//（4）
}
//前驱
int bin_search2(int n, int x) {
	int left = 0, right = n;
	while (check1()) {//left<right
		int mid = left + right+1 >> 1;//mid = left + ((right - left + 1) >> 1)（1）
		if (check2(mid))
			left = mid;//（2）
		else
			right = mid - 1;//（3）
	}
	return left;//（4）
}

最小表示法

一个字符串，这个字符串的首尾是连在一起的，要求寻找一个位置，以该位置为起点的字符串的字典序在所有的字符串中中最小，复杂度为线性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
#define N 300005
using namespace std;

int s[N*2 + 2],n;

int main(){
	read(n);
	for(int i = 1;i<=n;++i)read(s[i]);
	for(int i = 1;i<=n;++i)s[i+n] = s[i];
	int i = 1,j=2;
	while(i<=n&&j<=n){
		int k = 0;
		while(s[i+k] == s[j+k]) ++k;
		if(s[i+k]>s[j+k])i+=k+1;
		else j += k+1;
		if(i==j)++j;
		if(i>j)swap(i,j);
	}
	for(int l = i;l<n+i;++l)write(s[l],' ');
	return 0;
}

O(n)求[1,n]的素数逆元

1
2
3
4
for(int i = 1;i<n;++i){
	if(i==1) inv[i] = 1;
    else inv[i] = (mod - mod/i)*inv[mod%i]%mod;
}

01Trie

https://z01prime.github.io/2024/02/13/01%E5%AD%97%E5%85%B8%E6%A0%91/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#define int long long
#define N 200005
using namespace std;

int n, a[N];
int nxt[N][2],cnt;

void insert(int x){
	int u = 0;
	for(int i = 8;i>=0;--i){
		int y = (x>>i)&1;
		if(nxt[u][y]) u = nxt[u][y];
		else nxt[u][y] = ++cnt,u = nxt[u][y];
	}
}

int find(int x){
	int u = 0,sum = 0;
	for(int i = 8;i>=0;--i){
		int y = (x>>i)&1;
		if(nxt[u][y^1]) sum += (1<<i),u = nxt[u][y^1];
		else u = nxt[u][y];
	}
	return sum;
}

void init(){
	for(int i = 0;i<=cnt;++i) nxt[i][1] = nxt[i][0] = 0;
	cnt = 0;
}

void solve() {
	cin>>n;
	a[0] = 0;
	for(int i = 1;i<=n;++i) cin>>a[i],a[i] ^= a[i-1],insert(a[i]);
	int ans = 0;
	for(int i = 1;i<=n;++i) ans = max({ans,find(a[i]),a[i]});
	cout<<ans<<endl;
}

组合数学相关

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const int mod = 1e9 + 7;

int inv2 = (mod + 1) >> 1, fact[N], invFact[N], inv[N];

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

void init() {
	fact[0] = fact[1] = invFact[0] = invFact[1] = inv[1] = 1;
	for (int i = 2; i < N; ++i) {
		fact[i] = fact[i - 1] * i % mod;
		inv[i] = (mod - mod / i) * inv[mod % i] % mod;
		invFact[i] = invFact[i - 1] * inv[i] % mod;
	}
}

int C(int n, int m) {
	if (n < m || m < 0) return 0;
	return fact[n] * invFact[n - m] % mod * invFact[m] % mod;
}

excrt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
int slow_mul(int x, int y, int mod) {
	int ans = 0;
	while (y > 0) {
		if (y & 1)(ans += x) %= mod;
		(x += x) %= mod;
		y >>= 1;
	}
	return ans;
}

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

void crt(int &a, int &b, int c, int d) {
	if (a == -1 && b == -1) return;
	int x, y;
	int g = exgcd(b, d, x, y);
	(c = c - a % d + d) %= d;
	if (c % g) return a = b = -1, void();
	d /= g;
//	int x0 = (c / g) % d * x % d;
	int x0 = slow_mul((c / g + d) % d, (x + d) % d, d);
	if (x0 < 0) x0 += d;
	a = b * x0 + a;
	b = b * d;
	a = (a % b + b) % b;
}

void solve() {
	int n;
	cin >> n;
	int a = 0, b = 1;
	for (int i = 1, c, d; i <= n; ++i) {
		cin >> d >> c;
		crt(a, b, c, d);
	}
	cout << a << endl;
}

segmentTree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
/*
jiangly
template<class Info> 是 C++ 中的模板声明。它指示编译器该类或函数是一个模板，并且其参数是一个名为 Info 的类型参数。
模板允许您编写通用的类或函数，其行为可以针对不同的类型进行参数化。在这种情况下，
SegmentTree 是一个类模板，Info 是模板的类型参数。
这意味着您可以在实例化 SegmentTree 类时指定不同的类型作为 Info，从而创建不同类型的线段树。

*/
template<class Info>
struct SegmentTree {
	int n;
	std::vector<Info> info;
//	默认构造函数。当您创建一个新的 SegmentTree 对象时，如果没有提供任何参数，就会调用这个默认构造函数。
	SegmentTree() : n(0) {}
//	这是带参数的构造函数。它用于创建一个具有指定大小的线段树对象，并且可以选择性地为每个节点指定初始值。
//	n_ 表示线段树的大小，即包含的元素数量。参数 v_ 是可选的，默认为 Info()，
//	这里的 Info() 是 Info 类的默认构造函数，用于创建一个默认的 Info 对象。
//	比如SegmentTree<Info> s(n);Info是一个结构体或者是int之类的一种数据类型。就会用到这个构造方法
	SegmentTree(int n_, Info v_ = Info()) {
		init(n_, v_);
	}
	template<class T>
	SegmentTree(std::vector<T> init_) {
		init(init_);
	}
	/*
	第一个 init 函数实际上是调用了第二个 init 函数，这是一种比较常见的设计模式，称为函数重载。
	*/
	void init(int n_, Info v_ = Info()) {
		init(std::vector<Info>(n_, v_));
	}
	template<class T>
	void init(std::vector<T> init_) {
		n = init_.size();
//		初始化 info 向量，使其大小为 4 * 2^log₂(n)，并将所有元素的值设置为 Info() 的默认构造值。
		info.assign(4 << std::__lg(n), Info());
//		build函数
		std::function<void(int, int, int)> build = [&](int p, int l, int r) {
			if (r - l == 1) {
				info[p] = init_[l];
				return;
			}
			int m = (l + r) / 2;
			build(2 * p, l, m);
			build(2 * p + 1, m, r);
			pull(p);
		};
		build(1, 0, n);
	}
//	从上往下传递区间值
	void pull(int p) {
		info[p] = info[2 * p] + info[2 * p + 1];
	}
//	区间修改
	void modify(int p, int l, int r, int x, const Info &v) {
		if (r - l == 1) {
			info[p] = v;
			return;
		}
		int m = (l + r) / 2;
		if (x < m) {
			modify(2 * p, l, m, x, v);
		} else {
			modify(2 * p + 1, m, r, x, v);
		}
		pull(p);
	}
	void modify(int p, const Info &v) {
		modify(1, 0, n, p, v);
	}
//	区间查询
	Info rangeQuery(int p, int l, int r, int x, int y) {
		if (l >= y || r <= x) {
			return Info();
		}
		if (l >= x && r <= y) {
			return info[p];
		}
		int m = (l + r) / 2;
		return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
	}
	Info rangeQuery(int l, int r) {
		return rangeQuery(1, 0, n, l, r);
	}
//	这段代码实现了线段树中的范围查询功能，具体来说是实现了查找满足特定条件的第一个元素的位置。
	template<class F>
	int findFirst(int p, int l, int r, int x, int y, F pred) {
		if (l >= y || r <= x || !pred(info[p])) {
			return -1;
		}
		if (r - l == 1) {
			return l;
		}
		int m = (l + r) / 2;
		int res = findFirst(2 * p, l, m, x, y, pred);
		if (res == -1) {
			res = findFirst(2 * p + 1, m, r, x, y, pred);
		}
		return res;
	}
	template<class F>
	int findFirst(int l, int r, F pred) {
		return findFirst(1, 0, n, l, r, pred);
	}
	template<class F>
	int findLast(int p, int l, int r, int x, int y, F pred) {
		if (l >= y || r <= x || !pred(info[p])) {
			return -1;
		}
		if (r - l == 1) {
			return l;
		}
		int m = (l + r) / 2;
		int res = findLast(2 * p + 1, m, r, x, y, pred);
		if (res == -1) {
			res = findLast(2 * p, l, m, x, y, pred);
		}
		return res;
	}
	template<class F>
	int findLast(int l, int r, F pred) {
		return findLast(1, 0, n, l, r, pred);
	}
};

struct Info {
	int max1 = 0;
	int max2 = 0;
	int cnt1 = 0;
	int cnt2 = 0;
};

Info operator+(Info a, Info b) {
//	Info c;
	if (a.max1 == b.max1) {
		if (a.max2 < b.max2) swap(a, b);
//		if(a.max2 == b.max2) c.cnt2 = a.cnt2 + b.cnt2;
		a.cnt1 += b.cnt1;
//		c.cnt1 = a.cnt1 + b.cnt1;
		if (a.max2 == b.max2) a.cnt2 += b.cnt2;
		return a;
	}
	if (a.max1 < b.max1)	swap(a, b);
	if (a.max2 == b.max1) a.cnt2 += b.cnt1;
	else if (a.max2 < b.max1) {
		a.cnt2 = b.cnt1;
		a.max2 = b.max1;
	}
	return a;
}

模2的64次意义下的long long取模

1
2
3
4
5
6
7
8
long long mul(long long x, long long y, long long m) {
	x %= m, y %= m;
	long long d = ((long double)x * y / m);
	d = x * y - d * m;
	if (d >= m) d -= m;
	if (d < 0) d += m;
	return d;
}

整除分块

1
2
3
4
5
6
// 求1-n的所有n/i的值的和，根号复杂度
for (int l = 1; l <= n; ++l) {
    int d = n / l, r = n/d;
    ans += (r-l+1)*d;
    l = r;
}

floordiv/ceildiv

1
2
3
4
5
6
7
8
9
10
11
int floordiv(int a, int b) {
	if (a % b == 0) return a / b;
	else if (a > 0) return a / b;
	else return a / b - 1;
}

int ceildiv(int a, int b) {
	if (a % b == 0) return a / b;
	else if (a > 0) return a / b + 1;
	else return a / b;
}