目录

• 代码模板
• KMP
• Prime
• Random
• ST Table
• INT128
• MINT/Combine
• DSU（不带持久化）

代码模板

#include <bits/stdc++.h>
using namespace std;
#define DEBUG 0

// #define int long long
#define fi first
#define se second
#define pb push_back
#define vt std::vector
#define lb lower_bound
#define eb emplace_back
#define sz(x) (int(x.size()))
#define all(x) x.begin(), x.end()
#define mst(x, bit) memset(x, bit, sizeof(x))
#define rep(i, l, r) for (ll i = (l); i < (r); ++ i)
#define per(i, l, r) for (ll i = (l); i >= (r); -- i)
#define dmp(x) cerr << __LINE__ << "->" << #x << " " << x << "\n"

using db = double;
using ll = long long;
using pdd = pair<db, db>;
using pll = pair<ll, ll>;
using pii = pair<int, int>;

template<typename... Args>
inline void read(Args&... args) { }
template<typename T, typename... Args>
inline void read(T &val, Args&... args) { std::cin >> val; read(args...); }

template<typename... Args>
inline void _wpr_(Args... args) { std::cout << '\n'; }
template<typename T, typename... Args>
inline void _wpr_(T val, Args... args) { std::cout << " " << val; _wpr_(args...); }
template<typename T, typename... Args>
void wpr(T val, Args... args) { std::cout << val; _wpr_(args...); }

const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e5 + 50;

void solve(){

}

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

KMP

#include <bits/stdc++.h>
using namespace std;
#define show(x) for (auto &e: x) cout << e << " "; cout << '\n';

struct KMP{
    vector<int> next; // 失配时，模式串 pattern 跳转的位置
    
    void build(const string &pattern){
        int n = pattern.length();
        next.resize(n + 1); // n + 1 可以保证再完成匹配后继续跳转的方便性（也可以快速获取整个字符串的最大前缀后缀匹配）
        for (int i = 0, j = next[0] = -1; i < n; next[++i] = ++j){ // next[i + 1] = j + 1 往后推一位
            while (~j && pattern[i] != pattern[j]) j = next[j];
        }
    }
    
    vector<int> match(const string &pattern, const string &text){
        build(pattern); // 预处理 next 数组
        vector<int> res; // 代表文本串中所有匹配位置的开始 
        int n = pattern.length(), m = text.length();
        for (int i = 0, j = 0; i < m; ++ i){
            while (j > 0 && pattern[j] != text[i]) j = next[j]; // 当 j != 0 时用next数组不断尝试匹配
            if (pattern[j] == text[i]) ++ j;
            if (j == n) res.emplace_back(i - n + 1), j = next[j]; // 匹配成功，假如首位置，利用next多处理出的一位进行转移
        }
        return res;
    }
};


int main(){

    string ss = "ABABAB";
    KMP kmp;
    kmp.build(ss);
    show(kmp.next)

    return 0;
}

Prime

#include <bits/stdc++.h>
using namespace std;

namespace Prime{
    const int Prime_max = 1e6 + 50;

    int ptot; // tot prime 
    int prime[Prime_max / 10];
    int is_prime[Prime_max + 1];

    void getPrime(){
        ptot = 0;
        memset(is_prime, 0, sizeof(is_prime));
        for (int i = 2; i <= Prime_max; ++ i){
            if (!is_prime[i]) prime[ptot++] = i;
            for (int j = 0; j < ptot && prime[j] <= Prime_max / i; ++ j){
                is_prime[i * prime[j]] = 1;
                if (i % prime[j] == 0) break; // i = k*prime[j], so i * prime[j+1] = (k*prime[j+1]) * prime[j]
            }
        }
    }

    vector<pair<int, int>> Factor(long long num){
        vector<pair<int, int>> ret;
        for (int i = 0; prime[i] <= num / prime[i]; ++ i){
            pair<int, int> cur = {0, 0};
            if (num % prime[i] == 0) {
                cur.first = prime[i];
                while (num % prime[i] == 0) ++ cur.second, num /= prime[i];
                ret.push_back(cur);
            }
        }
        if (num != 1) ret.push_back(make_pair(num, 1));
        return ret;
    }


    void disp(vector<pair<int, int>> ftr){
        std::cout << "      show factor    \n";
        for (auto x: ftr)
            std::cout << "Prime: " << setw(5) << x.first << " cnt: " << setw(5) << x.second << "\n";
        std::cout << "---------------------\n";
    }
}

signed main(){
    using namespace Prime;
    getPrime();
    auto res = Factor(210);
    disp(res);
    return 0;
}

Random

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#include <random>
#include <chrono>
// 获取a,b之间均匀分布的整数
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
// 茅台19937 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ST Table

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 50;
const int logn = 21;

int n; // 长度
int st[maxn][logn]; // st(i, j) -> [i, i + 2^j - 1]
int Logn[maxn], arr[maxn];

inline void pre(){
    Logn[1] = 0;
    Logn[2] = 1;
    for (int i = 3; i < maxn; ++ i) Logn[i] = Logn[i / 2] + 1;
}

void init(){
    for (int i = 0; i < n; ++ i) st[i][0] = arr[i];

    for (int j = 1; (1 << j) <= n; ++ j){
        for (int i = 0; i + (1 << j) - 1 < n; ++ i){
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int query(int l, int r){
    int s = Logn[r - l + 1];
    return max(st[l][s], st[r - (1 << s) + 1][s]);
}

INT128

#include <bits/stdc++.h>
using namespace std;


namespace I128{
#ifndef lll
    #define lll __int128
#endif
    lll read(){
        lll x = 0, f = 1;
        char ch = getchar();
        while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
        while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
        return x * f;
    }
    void print(lll x){
        if (x < 0) { putchar('-'); x = -x; }
        if (x > 9) print(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace I128;

void solve(){
    lll a = read();
    print(a);
}

int main(){
    // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    while (t--) solve();
    return 0;
}

MINT/Combine

#include <bits/stdc++.h>
using namespace std;

template<int m>
struct modint{
	unsigned int x;
	constexpr modint()noexcept:x(){}
	template<typename T>
	constexpr modint(T x_)noexcept:x((x_%=m)<0?x_+m:x_){}
	constexpr unsigned int val()const noexcept{return x;}
	constexpr modint&operator++()noexcept{if(++x==m)x=0;return*this;}
	constexpr modint&operator--()noexcept{if(x==0)x=m;--x;return*this;}
	constexpr modint operator++(int)noexcept{modint res=*this;++*this;return res;}
	constexpr modint operator--(int)noexcept{modint res=*this;--*this;return res;}
	constexpr modint&operator+=(const modint&a)noexcept{x+=a.x;if(x>=m)x-=m;return*this;}
	constexpr modint&operator-=(const modint&a)noexcept{if(x<a.x)x+=m;x-=a.x;return*this;}
	constexpr modint&operator*=(const modint&a)noexcept{x=(unsigned long long)x*a.x%m;return*this;}
	constexpr modint&operator/=(const modint&a)noexcept{return*this*=a.inv();}
	constexpr modint operator+()const noexcept{return*this;}
	constexpr modint operator-()const noexcept{return modint()-*this;}
	constexpr modint pow(long long n)const noexcept
	{
		if(n<0)return pow(-n).inv();
		modint x=*this,r=1;
		for(;n;x*=x,n>>=1)if(n&1)r*=x;
		return r;
	}
	constexpr modint inv()const noexcept
	{
		int s=x,t=m,x=1,u=0;
		while(t)
		{
			int k=s/t;
			s-=k*t;
			swap(s,t);
			x-=k*u;
			swap(x,u);
		}
		return modint(x);
	}
	friend constexpr modint operator+(const modint&a,const modint&b){return modint(a)+=b;}
	friend constexpr modint operator-(const modint&a,const modint&b){return modint(a)-=b;}
	friend constexpr modint operator*(const modint&a,const modint&b){return modint(a)*=b;}
	friend constexpr modint operator/(const modint&a,const modint&b){return modint(a)/=b;}
	friend constexpr bool operator==(const modint&a,const modint&b){return a.x==b.x;}
	friend constexpr bool operator!=(const modint&a,const modint&b){return a.x!=b.x;}
	friend ostream&operator<<(ostream&os,const modint&a){return os<<a.x;}
	friend istream&operator>>(istream&is,modint&a){long long v;is>>v;a=modint(v);return is;}
};

using mint = modint<998244353>;

namespace Combine{
	const int Combine_max = 1e5 + 50;
	mint fac[Combine_max];
	void init() { fac[0] = 1; for (int i = 1; i < Combine_max; ++ i) fac[i] = fac[i - 1] * i; }
	mint A(int n, int m) { return fac[n] / fac[n - m]; }
	mint C(int n, int m) { return fac[n] / (fac[n - m] * fac[m]); }
	mint fpow(mint x, int exp){
		mint res = 1;
		for (; exp; x *= x, exp >>= 1) if (exp & 1) res *= x;
		return res;
	}
}

signed main(){
    mint a = 1000000000;
    std::cout << a << "\n";
	using namespace Combine;
	init();
	std::cout << C(5, 3) << "\n";
    return 0;
}

DSU（不带持久化）

#include <bits/stdc++.h>
using namespace std;


struct DSU{
    vector<int> parent;
    void init(int k){
        // 0 or 1-index ?
        parent.resize(k + 1);
        for (int i = 0; i <= k; ++ i) parent[i] = i;
    }
    int find(int x){
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    void to_union(int x, int y){
        parent[find(x)] = find(y);
    }
    bool is_same(int x, int y){
        return find(x) == find(y);
    }
};

// 按秩合并的 不一定需要
struct DSU{
    vector<int> parent, rank;
    void init(int K){
        parent.resize(K), rank.resize(K);
        for (int i = 0; i <= K; ++ i) parent[i] = i, rank[i] = 0;
    }
    int find(int x){
        return (x == parent[x]) ? x : parent[x] = find(parent[x]);
    }
    void to_union(int to, int from){
        int rto = find(to);
        int rfrom = find(from);
        if (rto == rfrom) return;
        if (rank[rto] > rank[rfrom]) parent[rfrom] = rto;
        else {
            parent[rto] = rfrom;
            if (rank[rto] == rank[rfrom]) ++ rank[rfrom];
        }
    }
    bool is_same(int x, int y) {
        return find(x) == find(y);
    }
};