写在前面

总结一下板子；顺序没有意义；尽量不会压行（但有时候略微压）；限于本人水平，有概率会错；有些东西的运用要视情况而定，会给出类似伪代码的东西，还有些之间用文字给出流程

关于编译选项，默认是 -O2 -std=c++14 -Wl,--stack=1145141919

关于头文件，默认是万能头 #include <bits/stdc++.h>

关于宏（包括 using ），默认包含以下宏

#define pb push_back
#define fi first
#define se second
#define STC static
using LL = long long;
using DB = double;
using LDB = long double;
template<class T1, class T2>
using PR = std::pair<T1, T2>;
using PII = std::pair<int, int>;
template<class T, std::size_t num>
using AR = std::array<T, num>;

大部分情况默认数据范围是 int

大部分情况默认 $P$ 为模数， $I N F$ 为正无穷

如未特殊说明，那些写在外面的语句就是主函数里的

由于这些板子学习的时间参差不齐，码风可能会有不同，见谅

数据结构

邻接表

struct Edge{ int ne, ver, w; } e[M];
int h[N], idx;
void init(int n){ memset(h, -1, (n + 1) * sizeof(int)), idx = 0; }
void add(int x, int y, int z){ e[idx] = {h[x], y, z}, h[x] = idx++; }

使用前要初始化（如何使用： for (int i = h[x]; ~i; i = e[i].ne) ）

并查集

int get(int x){ return x == fa[x] ? x : fa[x] = get(fa[x]); } //路径压缩
void merge(int x, int y)
{
    x = get(x), y = get(y);
    if (x == y) return ;
    if (rk[x] > rk[y]) std::swap(x, y);
    fa[x] = y, rk[y] += rk[x] == rk[y]; //按秩合并
}

堆

STL （大根堆）： std::priority_queue<int> q;

手打（小根堆）：

namespace Hp //Heap
{
	int hp[N], tot;
	void up(int x){ for (; x > 1 && hp[x] < hp[x >> 1]; x >>= 1) std::swap(hp[x], hp[x >> 1]); }
	void dw(int x)
	{
		for (int y = x << 1; y <= tot; y = x << 1)
		{
			if (y < tot && hp[y + 1] < hp[y]) ++y;
			if (hp[y] < hp[x])
			{
				std::swap(hp[y], hp[x]);
				x = y;
			}
			else break;
		}
	}
	void ins(int x){ hp[++tot] = x, up(tot); }
	void del(int x = 1){ hp[x] = hp[tot--], up(x), dw(x); }
}

左偏树（小根堆）：

namespace LH //Left Heap
{
	int fa[N], tot; //并查集维护根
	struct Node{ int lc, rc, v, dis; } lh[N];
	#define lc lh[x].lc
	#define rc lh[x].rc
	#define v(x) lh[(x)].v
	#define ds(x) lh[(x)].dis
	void ins(int x) //新建一个只有值x的堆
	{
		lh[++tot] = {0, 0, x, 0};
		fa[tot] = tot;
	}
	int _merge(int x, int y)
	{
		if (!x || !y) return x + y;
		if (v(x) > v(y)) std::swap(x, y);
		rc = _merge(rc, y);
		if (ds(rc) > ds(lc)) std::swap(rc, lc);
		ds(x) = ds(rc) + 1;
		return x;
	}
	int get(int x){ return x == fa[x] ? x : fa[x] = get(fa[x]); }
	int merge(int x, int y)
	{
		if (v(x) == -1 || v(y) == -1) return -1;
		x = get(x), y = get(y);
		if (x != y) return fa[x] = fa[y] = _merge(x, y);
		return -1;
	}
	void del(int x){ v(x) = -1, fa[lc] = lc, fa[rc] = rc, fa[x] = merge(lc, rc); }
	int top(int x){ return v(x) == -1 ? -1 : v(get(x)); }
	#undef lc
	#undef rc
	#undef v
	#undef ds
}

树状树组

namespace BIT
{
	#define lb(x) ((x) & (-(x)))
	int c[N];
	void add(int x, int d){ for (; x <= n; x += lb(x)) c[x] += d; }
	int ask(int x)
	{
		int res = 0;
		for (; x; x ^= lb(x)) res += c[x];
		return res;
	}
	#undef lb
}

注意下标必须从 $1$ 开始，否则会死循环

ST 表

namespace ST
{
	int mx[N][D], lg2[N];
	void prev(int x[])
	{
		for (int i = 1; i <= n; ++i) mx[i][0] = x[i];
		lg2[1] = 0;
		for (int i = 2; i <= n; ++i) lg2[i] = lg2[i >> 1] + 1;
		int t = lg2[n] + 1;
		for (int j = 1; j < t; ++j)
			for (int i = 1; i <= n - (1 << j) + 1; ++i) mx[i][j] = std::max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
	}
	int ask(int l, int r)
	{
		int t = lg2[r - l + 1];
		return std::max(mx[l][t], mx[r - (1 << t) + 1][t]);
	}
}

四毛子

namespace FR //Four Russians
{
    const int L = N << 1;
    struct Tree{ int lc, rc, dat; } tr[N];
    struct Block{ int l, r, tp; } b[N];
    int dfn[N], bid[L], cnt = 0, rt, num = 0, B, bk[L];
    PII dat[L];
    template<class T>
    bool cmn(T &x, T y){ return y < x ? x = y, true : false; }
    namespace ST
    {
        const int D = 18;
        int lg2[L];
        PII mn[L][D];
        void init()
        {
            lg2[1] = 0;
            for (int i = 2; i <= num; ++i) lg2[i] = lg2[i >> 1] + 1;
            for (int i = 1; i <= num; ++i) mn[i][0] = dat[b[i].l + bk[b[i].tp] - 1];
            for (int j = 1, t = lg2[num]; j <= t; ++j)
                for (int i = 1; i <= num - (1 << j) + 1; ++i) mn[i][j] = std::min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
        }
        PII ask(int l, int r)
        {
            if (l > r) return {INF, INF};
            int t = lg2[r - l + 1];
            return std::min(mn[l][t], mn[r - (1 << t) + 1][t]);
        }
    }
    void init(int len, int x[])
    {
        FF<void(int, int[])> bct = [&](int len, int x[])
        {
            STC int stk[N];
            int top = 0;
            for (int i = 1; i <= len; ++i) tr[i].dat = x[i];
            for (int i = 1, k; i <= len; ++i)
            {
                for (k = top; k && tr[stk[k]].dat < tr[i].dat; --k);
                if (k) tr[stk[k]].rc = i;
                if (k < top) tr[i].lc = stk[k + 1];
                stk[top = k + 1] = i;
            }
            rt = stk[1];
        } ; 
        bct(len, x);
        FF<void(int, int)> dfs = [&](int x, int dep)
        {
            dfn[x] = ++cnt, dat[cnt] = {dep, x};
            if (tr[x].lc) dfs(tr[x].lc, dep + 1), dat[++cnt] = {dep, x};
            if (tr[x].rc) dfs(tr[x].rc, dep + 1), dat[++cnt] = {dep, x};
        } ;
        dfs(rt, 1);
        B = log2(cnt) / 2 + 1;
        for (int i = 1; i <= cnt; i += B) b[++num].l = i, b[num].r = i + B - 1;
        for (int i = cnt + 1; i <= b[num].r; ++i) dat[i] = {INF, INF};
        for (int i = 1; i <= num; ++i)
            for (int j = b[i].l; j <= b[i].r; ++j) bid[j] = i;
        FF<void(int)> calc = [&](int x)
        {
            bk[x] = 1;
            for (int i = 2, mn = 0, sum = 0; i <= B; ++i)
            {
                if ((x >> (i - 1)) & 1) ++sum;
                else --sum;
                if (cmn(mn, sum)) bk[x] = i; 
            }
        } ;
        FF<int(Block)> get_tp = [&](Block x)
        {
            int res = 0;
            for (int i = x.l + 1; i <= x.r; ++i) res |= (dat[i].fi - dat[i - 1].fi >= 0 ? 1 : 0) << (i - x.l);
            return res;
        } ; 
        for (int i = (1 << B) - 1; ~i; --i) calc(i);
        for (int i = 1; i <= num; ++i) b[i].tp = get_tp(b[i]);
        ST::init();
    }
    PII to_ask(int l, int r)
    {
        if (l > r) return to_ask(r, l);
        FF<PII(int, int)> bask = [&](int l, int r)
        {
            Block &x = b[bid[l]];
            int t = x.tp, ll = l - x.l + 1, rr = r - x.l + 1;
            t >>= ll - 1;
            t |= ((1 << (rr - ll + 1)) - 1) ^ ((1 << B) - 1);
            return dat[l + bk[t] - 1];
        } ;
        if (bid[l] == bid[r]) return bask(l, r); 
        PII res = std::min(bask(l, b[bid[l]].r), bask(b[bid[r]].l, r));
        if (bid[r] - bid[l] > 1) cmn(res, ST::ask(bid[l] + 1, bid[r] - 1));
        return res;
    }
    int ask(int l, int r){ return tr[to_ask(dfn[l], dfn[r]).se].dat; }
}

线段树

namespace LT
{
	struct Node{ ... } tr[N << 2];
	#define lc (u << 1)
	#define rc ((u << 1) | 1)
	#define mid ((l + r) >> 1)
	...
	void up(int u){ ... }
	void adt(int u, int d){ ... }
	void dw(int u)
	{
		if (tg(u))
		{
			adt(lc, tg(u)), adt(rc, tg(u));
			tg(u) = 0;
		}
	}
	void bd(int u = 1, int l = 1, int r = n)
	{
		tr[u] = {0, ...};
		if (l == r) return ;
		bd(lc, l, mid), bd(rc, mid + 1, r);
		up(u); //有时候可以不要
	}
	void cg(int pos, int d, int u = 1, int l = 1, int r = n)
	{
		if (l == r) return adt(u, d);
		dw(u);
		pos <= mid ? cg(pos, d, lc, l, mid) : cg(pos, d, rc, mid + 1, r);
		up(u);
	}
	void mdf(int ql, int qr, int d, int u = 1, int l = 1, int r = n)
	{
		if (l >= ql && r <= qr) adt(u, d);
		dw(u);
		if (ql <= mid) mdf(ql, qr, d, lc, l, mid);
		if (qr > mid) mdf(ql, qr, d, rc, mid + 1, r);
		up(u);
	}
	int ask(int pos, int u = 1, int l = 1, int r = n)
	{
		if (l == r) return ...;
		dw(u);
		return pos <= mid ? ask(pos, lc, l, mid) : ask(pos, rc, mid + 1, r);
	}
	int qry(int ql, int qr, int u = 1, int l = 1, int r = n)
	{
		if (l >= ql && r <= qr) return ...;
		dw(u);
		int res = 0;
		if (ql <= mid) res ? qry(ql, qr, lc, l, mid); //?表示某种运算
		if (qr > mid) res ? qry(ql, qr, rc, mid + 1, r);
		return res;
	}
	#undef lc
	#undef rc
	#undef mid
	...
}

注意空间开 $4$ 倍

莫队

读入
将询问按照(l所在块号，r)双关键字排序
依次处理每一个询问:
	移动指针
    维护答案
输出

莫队二次离线

namespace TOF //Twice Offline
{
    const int B = 320;
    struct Tag{ int l, r, id, pos; } tg1[N], tg2[N]; //用vector可以不必排序,但慢一些,且有时候不好优化
    int tp1 = 0, tp2 = 0;
	int bid[N], f[2][N]; //f[0/1][i]:f(i,[1,i-1/i+1])
    void prev() //处理块号并排序询问
    {
        for (int i = 1; i <= n; ++i) bid[i] = (i - 1) / B + 1;
        std::sort(q + 1, q + m + 1, [&](Q x, Q y){ return bid[x.l] == bid[y.l] ? x.r < y.r : x.l < y.l; });
    }
    void add_tag() //打上离线标记
    {
        for (int i = 1, il = q[1].r + 1, ir = q[1].r; i <= m; ++i)
        {
            if (il > q[i].l) tg1[++tp1] = {q[i].l, il - 1, -i, ir};
            else  if (il < q[i].l) tg1[++tp1] = {il, q[i].l - 1, i, ir}; 
            il = q[i].l; //一定要记得移动指针
            if (ir < q[i].r) tg2[++tp2] = {ir + 1, q[i].r, -i, il - 1};
            else if (ir > q[i].r) tg2[++tp2] = {q[i].r + 1, ir, i, il - 1};
            ir = q[i].r;
        }
        std::sort(tg1 + 1, tg1 + tp1 + 1, [&](Tag x, Tag y){ return x.pos < y.pos; }); //标记排序
        std::sort(tg2 + 1, tg2 + tp2 + 1, [&](Tag x, Tag y){ return x.pos < y.pos; });
    }
    void offline()
    {
        int p = 0;
        for (int i = 1; i <= tp2; ++i)
        {
            while (p < tg2[i].pos && ++p)
            {
				计算f[0][p]
				完成a[p]的修改
            }
            for (int l = tg2[i].l, r = tg2[i].r, k = (tg2[i].id < 0 ? -1 : 1), id = tg2[i].id * k; l <= r; ++l) q[id].ans += (计算贡献) * k;
        }
        while (p < n && ++p)
        {
            计算f[0][p]
			完成a[p]的修改
        }
        p = 0;
        for (int i = 1; i <= tp1; ++i)
        {
            while (p < tg1[i].pos && ++p)
            {
				完成a[p]的修改
                计算f[1][p]
            }
            for (int l = tg1[i].l, r = tg1[i].r, k = (tg1[i].id < 0 ? -1 : 1), id = tg1[i].id * k; l <= r; ++l) q[id].ans += (计算贡献) * k;
        }
        while (p < n && ++p)
        {
            完成a[p]的修改
            计算f[1][p]
        }
    }
    void modui()
    {
        for (int i = 1, il = q[1].r + 1, ir = q[1].r; i <= m; ++i)
        {
            if (il != q[i].l) q[i].ans += f[1][il - 1] - f[1][q[i].l - 1];
            il = q[i].l;
            if (ir != q[i].r) q[i].ans += f[0][q[i].r] - f[0][ir];
            ir = q[i].r;
        }
        for (int i = 2; i <= n; ++i) q[i].ans += q[i - 1].ans; //前缀和后才是答案
        for (int i = 1; i <= m; ++i) ans[q[i].id] = q[i].ans;
    }
    void work(){ prev(), add_tag(), offline(), modui(); }
}

分块

额……，略

点分治

int get_si(int x, int fa)
{
	if (del[x]) return 0;
	int res = 1;
	for (int i = h[x]; ~i; i = e[i].ne) if (e[i].ver != fa) res += get_si(e[i].ver, x);
	return res;
}
int get_wc(int x, int fa, int si, int &wc) //求重心(其实是一个保证删去后子树大小小于n/2的点,不一定是重心)
{
	if (del[x]) return 0;
	int sum = 1, mx = 0;
	for (int i = h[x], y, t; ~i; i = e[i].ne) if ((y = e[i].ver) != fa)
	{
		t = get_wc(y, x, si, wc);
		mx = max(mx, t);
		sum += t;
	}
	mx = max(mx, si - sum);
	if (LL(mx << 1) <= si) wc = x;
	return sum;
}
int calc(int x) //cp,cq是p[],q[]的计数器
{
	if (del[x]) return 0;
	int res = 0;
	get_wc(x, -1, get_si(x, -1), x);
	del[x] = true;
	cp = 0;
	for (int i = h[x], y; ~i; i = e[i].ne)
	{
		y = e[i].ver;
		cq = 0;
		得到y子树的,记录在q[]中
		for (int j = 1; j <= cq; ++j)
		{
			利用q[j]计算答案
			将q[j]的信息记录在p[]中
		}
		可能需要修正一些偏差量(比如多算的减掉)
	}
	用p[]还原q[]计算时的修改
	for (int i = h[x]; ~i; i = e[i].ne) res += calc(e[i].ver);
	return res;
}

边分治

注意点数要开 $2$ 倍，边数开 $4$ 倍

int si[N << 1], mxs, rte;
bool del[N << 2];
void dfs(int x, int fa)
{
    for (int i = h[x]; ~i; i = e[i].ne) if (e[i].ver != fa)
    {
        dfs(e[i].ver, x);
        G[x].pb({e[i].ver, e[i].w});
    }
}
void rebuild()
{
    dfs(1, -1);
    std::memset(h, -1, sizeof h), idx = 0;
    for (int i = 1, lc, rc; i <= n; ++i)
        if (G[i].size() <= 2)
            for (auto t : G[i]) add(i, t.fi, t.se), add(t.fi, i, t.se);
        else
        {
            lc = ++n, rc = ++n;
            add(i, lc, 0), add(lc, i, 0);
            add(i, rc, 0), add(rc, i, 0);
            for (auto t : G[i]) G[lc].pb(t), std::swap(lc, rc);
        }
}
void get_rt(int x, int fa, int tot)
{
    si[x] = 1;
    for (int i = h[x], y, mx; ~i; i = e[i].ne) if (!del[i] && (y = e[i].ver) != fa)
    {
        get_rt(y, x, tot);
        si[x] += si[y], mx = std::max(si[y], tot - si[y]);
        if (mx < mxs) mxs = mx, rte = i;
    }
}
void calc(int x, int tot)
{
    mxs = n, rte = -1;
    get_rt(x, -1, tot);
    if (rte ==-1 || del[rte]) return ;
    x = rte; //注意,这里x由点变成边
    del[x] = del[x ^ 1] = true;
    int lc = e[x].ver, rc = e[x ^ 1].ver; //把lc作为基准
   	得到lc,rc的子树信息(以lc为基准)
    统计答案
   	这里可能需要还原某些信息
    注意,要重新统计一遍si(以lc/rc为根),这可以在得到子树信息时一起做
    calc(lc, si[lc]), calc(rc, si[rc]);
}

平衡树

STL1 ： std::set<int> s;

STL2 ：

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
tree<LL, null_type, less<LL>, rb_tree_tag,tree_order_statistics_node_update> tr;
函数为:
tr.insert(val);
tr.erase(tr.lower_bound(val));
tr.order_of_key(val);
tr.find_by_order(rank);
tr.lower_bound(val)
tr.upper_bound(val)
...

Splay ：

namespace Splay
{
	int rt, tot;
	struct Node{ int ch[2], fa, val, size, tag, cnt; } tr[N];
	#define ch(x, y) tr[(x)].ch[(y)]
	#define fa(x) tr[(x)].fa
	#define v(x) tr[(x)].val
	#define si(x) tr[(x)].size
	#define tg(x) tr[(x)].tag
	#define c(x) tr[(x)].cnt
	void up(int x){ si(x) = si(ch(x, 0)) + si(ch(x, 1)) + c(x); }
	void dw(int x) //文艺平衡树的交换
	{
		if (tg(x))
		{
			tg(ch(x, 0)) ^= 1, tg(ch(x, 1)) ^= 1;
			tg(x) = 0;
			std::swap(ch(x, 0), ch(x, 1));
		}
	}
	void rot(int x)
	{
		int y = fa(x), z = fa(y);
		int k = ch(y, 1) == x;
		ch(z, ch(z, 1) == y) = x, fa(x) = z;
		ch(y, k) = ch(x, k ^ 1), fa(ch(x, k ^ 1)) = y;
		ch(x, k ^ 1) = y, fa(y) = x;
		up(y), up(x);
	}
	void splay(int x, int f)
	{
		while (fa(x) != f)
		{
			int y = fa(x), z = fa(y);
			if (z != f) (ch(y, 1) == x) ^ (ch(z, 1) == y) ? rot(x) : rot(y);
			rot(x);
		}
		if (!f) rt = x;
	}
	void find(int x)
	{
		int u = rt;
		if (!u) return ;
		while (x != v(u) && ch(u, x > v(u)) ) u = ch(u, x > v(u));
		splay(u, 0);
	}
	int near(int x, int dir) //查询前驱(0)后继(1)
	{
		find(x);
		int u = rt;
		if ((v(u) > x && dir) || (v(u) < x && !dir)) return u;
		u = ch(u, dir);
		while (ch(u, dir ^ 1)) u = ch(u, dir ^ 1);
		return u;
	}
	void del(int x)
	{
		int last = near(x, 0), next = near(x, 1);
		splay(last, 0), splay(next, last);
		int t = ch(next, 0);
		if (c(t) > 1) --c(t), splay(t, 0);
		else ch(next, 0) = 0;
	}
	void ins(int x)
	{
		int u = rt, f = 0;
		while (u && v(u) != x) f = u, u = ch(u, x > v(u));
		if (u) ++c(u);
		else
		{
			u = ++tot;
			if (f) ch(f, x > v(f)) = u;
			tr[u] = {{0, 0}, f, x, 1, 0, 1};
		}
		splay(u, 0);
	}
	int get_k(int k) //查询排名为k的数
	{
		int u = rt;
		if (si(u) < k) return -1;
		while (true)
		{
			dw(u);
			int y = ch(u, 0);
			if (k > si(y) + c(u)) k -= si(y) + c(u), u = ch(u, 1);
			else if (si(y) >= k) u = y;
			else return v(u);
		}
		return -1;
	}
	#undef ch
	#undef fa
	#undef v
	#undef si
	#undef tg
	#undef c
}

优点是可拓展性强，缺点是慢（被卡的化可以试试多转几下）

FHQ Treap ：

namespace FHQ
{
    struct Node{ int priority, size, val, left_child, right_child; } tr[N];
    #define p(x) tr[(x)].priority
    #define si(x) tr[(x)].size
    #define v(x) tr[(x)].val
    #define lc(x) tr[(x)].left_child
    #define rc(x) tr[(x)].right_child
    int rub[N], top = 0, num = 0, rt;
    std::mt19937 rud(114514);
    void up(int x){ si(x) = si(lc(x)) + si(rc(x)) + 1; }
    int newnd(int val)
    {
        int res = (top ? rub[top--] : ++num);
        tr[res] = {(int)rud(), 1, val, 0, 0};
        return res;
    }
    int merge(int x, int y) //合并以x,y为根的树,返回合并后的根(要保证x的val都小于y)
    {
        if (!x || !y) return x + y;
        if (p(x) > p(y))
        {
            rc(x) = merge(rc(x), y);
            return up(x), x;
        }
        lc(y) = merge(x, lc(y));
        return up(y), y;
    }
    void split(int u, int val, int &x, int &y) //把以u为根的树分裂为x,y
    {
        if (!u) return void(x = y = 0);
        if (v(u) <= val) split(rc(x = u), val, rc(u), y);
        else split(lc(y = u), val, x, lc(u));
        up(u);
    }
    void ins(int val)
    {
        int tx, ty;
        split(rt, val, tx, ty), rt = merge(merge(tx, newnd(val)), ty);
    }
    void del(int val)
    {
        int tx, ty, tz;
        split(rt, val, tx, ty);
        split(tx, val - 1, tx, tz);
        rub[++top] = tz;
        tz = merge(lc(tz), rc(tz));
        rt = merge(merge(tx, tz), ty);
    }
    int rank(int val)
    {
        int tx, ty, res;
        split(rt, val - 1, tx, ty);
        res = si(tx) + 1;
        rt = merge(tx, ty);
        return res;
    }
    int getk(int u, int k)
    {
        for (int t; u; )
            if ((t = si(lc(u)) + 1) == k) break;
            else if (t > k) u = lc(u);
            else k -= t, u = rc(u);
        return v(u); //可视题目改
    }
    int getk(int k){ return getk(rt, k); }
    int pre(int val)
    {
        int tx, ty, res;
        split(rt, val - 1, tx, ty);
        res = getk(tx, si(tx));
        rt = merge(tx, ty);
        return res;
    }
    int suc(int val)
    {
        int tx, ty, res;
        split(rt, val, tx, ty);
        res = getk(ty, 1);
        rt = merge(tx, ty);
        return res;
    }
    #undef p
    #undef si
    #undef v
    #undef lc
    #undef rc
}

补充一个按大小分裂（但是指针码风）

void split(Node *u, int si, Node *&x, Node *&y)
{
    if (u == null) return void(x = y = null);
    if (u->lc->si < si) x = u, split(u->rc, si - u->lc->si - 1, u->rc, y);
    else y = u, split(u->lc, si, x, u->lc);
    up(u);
}

优点是好打且较快

SBT ：

namespace SBT
{
	struct SBT{ int size, lc, rc, val; } tr[N];
	#define si(x) tr[(x)].size
	#define rc(x) tr[(x)].rc
	#define lc(x) tr[(x)].lc
	#define v(x) tr[(x)].val
	int rt, tot;
	void r_r(int &t)
	{
		int k = lc(t);
		lc(t) = rc(k), rc(k) = t;
		si(k) = si(t), si(t) = si(rc(t)) + si(lc(t)) + 1;
		t = k;
	}
	void l_r(int &t)
	{
		int k = rc(t);
		rc(t) = lc(k), lc(k) = t;
		si(k) = si(t), si(t) = si(rc(t)) + si(lc(t)) + 1;
		t = k;
	}
	void mt(int &t, bool f) //maintain
	{
		if (!f)
		{
			if (si(lc(lc(t))) > si(rc(t))) r_r(t);
			else if (si(rc(lc(t))) > si(rc(t))) l_r(lc(t)), r_r(t);
			else return ;
		}
		else
		{
			if (si(rc(rc(t))) > si(lc(t))) l_r(t);
			else if (si(lc(rc(t))) > si(lc(t))) r_r(rc(t)), l_r(t);
			else return ;
		}
		mt(lc(t), false), mt(rc(t), true);
		mt(t, false), mt(t, true);
	}
	void ins(int &t, int x)
	{
		if (!t) return void(tr[t = ++tot] = {1, 0, 0, x});
		++si(t);
		x <= v(t) ? ins(lc(t), x) : ins(rc(t), x);
		mt(t, x > v(t));
	}
	int del(int &t, int x)
	{
		--si(t);
		if ((v(t) == x) || (v(t) > x && !lc(t)) || (v(t) < x && !rc(t)))
		{
			int res = v(t);
			if (!lc(t) || !rc(t)) t = lc(t) + rc(t);
			else v(t) = del(lc(t), v(t) + 1);
			return res;
		}
		return v(t) > x ? del(lc(t), x) : del(rc(t), x);
	}
	int rk(int &t, int x)
	{
		if (!t) return 1;
		return v(t) >= x ? rk(lc(t), x) : si(lc(t)) + 1 + rk(rc(t), x);
	}
	int get_k(int &t, int x)
	{
		if (x == si(lc(t)) + 1) return v(t);
		return x <= si(lc(t)) ? get_k(lc(t), x) : get_k(rc(t), x - 1 - si(lc(t)));
	}
	int pred(int &t, int x)
	{
		if (!t) return x;
		if (x <= v(t)) return pred(lc(t), x);
		int res = pred(rc(t), x);
		if (res == x) res = v(t);
		return res;
	}
	int succ(int &t, int x)
	{
		if (!t) return x;
		if (x >= v(t)) return succ(rc(t), x);
		int res = succ(lc(t), x);
		if (res == x) res = v(t);
		return res;
	}
	#undef si
	#undef rc
	#undef lc
	#undef v
}

优点是快

跳表

namespace SL //Skip List
{
    const int D = 15;
    std::mt19937 rud(114514);
    struct Node
    {
        Node *nx = nullptr, *dw = nullptr; //后继,下层
        int v = 0, si = 0, lvl = 0; //权值,对应范围的大小,层数
    } pool[N << 2], *upd[D + 1], *rt; //池,待跟新,根
    int tot = 0;
    Node* newnd(){ return &pool[++tot]; }
    void up(Node *u)
    {
        if (u->dw == nullptr) return void(u->si = (u->v != -INF));
        Node *end = u->nx == nullptr ? nullptr : u->nx->dw;
        u->si = 0;
        for (Node *it = u->dw; it != end; it = it->nx) u->si += it->si;
    }
    void find(int val, Node *u = rt)
    {
        upd[u->lvl] = u;
        if (u->nx != nullptr && u->nx->v <= val) return find(val, u->nx);
        if (u->dw != nullptr) return find(val, u->dw);
    }
    void init()
    {
        rt = newnd();
        rt->lvl = 1, rt->v = -INF, upd[1] = rt;
        Node *t = nullptr;
        while (rt->lvl < D)
        {
            t = rt, rt = newnd();
            upd[rt->lvl = t->lvl + 1] = rt;
            rt->dw = t, rt->v = -INF;
        }
    }
    void ins(int val)
    {
        find(val - 1);
        Node *p = newnd(), *t = nullptr;
        p->v = val, p->nx = upd[1]->nx, upd[1]->nx = p;
        up(upd[1]);
        upd[p->lvl = 1] = p;
        while (p->lvl < D && !(rud() & 2))
        {
            t = p, p = newnd();
            p->lvl = t->lvl + 1, p->v = val, p->dw = t;
            p->nx = upd[p->lvl]->nx, upd[p->lvl]->nx = p;
            up(upd[p->lvl]);
            upd[p->lvl] = p;
        }
        for (int i = 1; i <= D; ++i) up(upd[i]);
    }
    void del(int val)
    {
        find(val - 1);
        Node *t = nullptr; bool f = true;
        for (int i = 1; i <= D; ++i)
        {
            if (f && upd[i]->nx != nullptr)
            {
                if (i != 1 && upd[i]->nx->dw != t) f = false;
                else t = upd[i]->nx, upd[i]->nx = t->nx;
            }
            up(upd[i]);
        }
    }
    int rk(int val, Node *u = rt) //查小于val的数的个数
    {
        if (u->nx != nullptr && u->nx->v < val) return u->si + rk(val, u->nx);
        if (u->dw != nullptr) return rk(val, u->dw);
        return u->si;
    }
    int kth(int k, Node *u = rt)
    {
        if (u->si < k) return kth(k - u->si, u->nx);
        return u->dw == nullptr ? u->v : kth(k, u->dw);
    }
    int pre(int val)
    {
        find(val - 1);
        return upd[1]->v;
    }
    int suc(int val)
    {
        find(val);
        return upd[1]->nx->v;
    }
}

CDQ 分治

void cdq(int l, int r)
{
    int mid = (l + r) >> 1;
    cdq(l, mid);
    计算[l, mid]对[mid + 1, r]的影响/计算跨过mid的贡献
    cdq(mid + 1, r);
}

这个顺序不是严格的，可以先左右都递归了再计算中间

李超线段树

struct Line
{
    int k; LL b;
    LL calc(int x){ return dis[bid[x]] * k + b; }
} li[N << 1];
namespace LC
{
    using std::max;
    using std::min;
    int id[N << 2];
    LL mn[N << 4];
    #define mid (l + r >> 1)
    #define lc (u << 1)
    #define rc (u << 1 | 1)
    bool judge(int a, int b, int x){ return li[a].calc(x) > li[b].calc(x); }
	void up(int u, int l, int r)
	{
		mn[u] = min(mn[u], min(li[id[u]].calc(l), li[id[u]].calc(r)));
		mn[u] = min(mn[u], min(mn[lc], mn[rc])); 
	}
    void upd(int u, int l, int r, int ql, int qr, int d)
    {
        if (l >= ql && r <= qr)
        {
            if (judge(id[u], d, mid)) std::swap(id[u], d);
            if (judge(id[u], d, l)) upd(lc, l, mid, ql, qr, d);
            if (judge(id[u], d, r)) upd(rc, mid + 1, r, ql, qr, d);
            return up(u, l, r); 
        }
        if (ql <= mid) upd(lc, l, mid, ql, qr, d);
        if (qr > mid) upd(rc, mid + 1, r, ql, qr, d);
        up(u, l, r);
    }
    LL ask(int u, int l, int r, int ql, int qr)
    {
        if (l >= ql && r <= qr) return mn[u];
        LL res = min(li[id[u]].calc(max(l, ql)), li[id[u]].calc(min(r, qr)));
        if (ql <= mid) res = min(res, ask(lc, l, mid, ql, qr));
        if (qr > mid) res = min(res, ask(rc, mid + 1, r, ql, qr));
        return res;
    }
    #undef mid
    #undef lc
    #undef rc
}

主席树

普通：

namespace CT //Chairman Tree
{
    const int NN = 5e6 + 100; //点一定要开够
    struct Node{ int lc, rc, dat; } tr[NN];
    int rt[N], tot = 0;
    #define lc(x) tr[(x)].lc
    #define rc(x) tr[(x)].rc
    #define dat(x) tr[(x)].dat
    #define mid ((l + r) >> 1)
    void bd(int &u, int l = 1, int r = num)
    {
        u = ++tot;
        tr[u] = {0, 0, 0};
        if (l < r) bd(lc(u), l, mid), bd(rc(u), mid + 1, r);
    }
    void cg(int pos, int d, int &u, int la, int l = 1, int r = num)
    {
        u = ++tot;
        tr[u] = tr[la];
        dat(u) += d;
        if (l == r) return ;
        (pos <= mid) ? cg(pos, d, lc(u), lc(la), l, mid) : cg(pos, d, rc(u), rc(la), mid + 1, r);
    }
    int ask(int ul, int ur, int k, int l = 1, int r = num)
    {
        if (l == r) return l;
        int t = dat(lc(ur)) - dat(lc(ul));
        return (t >= k) ? ask(lc(ul), lc(ur), k, l, mid) : ask(rc(ul), rc(ur), k - t, mid + 1, r);
    }
    #undef lc
    #undef rc
    #undef dat
    #undef mid 
}

带修：

namespace BIT
{
    const int NN = 6e7 + 100, D = 20; //任然是空间要开够
    int rts[2][D];
    namespace CT
    {
        struct Node{ int lc, rc, cnt; } tr[NN];
        int rt[N], tot = 0;
        #define lc(x) tr[(x)].lc
        #define rc(x) tr[(x)].rc
        #define ct(x) tr[(x)].cnt
        #define mid ((l + r) >> 1)
        void cg(int pos, int d, int &u, int l = 1, int r = num)
        {
            if (!u) u = ++tot;
            ct(u) += d;
            if (l == r) return ;
            (pos <= mid) ? cg(pos, d, lc(u), l, mid) : cg(pos, d, rc(u), mid + 1, r);
        }
        int ask(int k, int l = 1, int r = num)
        {
            if (l == r) return l;
            int sum = 0;
            for (int i = rts[1][0]; i; --i) sum += ct(lc(rts[1][i]));
            for (int i = rts[0][0]; i; --i) sum -= ct(lc(rts[0][i]));
            if (sum >= k)
            {
                for (int i = rts[1][0]; i; --i) rts[1][i] = lc(rts[1][i]);
                for (int i = rts[0][0]; i; --i) rts[0][i] = lc(rts[0][i]);
                return ask(k, l, mid);
            }
            else
            {
                for (int i = rts[1][0]; i; --i) rts[1][i] = rc(rts[1][i]);
                for (int i = rts[0][0]; i; --i) rts[0][i] = rc(rts[0][i]);
                return ask(k - sum, mid + 1, r);
            }
        }
        #undef lc
        #undef rc
        #undef ct
        #undef mid
    }
    using CT::rt;
    #define lb(x) ((x) & (-(x)))
    void cg(int x, int d){ for (int i = x; i <= n; i += lb(i)) CT::cg(a[x], d, rt[i]); }
    int ask(int l, int r, int k)
    {
        rts[0][0] = rts[1][0] = 0;
        for (int i = r; i; i ^= lb(i)) rts[1][++rts[1][0]] = rt[i];
        for (int i = l - 1; i; i ^= lb(i)) rts[0][++rts[0][0]] = rt[i];
        return CT::ask(k);
    }
    #undef lb
}

K-D Tree

struct Point{ int x[D], w; };
namespace KDT //K-D Tree
{
    const DB a = 0.725;
    int rt, top, rub[M], cur, tot; //rub:回收空间
    Point p[M];
    struct Node
    {
        int mn[D], mx[D], sum, lc, rc, si, k;
        Point p;
    } tr[M];
    #define mn(x) tr[(x)].mn
    #define mx(x) tr[(x)].mx
    #define sum(x) tr[(x)].sum
    #define lc(x) tr[(x)].lc
    #define rc(x) tr[(x)].rc
    #define si(x) tr[(x)].si
    #define k(x) tr[(x)].k
    #define p(x) tr[(x)].p
    int newnode(){ return top ? rub[top--] : ++cur; }
    void up(int u)
    {
        int ls = lc(u), rs = rc(u);
        for (int i = 0; i < D; ++i)
        {
            mn(u)[i] = mx(u)[i] = p(u).x[i];
            if (ls) mn(u)[i] = min(mn(u)[i], mn(ls)[i]), mx(u)[i] = max(mx(u)[i], mx(ls)[i]);
            if (rs) mn(u)[i] = min(mn(u)[i], mn(rs)[i]), mx(u)[i] = max(mx(u)[i], mx(rs)[i]);
        }
        sum(u) = sum(ls) + sum(rs) + p(u).w, si(u) = si(ls) + si(rs) + 1;
    }
    int build(int l, int r, int k)
    {
        if (l > r) return 0;
        int mid = l + r >> 1, u = newnode();
        nth_element(p + l, p + mid, p + r + 1, [&](Point a, Point b){ return a.x[k] < b.x[k]; });
        k(u) = k, p(u) = p[mid], lc(u) = build(l, mid - 1, k ^ 1), rc(u) = build(mid + 1, r, k ^ 1);
        return up(u), u;
    }
    void get_p(int u){ if (u) get_p(lc(u)), p[++tot] = p(u), rub[++top] = u, get_p(rc(u)); }
    void chk(int &u){ if (si(u) * a < max(si(lc(u)), si(rc(u)))) tot = 0, get_p(u), u = build(1, tot, k(u)); }
    void ins(int &u, Point x)
    {
        if (!u)
        {
            u = newnode();
            lc(u) = rc(u) = k(u) = 0, p(u) = x;
            return up(u);
        }
        if (x.x[k(u)] <= p(u).x[k(u)]) ins(lc(u), x);
        else ins(rc(u), x);
        up(u), chk(u);
    }
    bool in(int mx[D], int mn[D], int l[D], int r[D])
    {
        for (int i = 0; i < D; ++i) if (r[i] < mx[i] || l[i] > mn[i]) return false;
        return true;
    }
    bool out(int mx[D], int mn[D], int l[D], int r[D])
    {
        for (int i = 0; i < D; ++i) if (l[i] > mx[i] || r[i] < mn[i]) return true;
        return false;
    }
    int ask(int u, int l[D], int r[D])
    {
        if (!u || out(mx(u), mn(u), l, r)) return 0;
        if (in(mx(u), mn(u), l, r)) return sum(u);
        return (in(p(u).x, p(u).x, l, r) ? p(u).w : 0) + ask(lc(u), l, r) + ask(rc(u), l, r);
    }
	#undef mn
	#undef mx
	#undef sum
	#undef lc
	#undef rc
	#undef si
	#undef k
	#undef p
}

笛卡尔树

void build()
{
	for (int i = 1; i <= n; ++i) tr[i].dat = a[i];
	for (int i = 1, k; i <= n; ++i)
	{
		k = top;
		//找到最下面的一个比当前小的,满足小根堆
		while (k > 0 && tr[stk[k]].dat > tr[i].dat) --k;
		if (k) tr[stk[k]].rc = i;
		if (k < top) tr[i].lc = stk[k + 1];
		top = k;
		stk[++top] = i;
	}
}

哈夫曼树

二叉：

建立小根堆q,把所有点放入
while (堆中元素个数 >= 2)
{
    int x = q.top(); q.pop();
    int y = q.top(); q.pop();
    ans += x + y;
    q.push(x + y);
}

多叉：

用权值为0的点补足点数,使(n - 1) % (k - 1) == 0
建立小根堆q,把所有点放入
while (堆中元素个数 >= k)
{
    取出前k个元素
    ans += 前k个元素和;
    q.push(前k个元素和);
}
把堆中剩下元素取出,计算贡献

树链剖分

重链剖分：

void dfs1(int x, int father, int depth) //求每个的重儿子
{
	dep[x] = depth, fa[x] = father, si[x] = 1;
	for (int i = h[x], y; ~i; i = e[i].ne) if ((y = e[i].ver) != father)
	{
		dfs1(y, x, depth + 1);
		si[x] += si[y];
		if (si[son[x]] < si[y]) son[x] = y;
	}
}
void dfs2(int x, int t) //求dfs序,t:当前节点所在重链的顶点
{ 
	id[x] = ++cnt, nw[cnt] = w[x], top[x] = t;
	if (!son[x]) return; //若是叶节点,直接返回
	dfs2(son[x], t);
	for (int i = h[x]; ~i; i = e[i].ne)
	{
		int y = e[i].ver;
		if (y == fa[x] || y == son[x]) continue;
		dfs2(y, y); //轻儿子一定是其所在重链的顶点
	}
}
void path(int )(int u, int v) //路径操作
{
	while (top[u] != top[v]) //当这两个点不在同一重链
	{ 
		if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
		work(id[top[u]], id[u]); //注意在dfs序中top[u]在u前面
		u = fa[top[u]];
	}
	if (dep[u] < dep[v]) std::swap(u, v);
	work(id[v], id[u]);
}
void tree(int u){ work(id[u], id[u] + si[u] - 1); } //子树操作

长链剖分：

void dfs1(int x, int fa)
{
    dep[x] = dep[fa] + 1, fa[x] = fa;
	for (int i = h[x], y; ~i; i = e[i].ne) if ((y = e[i].ver) != fa)
	{
		dfs1(y, x);
		if (len[y] > len[son[x]]) son[x] = y;
	}
	len[x] = len[son[x]] + 1;
}
void dfs2(int x, int tp)
{
    top[x] = tp;
	if (!son[x]) return ;
	dfs2(son[x], tp);
	for (int i = h[x], y; ~i; i = e[i].ne) if ((y = e[i].ver) != fa[x] && y != son[x]) dfs2(y, y);
}
//常套在dp上:
int dd[N], *d[N], *cur = dd + 1;
void dp(int x)
{
    初始化d[x]和答案
	if (!son[x]) return ;
	d[son[x]] = d[x] + 1;
	dfs2(son[x], x);
	用长儿子的答案跟新x的答案
	for (int i = h[x], y; ~i; i = e[i].ne) if ((y = e[i].ver) != fa[x] && y != son[x])
	{
		d[y] = cur, cur += len[y];
		dfs2(y, x);
		for (int j = 1; j <= len[y]; ++j)
		{
			d[x][j] += d[y][j - 1]; //合并链
			跟新答案
		}
	}
}

动态树

以 UOJ207 为例（LCT 维护子树异或和）

struct LCT
{
    struct Node
    {
        Node *ch[2], *fa;
        ULL v, s, vs;
        bool rev;
    } tr[N];
    const Node _null = (Node){nullptr, nullptr, nullptr, 0, 0, 0, false};
    Node *null = (Node*)&_null, *tot = tr;
    Node* _new(ULL v = 0)
    {
        *tot = (Node){null, null, null, v, v, 0, false};
        return tot++;
    }
    void adt(Node *x){ std::swap(x->ch[0], x->ch[1]), x->rev ^= 1; }
    void up(Node *x){ x->s = x->ch[0]->s ^ x->ch[1]->s ^ x->v ^ x->vs; }
    void dw(Node *x){ if (x->rev) adt(x->ch[0]), adt(x->ch[1]), x->rev = false; }
    bool is_rt(Node *x){ return x->fa->ch[0] != x && x->fa->ch[1] != x; }
    void rot(Node *x)
    {
        Node *y = x->fa, *z = y->fa;
        int k = y->ch[1] == x;
        if (!is_rt(y)) z->ch[z->ch[1] == y] = x;
        x->fa = z;
        y->ch[k] = x->ch[k ^ 1], x->ch[k ^ 1]->fa = y;
        y->fa = x, x->ch[k ^ 1] = y;
        up(y);
    }
    void splay(Node *x)
    {
        static Node *stk[N];
        int top = 0;
        Node *y = x, *z;
        stk[++top] = x;
        while (!is_rt(y)) stk[++top] = y = y->fa;
        while (top) dw(stk[top--]);
        while (!is_rt(x))
        {
            y = x->fa, z = y->fa;
            if (!is_rt(y)) (y->ch[1] == x) ^ (z->ch[1] == y) ? rot(x) : rot(y);
            rot(x);
        }
        up(x);
    }
    void acs(Node *x)
    {
        for (Node *y = null; x != null; y = x, x = x->fa)
        {
            splay(x);
            x->vs ^= x->ch[1]->s ^ y->s;
            x->ch[1] = y;
            up(x);
        }
    }
    void mk_rt(Node *x){ acs(x), splay(x), adt(x); }
    Node* f_rt(Node *x)
    {
        acs(x), splay(x);
        while (x->ch[0] != null) dw(x), x = x->ch[0];
        return x;
    }
    void lk(int idx, int idy)
    {
        Node *x = tr + idx - 1, *y = tr + idy - 1;
        mk_rt(x);
        if (f_rt(y) == x) return ; //find root的同时完成了acess和splay
        x->fa = y, y->vs ^= x->s;
        up(y);
    }
    void cut(int idx, int idy)
    {
        Node *x = tr + idx - 1, *y = tr + idy - 1;
        mk_rt(x);
        if (f_rt(y) != x) return ;
        x->fa = y->ch[0] = null;
        up(y);
    }
    void cg(int idx, ULL v)
    {
        Node *x = tr + idx - 1;
        acs(x), splay(x), x->v ^= v;
        up(x); 
    }
    ULL ask(int idx, int idy)
    {
        Node *x = tr + idx - 1, *y = tr + idy - 1;
        mk_rt(x), acs(y), splay(y);
        return x->s;
    }
} lct;

补充，如何用 LCT 支持一些奇怪的操作：

维护子树信息和：思路是维护虚子树信息和； access 只要在更换右儿子的同时维护一下即可；而在 link 的时候， $x$ make_root 后把 $y$ 要 access 再 splay 一下避免 $y$ 有祖先信息需要维护
维护边权：思路是每个点定义他的“前一条边”和“后一条边”，前一条边指的即是他在原树中与父亲之间的边（可能不存在)，而后一条边指的是在当前的链剖分下，与他在同一条剖分链上的儿子与他之间的边（可能不存在），然后每个点维护它的维护他的前一条边和后一条边是哪条，注意是维护是哪条边，而不是直接维护边权

考虑这两两个边的修改：在 link 的时候， $x$ 的前一条边要修改；在 cut 的时候，一个点的前一条边设成没有，另一个的后一条边设成没有；在 access 的时候，我们有更换 $x$ 的右儿子的操作，即改变了当前的链剖分，所以 $x$ 的后一条边理应变成他新的右儿子所在的 splay 里最左边的点的前一条边，而为了找到这一条边，我们还需要维护每个 splay 的第一条边和最后一条边，即最左边的点的前一条边和最右边的点的后一条边，（为什么要维护最后一条边呢，因为在翻转的时候我们要交换这两个值）；然后我们对每个点维护他的 splay 子树所代表的链的边权信息和（注意一个 splay 所代表的链所包含的边只有那些两个端点都在这个 splay 里的边）；那么我们考虑这个信息的合并，如果一个点有左子树，那么他的前一条边的另一个端点一定在左子树里，所以他的链信息和就要加上左子树的链信息和以及他的前一条边的信息，右子树亦然；我们考虑链修改操作，与链信息合并类似，如果他有左儿子，那么更改他的前一条边的权值，右儿子亦然，然后对这个点打标

字符串

KMP

ne[1] = 0;
for (int i = 2, j = 0; i <= s_len; ++i)
{
    while (j && s[i] != s[j + 1]) j = ne[j];
    if (s[i] == s[j + 1]) ++j;
    ne[i] = j;
}
for (int i = 1, j = 0; i <= t_len; ++i)
{
    while (j && (t[i] != s[j + 1] || j == s_len)) j = ne[j];
    if (t[i] == s[j + 1]) ++j;
    if (j == s_len); // 此时t[i - s_len + 1, i] = s
}

下标均从 $1$ 开始

Z函数

Z[1] = s_len;
for (int i = 2, l = 0, r = 0; i <= s_len; ++i)
{
    if (i <= r) Z[i] = std::min(Z[i - l + 1], r - i + 1);
    while (Z[i] + i <= s_len && s[Z[i] + i] == s[Z[i] + 1]) ++Z[i];
    if (i + Z[i] - 1 > r) r = i + Z[i] - 1, l = i;
}
for (int i = 1, l = 0, r = 0, as; i <= t_len; ++i)
{
    as = 0;
    if (i <= r) as = std::min(Z[i - l + 1], r - i + 1);
    while (as + i <= t_len && s[as + 1] == t[as + i]) ++as;
    if (i + as - 1 > r) r = i + as - 1, l = i;
    //此时的as就是t[i, s_len]与s的LCP长度
}

下标从 $1$ 开始

Trie

普通：

namespace Trie
{
	int ch[N][26], ed[N], tot = 1;
	void ins(char *s)
	{
		int p = 1;
		for (; *s != '\0'; ++s)
		{
			if (!ch[p][*s - 'a']) ch[p][*s - 'a'] = ++tot;
			p = ch[p][*s - 'a'];
		}
		++ed[p];
	}
	bool find(char *s)
	{
		int p = 1;
		for (; *s != '\0'; ++s)
		{
			if (!ch[p][*s - 'a']) return false;
			p = ch[p][*s - 'a'];
		}
		if (ed[p]) return true;
	}
}

Trie 的根是 $1$ ；注意空间要开够

可持久化：

namespace Trie
{
	AR<int, 26> ch[N];
	int rt[M], cid, tot;
	void ins(char *s)
	{
		int p = rt[cid], q = rt[++cid] = ++tot;
		for (; *s != '\0'; ++s)
		{
			if (p) ch[q] = ch[p];
			ch[q][*s - 'a'] = ++tot;
			p = ch[p][*s - 'a'], q = ch[q][*s - 'a'];
		}
	}
	bool find(int id, char *s)
	{
		int p = rt[id];
		for (; *s != '\0'; ++s)
		{
			if (!ch[p][*s - 'a']) return false;
			p = ch[p][*s - 'a'];
		}
		return true;
	}
}

任然是要注意空间

最小表示法

int get_min(char *s) //求串s的最小表示,完成后答案存在s[k...k + len - 1]中
{
	int len = strlen(s + 1);
	for (int i = 1; i <= len; ++i) s[i + len] = s[i];
	int i = 1, j = 2, k;
	while (i <= len && j <= len)
	{
		for (k = 0; k <= len && s[i + k] == s[j + k]; ++k);
		if (k > len) break;
		if (s[i + k] > s[j + k]) i += k + 1;
		else j += k + 1;
		if (i == j) ++j;
	}
	k = std::min(i, j);
	s[k + len] = '\0';
	return k;
}

注意空间要开两倍

Manacher

int manacher(char *s)
{
	STC char t[N << 1]; //临时字符串要两倍
	STC int p[N << 1];
	int len = strlen(s + 1), mr = 0, mid, res = 0;
	t[++mr] = '$', t[++mr] = '#';
	for (int i = 1; i <= len; ++i) t[++mr] = s[i], t[++mr] = '#';
	t[++mr] = '^';
	len = mr, mr = 0;
	for (int i = 2; i <= len; ++i)
	{
		p[i] = i < mr ? std::min(p[mid * 2 - i], mr - i) : 1;
		while (t[i - p[i]] == t[i + p[i]]) ++p[i];
		if (i + p[i] > mr) mr = i + p[i], mid = i;
	}
	for (int i = 1; i <= len; ++i) res = std::max(res, p[i]);
	return res - 1;
}

AC 自动机

namespace AC
{
	int ch[N][26], tot, in[N], as[N], fail[N];
	std::vector<int> ed[N];
	void ins(char *s, int id)
	{
		int p = 0;
		for (; *s != '\0'; ++s)
		{
			if (!ch[p][*s - 'a']) ch[p][*s - 'a'] = ++tot;
			p = ch[p][*s - 'a'];
		}
		ed[p].pb(id);
	}
	void get_fail()
	{
		std::queue<int> q;
		fail[0] = 0;
		for (int i = 0; i < 26; ++i) if (ch[0][i])
		{
			fail[ch[0][i]] = 0;
			q.push(ch[0][i]);
		}
		while (!q.empty())
		{
			int u = q.front(); q.pop();
			for (int i = 0, v; i < 26; ++i)
				if (v = ch[u][i])
				{
					fail[v] = ch[fail[u]][i];
					++in[fail[v]];
					q.push(v);
				}
				else ch[u][i] = ch[fail[u]][i]; //优化
		}
	}
	void ask(char *s, int ans[])
	{
		int p = 0;
		std::queue<int> q;
		int ct = 0;
		for (; *s != '\0'; ++s)
		{
			++ct;
			p = ch[p][*s - 'a'];
			++as[p];
		}
		for (int i = 1; i <= tot; ++i) if (!in[i]) q.push(i);
		while (!q.empty())
		{
			int u = q.front(), v; q.pop();
			for (int i : ed[u]) ans[i] = as[u];
			v = fail[u];
			as[v] += as[u];
			if (!(--in[v])) q.push(v);
		}
	}
}

SAM

namespace SAM
{
    struct Node{ int len, fa, ch[26]; } nd[N << 1];
    int tot = 1, last = 1;
    #define l(x) nd[(x)].len
    #define f(x) nd[(x)].fa
    #define c(x, y) nd[(x)].ch[(y)]
    void ins(int x)
    {
        int p = last, cur = last = ++tot;
        si[tot] = 1;
        l(cur) = l(p) + 1;
        while (p && !c(p, x)) c(p, x) = cur, p = f(p);
        if (!p) f(cur) = 1;
        else
        {
            int s = c(p, x);
            if (l(s) == l(p) + 1) f(cur) = s;
            else
            {
                int clone = ++tot;
                nd[clone] = nd[s], l(clone) = l(p) + 1;
                f(s) = f(cur) = clone;
                while (p && c(p, x) == s) c(p, x) = clone, p = f(p);
            }
        }
    }
    #undef l
    #undef f
    #undef c
}

广义 SAM

离线版：

struct Trie
{
	int tot, c[L], fa[L], ch[L][26];
	Trie() : tot(1) {}
	void ins(char *s)
	{
		int p = 1;
		while (*s != '\0')
		{
			int t = *s++ - 'a';
			if (!ch[p][t]) ch[p][t] = ++tot, fa[tot] = p, c[tot] = t;
			p = ch[p][t];
		}
	}
} trie;
struct SAM
{
	struct Node{ int fa, len, ch[26]; } nd[L << 1];
	int& f(int x){ return nd[x].fa; }
	int& l(int x){ return nd[x].len; }
	int& c(int x, int y){ return nd[x].ch[y]; }
	int tot;
	SAM() : tot(1) {}
	int ins(int x, int las)
	{
		int p = las, cur = ++tot;
		l(cur) = l(p) + 1;
		while (p && !c(p, x)) c(p, x) = cur, p = f(p);
		if (!p) f(cur) = 1;
		else
		{
			int s = c(p, x);
			if (l(s) == l(p) + 1) f(cur) = s;
			else
			{
				int cl = ++tot;
				nd[cl] = nd[s], l(cl) = l(p) + 1;
				f(cur) = f(s) = cl;
				while (p && c(p, x) == s) c(p, x) = cl, p = f(p);
			}
		}
		return cur;
	}
	void bd()
	{
		std::queue<int> q;
		int pos[L];
		for (int i = 0; i < 26; ++i) if (trie.ch[1][i]) q.push(trie.ch[1][i]);
		pos[1] = 1;
		while (!q.empty())
		{
			int x = q.front(); q.pop();
			pos[x] = ins(trie.c[x], pos[trie.fa[x]]);
			for (int i = 0; i < 26; ++i) if (trie.ch[x][i]) q.push(trie.ch[x][i]);
		}
	}
} sam;

在线：

struct SAM
{
	struct Node{ int len, fa, ch[26]; } nd[L << 1];
	int& l(int x){ return nd[x].len; }
	int& f(int x){ return nd[x].fa; }
	int& c(int x, int y){ return nd[x].ch[y]; }
	int tot;
	SAM() : tot(1) {}
	int ins(int x, int las)
	{
		if (c(las, x))
		{
			int p = las, s = c(p, x);
			if (l(s) == l(p) + 1) return s;
			else
			{
				int cl = ++tot;
				nd[cl] = nd[s], l(cl) = l(p) + 1;
				while (p && c(p, x) == s) c(p, x) = cl, p = f(p);
				f(s) = cl;
				return cl;
			}
		}
		int cur = ++tot, p = las;
		l(cur) = l(p) + 1;
		while (p && !c(p, x)) c(p, x) = cur, p = f(p);
		if (!p) f(cur) = 1;
		else
		{
			int s = c(p, x);
			if (l(s) == l(p) + 1) f(cur) = s;
			else
			{
				int cl = ++tot;
				nd[cl] = nd[s], l(cl) = l(p) + 1;
				while (p && c(p, x) == s) c(p, x) = cl, p = f(p);
				f(s) = f(cur) = cl;
			}
		}
		return cur;
	}
} sam;

SA

namespace SA
{
    const int D = 16;
    int sa[N], rk[N], hei[N], mn[N][D], lg2[N], len;
    int x[N], y[N], c[N]; 
    template<typename T>
    void get_sa(T s[], int _len, int mxv)
    {
        len = _len;
        int i, k, nxv;
        for (i = 1; i <= len; ++i) ++c[x[i] = s[i]];
        for (i = 2; i <= mxv; ++i) c[i] += c[i - 1];
        for (i = len; i; --i) sa[c[x[i]]--] = i;
        for (k = 1; k <= len; k <<= 1)
        {
            for (nxv = 0, i = len - k + 1; i <= len; ++i) y[++nxv] = i;
            for (i = 1; i <= len; ++i) if (sa[i] > k) y[++nxv] = sa[i] - k;
            memset(c + 1, 0, mxv << 2);
            for (i = 1; i <= len; ++i) ++c[x[i]];
            for (i = 2; i <= mxv; ++i) c[i] += c[i - 1];
            for (i = len; i; --i) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
            std::swap(x, y);
            x[sa[1]] = nxv = 1;
            for (i = 2; i <= len; ++i) x[sa[i]] = y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? nxv : ++nxv;
            if (nxv == len) break;
            mxv = nxv;
        }
        for (int i = 1; i <= len; ++i) rk[sa[i]] = i;
    }
    template<typename T>
    void get_hei(T s[])
    {
        for (int i = 1, j, k = 0; i <= n; ++i)
        {
            if (rk[i] == 1) continue;
            if (k) --k;
            j = sa[rk[i] - 1];
            while (i + k <= len && j + k <= len && s[i + k] == s[j + k]) ++k;
            hei[rk[i]] = k;
        }
    }
    void prev()
    {
        lg2[1] = 0;
        for (int i = 2; i <= len; ++i) lg2[i] = lg2[i >> 1] + 1;
        for (int i = 1; i <= len; ++i) mn[i][0] = hei[i];
        for (int j = 1, t = lg2[len]; j <= t; ++j)
            for (int i = 1; i <= len - (1 << j) + 1; ++i) mn[i][j] = std::min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
    }
    int lcp(int i, int j)
    {
        if (i == j) return len - sa[i] + 1;
        if (i > j) std::swap(i, j);
        ++i;
        int t = lg2[j - i + 1];
        return std::min(mn[i][t], mn[j - (1 << t) + 1][t]);
    }
}

图论

单源最短路

Dij ：

void dij(int star)
{
    std::priority_queue<PII> q;
    for (int i = 1; i <= n; ++i) dis[i] = INF;
    dis[star] = 0;
    q.push({0, star});
    int x, y;
    while (!q.empty())
    {
        x = q.top().se, q.pop();
        if (vis[x]) continue;
        vis[x] = true;
        for (int i = h[x], y; ~i; i = e[i].ne) if (!vis[y = e[i].ver] && dis[y] > dis[x] + e[i].w)
		{
			dis[y] = dis[x] + e[i].w;
			q.push({-dis[y], y});
		}
    }
}

spfa（慎用）：

void spfa(int star)
{
    queue<int> q;
    for (int i = 1; i <= n; ++i) dis[i] = INF;
    dis[star] = 0, vis[star] = true;
    q.push(star);
    int x, y;
    while (!q.empty())
    {
        x = q.front(), q.pop();
        vis[x] = false;
        for (int i = h[x]; ~i; i = e[i].ne) if (dis[y = e[i].ver] > dis[x] + e[i].w)
		{
			dis[y] = dis[x] + e[i].w;
			if (!vis[y]) vis[y] = true, q.push(y);
		}
    }
}

判负环

bool spfa(int star) //判断是否有能从star到达的负环
{
    queue<int> q;
    for (int i = 1; i <= n; ++i) dis[i] = INF, cnt[i] = 0, vis[i] = false;
    dis[star] = 0, vis[star] = true;
    q.push(star);
    int x, y;
    while (!q.empty())
    {
        x = q.front(), q.pop();
        v[x] = false;
        for (int i = h[x]; ~i; i = e[i].ne) if (dis[y = e[i].ver] > dis[x] + e[i].w)
		{
			dis[y] = dis[x] + e[i].w, cnt[y] = cnt[x] + 1;
			if (cnt[y] >= n) return false;
			if (!vis[y]) vis[y] = true, q.push(y);
		}
        
    }
    return true;
}

差分约束

建图:
	对于每个形如x[i] - x[j] <= c的不等式,连有向边(j, i, c)
    增加一个0号节点,对于每个i,连边(0, i, 0),表示x[i] <= 0(我们先求出一组负解)
完成以后以0为源点跑spfa,若出现负环则无解;否则dis[]即为一组负数解

多源最短路

Floyed ：

memset(dis, 0x3f, sizeof dis);
for (int i = 1; i <= n; ++i) dis[i][i] = 0;
用dis做邻接矩阵存图
for (int k = 1; k <= n; ++k)
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]);

当然也可以做 $n$ 次单源最短路

最小生成树

Kruskal ：

struct Edge{ int from, to, w; } e[M];
读入数据,初始化并查集
sort(e + 1, e + 1 + m, [&](Edge x, Edge y){ return x.w < y.w; });
for (int i = 1, x, y; i <= m; ++i)
{
    x = get(e[i].from), y = get(e[i].to); //这里的get和merge就是并查集
    if (x != y) ans += e[i].w, merge(x, y);
}

Prim ：

memset(dis, 0x3f, sizeof dis);
memset(vis, 0, sizeof vis);
dis[1] = 0;
for (int i = 1, t; i <= n; ++i)
{
    t = -1;
    for (int j = 1; j <= n; ++j) if (!vis[j] && (t == -1 || dis[j] < dis[t])) t = j;
    vis[t] = true;
    for (int j = 1; j <= n; ++j) if (!vis[j]) dis[j] = std::min(dis[j], map[t][j]);
}
此时dis[]的和就是答案

Kruskal 重构树

Kruskal 重构树的建树流程为：

把所有边排序，记边为 $(x, y, z)$ ，表示 $x \to y$ ，权为 $z$
构建 $n$ 个无权点，没有边
每次取出一条边 $(x, y, z)$ ：
- 若 $x, y$ 联通（在同一棵树），不管它
- 否则，新建一个节点 $t$ ，记 $x, y$ 所在树的根为 $r_{x}, r_{y}$ ，让 $t$ 的左右儿子分别为 $r_{x}, r_{y}$ ，并让 $t$ 的点权为 $z$

不难发现 kruskal 重构树有如下性质：

它是一棵二叉树（更进一步，它其实就是个二叉堆），树上除叶子结点以外的点都对应着原来生成树中的边，叶子结点就是原来生成树上的节点
除叶节点外，儿子节点对应边一定排序在父亲前面，即从每个点到根节点上除叶子结点外按顺序访问到的点的点权是单调的
对于叶节点 $x, y$ ， $l c a (x, y)$ 对应的边就是最小生成树中联通 $x, y$ 的“瓶颈边”（它排序在最后）

树的直径

dp 自然可以，但不好求出具体的路径

两次 bfs/dfs 的流程如下：

任选一个点出发，找到离该点最远的节点 $p$
从 $p$ 出发，找到离 $p$ 最远的节点 $q$
$p, q$ 间的路径就是树的一条直径；如要得到具体路径，在进行 $2$ 时记录前驱即可

无向图 Tarjan

判桥：

void tarjan(int x, int in_e)
{
	dfn[x] = low[x] = ++num;
	for (int i = h[x], y; ~i; i = e[i].ne)
		if (!dfn[y = e[i].ver;])
		{
			tarjan(y, i);
			low[x] = std::min(low[x], low[y]);
			if (low[y] > dfn[x]) bridge[i] = bridge[i ^ 1] = true;
		}
		else if (i != (in_e ^ 1)) low[x] = std::min(low[x], dfn[y]);
}
for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i,-1);

边双联通分量：

在判桥的代码后加入以下代码:
void dfs(int x)
{
	c[x] = dcc;
	for (int i = h[x], y; ~i; i = e[i].ne) if (!bridge[i] && !c[y = e[i].ver]) dfs(y);
}
for (int i = 1; i <= n; ++i) if (!c[i]) ++dcc, dfs(i);
printf("the num of e-DCC is %d\n", dcc);
for (int i = 1; i <= n; ++i) printf("%d blongs to e-DCC %d\n", i, c[i]);

判割点：

void tarjan(int x)
{
	dfn[x] = low[x] = ++num;
    (1)
	int f = 0;
	for (int i = h[x], y; ~i; i = e[i].ne)
		if (!dfn[y = e[i].ver])
		{
			tarjan(y);
			low[x] = std::min(low[x], low[y]);
			if (low[y] >= dfn[x])
			{
				++f;
				if (x != root || f > 1) cut[x] = true;
				(2)
            }
		}
		else low[x] = std::min(low[x], dfn[y]);
}
for (int i = 1; i <= n; ++i) if (!dfn[i]) root = i, tarjan(i);

点双联通分量：

在上面求割点的代码的(1), (2)处加入以下两段代码:
(1):
stk[++top] = x; //栈记录经过的节点
if (x == root && h[x] == -1) return void(dcc[++cnt].pb(x)); //孤立点
(2):
++cnt;
int z;
do
{
    z = stk[top--];
    dcc[cnt].pb(z);
} while (z != y);
dcc[cnt].pb(x);

有向图 Tarjan

强连通分量：

void tarjan(int x)
{
	dfn[x] = low[x] = ++num;
	stk[++top] = x, ins[x] = true;
	for (int i = h[x], y; ~i; i = e[i].ne)
		if (!dfn[y = e[i].ver])
		{
			tarjan(y);
			low[x] = std::min(low[x], low[y]);
		}
		else if (ins[y]) low[x] = std::min(low[x], dfn[y]);
	if (dfn[x] == low[x])
	{
		++cnt;
		int y;
		do
		{
			y = stk[top--], ins[y] = false;
			c[y] = cnt, scc[cnt].pb(y);
		} while (x != y);
	}
}

2-SAT

建图:
	图中有2n个节点,i表示x[i]为假,i + n表示x[i]为真
    按命题连边:
		1.x[i] and x[j] = 0:连(i + n, j)和(j + n, i)
        2.x[i] and x[j] = 1:连(i, i + n)和(j, j + n) (若有一个为0就产生矛盾)
        3.x[i] or x[j] = 0:连(i + n, i)和(j + n, j) (若有一个为1就产生矛盾)
        4.x[i] or x[j] = 1:连(i, j + n)和(j, i + n)
        5.x[i] xor x[j] = 0:连(i, j), (j, i), (i + n, j + n)和(j + n, i + n)
        6.x[i] xor x[j] = 1:连(i, j + n), (j, i + n), (i + n, j)和(j + n, i)
    有向图Tarjan缩点,若i和i + n在一个强联通分量说明无解;否则任意一个强连通分量代表一组解

圆方树

直接对原图进行无向图 Tarjan ，因为原图上每个环都是一个点双，而且在栈中的顺序就是环上点的顺序，如果一个点 $i$ 的出边 $(i, j)$ 满足 $d f n (i) < l o w (j)$ ，说明 $(i, j)$ 是一条树边，直接加上即可；如果 $d f n (i) = l o w (j)$ ，那么我们找到了一个环（可能是重边造成的二元环），则从栈中取出点直到取出 $j$ 为止，设这样从栈中取出的点集为 $R$ ，则 $i$ 和 $R$ 构成一个环

对于环，我们新建一个方点，对环上每个点连边即可

void tarjan(int x)
{
    low[x] = dfn[x] = ++dfc;
    stk[++top] = x;
    for (auto y : G[x])
        if (!dfn[y])
        {
            tarjan(y);
            low[x] = min(low[x], low[y]);
            if (low[y] == dfn[x])//标志着找到一个以x为根的点双连通分量
            {
                ++cnt; //增加方点个数
                for (int z = 0; z != y; --top) //这里一定要让z=0!
                {
                    z = stk[top];
                    T[cnt].push_back(z);
                    T[z].push_back(cnt);
                }
                //注意x自身也要连边（但不退栈）
                T[cnt].push_back(x);
                T[x].push_back(cnt);
            }
        }
        else low[x] = min(low[x], dfn[y]);
}
for (int i = 1; i <= n; ++i) if (!dfn[i]) tarjan(i), --top; //注意到退出Tarjan时栈中还有一个元素即根,将其退栈

注意新图的节点数变成两倍

三元环计数

要改造一下边，把无向图变成有向图，总时间为 $O (m \sqrt{m})$ ，这同时也是三元环的个数上界

读入数据,去掉重边,记录每个点的度(下面假设用PII存的边)
for (int i = 1; i <= m; ++i)
{
    if (_e[i].fi < _e[i].se) std::swap(_e[i].fi, _e[i].se);
	dep[_e[i].fi] >= dep[_e[i].se] ? add(_e[i].fi, _e[i].se) : add(_e[i].se, _e[i].fi);
}
int find3c()
{
    int res = 0;
    for (int x = 1; x <= n; ++x)
    {
        for (int i = h[x]; ~i; i = e[i].ne) vis[e[i].ver] = true;
        for (int i = h[x]; ~i; i = e[i].ne)
            for (int j = h[e[i].ver]; ~j; j = e[j].ne) res += vis[e[j].ver];
        for (int i = h[x]; ~i; i = e[i].ne) vis[e[i].ver] = false;
    }
    return res;
}

四元环计数

我们将每个点按度数大小重新编号，度数相同原来编号大的点在前的方法，就可以通过编号直接得到任意两个点的关系

设重新编号后排名为 $r k$ ，枚举四圆环中 $r k$ 最大的点 $x$ ，再枚举 $x$ 的出点 $y$ ，枚举 $y$ 的出点 $z$ （这里直接枚举无向边，注意判断 $r k (x) > r k (y) > r k (z)$ ），这里就得到了一个长度为 $2$ 的链了，再枚举一个点 $c$ ，只要 $r k (x) > r k (c)$ 就计入答案的贡献，不管 $r k (c)$ 和 $r k (z)$ 的关系

时间复杂度还是 $O (m \sqrt{m})$ ，注意四元环的个数上界是 $n m \sqrt{m}$ ，可能要 LL

读入数据,记录每个点的度
for (int i = 1; i <= n; ++i) id[i] = i;
std::sort(id + 1, id + n + 1, [&](int x, int y){ return deg[x] == dep[y] ? x < y : dep[x] < dep[y]; });
for (int i = 1; i <= n; ++i) rk[id[i]] = i;
LL find4c()
{
    LL res = 0;
    for (int x = 1; x <= n; ++x)
    {
        for (int i = h[x]; ~i; i = e[i].ne) if (rk[x] > rk[e[i].ver])
            for (int j = h[e[i].ver]; ~j; j = e[j].ne) if (rk[x] > rk[e[j].ver]) res += cnt[e[j].ver]++;
        for (int i = h[x]; ~i; i = e[i].ne) if (rk[x] > rk[e[i].ver])
            for (int j = h[e[i].ver]; j != -1; j = e[j].ne) cnt[e[i].ver] = 0;
    }
    return res;
}

欧拉回路

void euler()
{
	stk[++top] = 1;
	while (top)
	{
		int x = stk[top], i = h[x];
		while (i != -1 && vis[i]) i = ne[i];
		if (i != -1)
		{
			stk[++top] = e[i].ver;
			vis[i] = vis[i ^ 1] = true; //这里用了成对存储的技巧
			h[x] = ne[i]; //保证时间复杂度
		}
		else
		{
			--top;
			ans[++cnt] = x;
		}
	}
}
最后ans[]存有一条欧拉回路

二分图

判定：染色法

求最大匹配：

网络流可做，这里介绍匈牙利，时间为 $O (n m)$ ：

bool dfs(int x)
{
	for (int i = h[x], y; ~i; i = e[i].ne) if (!vis[y = e[i].ver])
	{
		vis[y] = true;
		if (!match[y] || dfs(match[y])) return match[y] = x, true;
	}
	return false;
}
for (int i = 1; i <= n; ++i)
{
	memset(vis, false, sizeof vis);
	if (dfs(i)) ++ans;
}

一般图最大匹配

智慧法（可能被卡）：

std::mt19937 rud(114514);
DB when(){ return (DB)(clock() - st) / CLOCKS_PER_SEC; }
void link(int x, int y){ match[x] = y, match[y] = x; }
int work(int x)
{
    std::shuffle(e[x].begin(), e[x].end(), rud);
    vis[x] = true;
    for (auto y : e[x]) if (!match[y]) return link(x, y), vis[y] = true;
    for (auto y : e[x])
    {
        int z = match[y];
        if (vis[z]) continue;
        link(x, y), match[z] = 0;
        if (work(z)) return 1;
        link(y, z), match[x] = 0;
    }
    return 0;
}
读入(用vector存图)
clock_t st = clock();
while (when() < 0.9)
    for (int i = 1; i <= n; ++i) if (!match[i])
    {
        memset(vis + 1, false, n * sizeof(bool));
        ans += work(i);
    }
最后ans是最大匹配数,match即为匹配  

带花树：

link同上,get就是并查集
void dad(int x, int y)
{
    if (!match[x] && !match[y]) link(x, y), ++ans; //优化
    add(x, y), add(y, x);
}
void rev(int x){ if (x) rev(match[pre[x]]), link(x, pre[x]); }
int lca(int x, int y)
{
    STC int dfn[N], cnt = 0;
    /*
    dfn是一个标记数组,一边打标即一边上跳，第一个重复点就是花根
	花根一定是一个绿点,所以可以隔点上跳
    */
    for (++cnt; ;x = pre[match[x]], swap(x, y))
		if (dfn[x = get(x)] == cnt) return x;
        else if (x) dfn[x] = cnt;
}
void blossom(int x, int y, int w) //缩奇环(开花)
{
    for (; get(x) != w; x = pre[y])
    {
        pre[x] = y, y = match[x];
        fa[x] = fa[y] = w;
        if (col[y] == 2) col[y] = 1, q.push(y);
    }
}
int aug(int x) //带花树
{
    if ((ans + 1) * 2 > n) return 0;
    for (int i = 1; i <= n; ++i) fa[i] = i, col[i] = pre[i] = 0;
    while (!q.empty()) q.pop();
    for (q.push(x), col[x] = 1; !q.empty(); q.pop())
        for (int u = q.front(), i = h[u], v, w; ~i; i = e[i].ne)
        {
            if (get(u) == get(v = e[i].ver) || col[v] == 2) continue;
            if (!col[v])
            {
                col[v] = 2, pre[v] = u;
                if (!match[v]) return rev(v), 1;
                col[match[v]] = 1, q.push(match[v]);
            }
            else blossom(u, v, w = lca(u, v)), blossom(v, u, w); //缩环两个方向各一次拼起来
        }
    return 0;
}
读入，加边用dad
for (int i = 1; i <= n; ++i) ans += (!match[i] && aug(i));

Prufer 序列

每次选择一个编号最小的叶结点并删掉它，然后在序列中记录下它连接到的那个结点，重复 $n - 2$ 次后就只剩下两个结点，算法结束，得到的序列可以与原树一一对应

虚树

void ins(int x)
{
    if (!top) return void(stk[++top] = x);
    int z = lca(stk[top], x);
    for (; tp > 1 && dep[z] < dep[stk[top - 1]]; --top) add(stk[top - 1], stk[top]);
    if (dep[z] < dep[stk[top]]) add(z, stk[top--]);
    if (!top || stk[top] != z) stk[++top] = z;
    stk[++top] = x;
}
std::sort(a + 1, a + k + 1, [&](int x, int y){ return dfn[x] < dfn[y]; });
top = ans = idf = 0;
if (a[1] != 1) stk[++top] = 1; //根
for (int i = 1; i <= k; ++i) ins(a[i]);
for (; top > 1; --top) adf(stk[top - 1], stk[top]); //在虚树上建边
计算答案,记得撤销!

虚树的空间和撤销是易错点

常见转换

原图的最大独立集大小 = 补图的最大团大小

二分图：

最大独立集大小 = 总点数 - 最小点覆盖大小
最小点覆盖大小 = 最大匹配大小
最小边覆盖大小 = 总点数 - 最大匹配大小

MCS

namespace MCS
{
	std::vector<int> cnt[N];
	bool vis[N];
	int pos[N], label[N], order[N], ne[N], N_[N];
	int stk[N], top;
	void init(int n)
	{
		for (int i = 1; i <= n; ++i) cnt[i].clear();
		std::memset(vis, false, (n + 1) * sizeof(bool));
		std::memset(pos, 0, (n + 1) << 2);
		std::memset(label, 0, (n + 1) << 2);
		std::memset(order, 0, (n + 1) << 2);
	}
	void mcs()
	{
		for (int i = 1; i <= n; ++i) cnt[0].pb(i);
		int mxct = 0, x = 0;
		for (int i = n; i; --i)
		{
			x = 0;
			while (mxct >= 0)
			{
				for (int j = cnt[mxct].size() - 1; ~j; --j)
					if (vis[cnt[mxct][j]]) cnt[mxct].pop_back();
					else{ x = cnt[mxct][j]; break; }
				if (!x) --mxct;
				else break;
			}
			vis[x] = true;
			order[i] = x, pos[x] = i;
			for (int j = h[x], y; ~j; j = e[j].ne) if (!vis[y = e[j].ver])
			{
				cnt[++label[y]].pb(y);
				mxct = std::max(mxct, label[y]);
			}
		}
	}
	bool judge() //判断是否是弦图
	{
		std::memset(vis, false, (n + 1) * sizeof(bool));
		for (int i = n, ct; i; --i)
		{
			top = 0, ct = 1;
			for (int j = h[order[i]]; ~j; j = e[j].ne) if (pos[e[j].ver] > i)
			{
				vis[stk[++top] = e[j].ver] = true;
				if (pos[stk[top]] < pos[stk[1]]) std::swap(stk[top], stk[1]);
			}
			for (int j = h[stk[1]], y; ~j; j = e[j].ne) if (vis[y = e[j].ver] && y != stk[1]) ++ct;
			if (top && ct != top) return false;
			while (top) vis[stk[top--]] = false;
		}
		return true;
	}
	int _max_clique() //极大团个数
	{
		int res = 0;
		for (int i = 1, x; i <= n; ++i)
		{
			top = 0;
			for (int j = h[order[i]], y; ~j; j = e[j].ne) if (pos[y = e[j].ver] > i)
			{
				stk[++top] = y;
				if (pos[stk[top]] < pos[stk[1]]) std::swap(stk[top], stk[1]);
			}
			ne[order[i]] = stk[1];
			N_[order[i]] = top;
		}
		for (int i = 1; i <= n; ++i)
		{
			if (!vis[order[i]]) ++res;
			if (N_[order[i]] >= N_[ne[order[i]]] + 1) vis[ne[order[i]]] = true;
		}
	}
	int max_clique() //最大团/最小着色
	{
		int res = 0;
		for (int i = 1; i <= n; ++i) res = std::max(res, label[i] + 1);
		return res;
	}
	int max_independent_set() //最大独立集/最小团覆盖
	{
		std::memset(vis, false, (n + 1) * sizeof(bool));
		int res = 0;
		for (int i = 1; i <= n; ++i) if (!vis[order[i]])
		{
			++res;
			vis[order[i]] = true;
			for (int j = h[order[i]]; ~j; j = e[j].ne) vis[e[j].ver] = true;
		}
		return res;
	}
}

Bron-Kerbosch

int n, m;
bool G[N][N]; //存反图
int ans, group[N]; //答案
int cnt[N];
int p[N]; //记录选则
bool dfs(int x, int as)
{
	for (int i = x + 1; i <= n; ++i)
    {
        if (cnt[i] + as <= ans) return false;
        if (G[x][i])
        {
            for (int j = 1; j <= as; ++j) if (!G[i][p[j]]) goto E_O_F_i;
            p[as + 1] = i;
            if (dfs(i, as + 1)) return true;
        }
        E_O_F_i:;
	}
    if (as > ans)
    {
        std::copy(p + 1, p + as + 1, group + 1);
        return ans = as, true;
	}
    return false;
}
void maxClique()
{
    ans = -1;
    for (int i = n; i; --i)
    {
        p[1] = i;
        dfs(i, 1);
        cnt[i] = ans;
    }
}

DP

背包

注意下面初始化都是 0xcf （最小值）

$01$ ：

memset(f, 0xcf, sizeof f), ans = -INF;
for (int i = 1; i <= n; ++i)
	for (int j = m; j >= v[i]; --j) f[j] = std::max(f[j - v[i]] + w[i], f[j]);
for (int i = 1; i <= m; ++i) ans = max(ans, f[i]);

$01$ 退背包（只能求方案数）：

for (int i = 1; i <= m; ++i) f[i] -= f[i - 1] * x; //禁用贡献为x的物品
for (int i = m; i; --i) f[i] += f[i - 1] * x; //加入贡献为x的物品

完全：

memset(f, 0xcf, sizeof f), ans = -INF;
for (int i = 1; i <= n; ++i)
	for (int j = v[i]; j <= m; ++j) f[j] = std::max(f[j - v[i]] + w[i], f[j]);
for (int i = 1; i <= m; ++i) ans = max(ans, f[i]);

多重背包二进制拆分（以下给出拆分代码）：

void split(Node x)
{
	int p = 1;
	while (x.p >= p)
	{
		b[++o].c = x.c * p;
		b[o].t = x.t * p;
		b[o].p = 1;
		x.p -= p;
		p <<= 1;
	}
	if (x.p)
	{
		b[++o].c = x.c * x.p;
		b[o].t = x.t * x.p;
		b[o].p = 1;
	}
}

多重背包单调队列优化：

int calc(int i, int u, int k){ return f[u + k * v[i]] - k * w[i]; }
memset(f, 0xcf, sizeof f), f[0] = 0;
for (int i = 1; i <= n; ++i)
    for (int u = 0; u < v[i]; ++u) // u:余数
    { 
        int hh = 1, tt = 0;
        int maxp = (m - u) / v[i];
        //将初始的候选集合插入队列
        for (int k = maxp - 1; k >= max(maxp - c[i], 0); --k)
        {
            while (hh <= tt && calc(i, u, q[tt]) <= calc(i, u, k)) --tt;
            q[++tt] = k;
        }
        // dp
        for (int p = maxp; p >= 0; p--) //循环状态
        { 
            while (hh <= tt && q[hh] > p - 1) ++hh; //排除过时决策
            if (hh <= tt) f[u + p * v[i]] = std::max(f[u + p * v[i]], calc(i, u, q[hh]) + p * w[i]); //取队头转移
            if (p - c[i] - 1 >= 0) //新决策入队,同时维护单调
            {
                while (hh <= tt && calc(i, u, q[tt]) <= calc(i, u, p - c[i] - 1)) --tt;
                q[++tt] = p - c[i] - 1;
            }
        }
    }

for (int i = 1; i <= m; ++i) ans = std::max(ans, f[i]);

单调队列优化

int q[N], l = 1, r = 0;
for (int i = 1; i <= n; ++i)
{
    while (l <= r && 队头不再合法) ++l;
    用队头跟新d[i]
   	while (l <= r && i优于队尾) --r;
    q[++r] = i;
}

各操作顺序不是严格

斜率优化

考虑 $j$ 优与 $k$ 的条件，把 dp 方程化成 $\frac{Y (j) - Y (k)}{X (j) - X (k)} \leq 无关 j, k 的值 K$ 的形式，然后分情况（以最大值为例）：

$X, K$ 单调：

int q[N], l = 1, r = 0;
//有时候需要先把0入队
for (int i = 1; i <= n; ++i)
{
    while (l < r && (Y(q[l + 1]) - Y(q[l])) > K(i) * (X(q[l + 1]) - X(q[l]))) ++l; //至少保证队列中有一个数
    用队头跟新i
    while (l < r && (Y(i) - Y(q[r])) * (X(q[r]) - X(q[r - 1])) >= (Y(q[r]) - Y(q[r - 1])) * (X(i) - X(q[r]))) --r;
    q[++r] = i;
}

$X$ 不单调， $K$ 单调：

int find(int i, int k)
{
    if (l == r) return q[l];
    int ll = l, rr = r, mid, res;
    while (ll <= rr)
    {
        mid = ll + rr >> 1;
		if ((Y(q[mid + 1]) - Y(q[mid])) <= (X(q[mid + 1]) - X(q[mid])) * k) res = mid, rr = mid - 1;
		else ll = mid + 1;
    }
    return q[res];
}
int q[N], l = 1, r = 0;
for (int i = 1; i <= n; ++i)
{
    int j = find(i, K(i));
    用j跟新i
    while (l < r && (Y(i) - Y(q[r])) * (X(q[r]) - X(q[r - 1])) >= (Y(q[r]) - Y(q[r - 1])) * (X(i) - X(q[r]))) --r;
    q[++r] = i;
}

$X, K$ 都不单调：

bool cmp(int x, int y){ return X(x) == X(y) ? Y(x) > Y(y) : X(x) < X(y); }
void cdq(int l, int r)
{
    if (l == r)
    {
        有时候这里有些操作
		return ;
    }
    int mid = (l + r) >> 1;
    lp = l - 1, rp = mid;
    for (int i = l; i <= r; ++i) (p[i] <= mid ? tmp[++lp] : tmp[++rp]) = p[i];
    for (int i = l; i <= r; ++i) p[i] = tmp[i];
    cdq(l, mid);
    ql = 1, qr = 0;
    for (int i = l; i <= mid; ++i)
    {
		if (i > l && X(p[i]) == X(p[i - 1])) continue;
        while (ql < qr && (Y(q[qr]) - Y(q[qr - 1])) * (X(p[i]) - X(q[qr])) <= (Y(p[i]) - Y(q[qr])) * (X(q[qr]) - X(q[qr - 1]))) --qr;
        q[++qr] = p[i];
    }
    for (int i = mid + 1, u, v; i <= r; ++i)
    {
        while (ql < qr && (Y(q[ql + 1]) - Y(q[ql])) > (X(q[ql + 1]) - X(q[ql])) * K(p[i])) ++ql;
        u = p[i], v = q[ql];
		用v跟新u
    }
    cdq(mid + 1, r);
    lp = tp = l, rp = mid + 1;
    while (lp <= mid && rp <= r) tmp[tp++] = (cmp(p[lp], p[rp]) ? p[lp++] : p[rp++]);
    while (lp <= mid) tmp[tp++] = p[lp++];
    while (rp <= r) tmp[tp++] = p[rp++];
    for (int i = l; i <= r; ++i) p[i] = tmp[i];
}
在进入cdq之前:
for (int i = 1; i <= n; ++i) p[i] = i;
std::sort(p + 1, p + n + 1, [&](int x, int y){ return K(x) < K(y); });
初始化dp数组

四边形不等式

式子： $a \leq b \leq c \leq d$ 若 $w (a, d) + w (b, c) \geq w (a, c) + w (b, d)$ 则满足四边形不等式（想象一个四边形，对边和小于对角线和）

分治打法：

设函数 sol(l, r, L, R) 表示“当然正在处理 $d [l \sim r]$ ，最优决策存在于区间 $[L, R]$ ”，函数伪代码如下：

sol(l, r, L, R)
	if (l > r || L > R) return ;
	mid <- (l + r) >> 1
	for i : L -> R
		找到最优决策点 pos 
	end for
	用 pos 跟新 d[mid]
	sol(l, mid - 1, L, pos)
	sol(mid + 1, r, pos, R)
end sol

要求 $v a l (i, j)$ 不含与 $d [j]$ 有关的项

队列 + 二分打法：

q[h = t = 1] = {0, 1, n}; //把0先入队
for (int i = 1, pos; i <= n; ++i)
{
	while (h <= t && q[h].r < i) ++h;
	用q[h].pos跟新i
	pos = n + 1;
	while (h <= t && 对于q[t].l,i比q[t].pos优) pos = q[t--].l;
	if (h <= t && 对于q[t].r,i比q[t].pos优)
	{
		int l = q[t].l, r = q[t].r, mid;
		while (l <= r)
		{
			mid = (l + r) >> 1;
			if (对于mid,i比q[t].pos优) pos = mid, r = mid - 1;
			else l = mid + 1;
		}
		q[t].r = pos - 1;
	}
	if (pos <= n) q[++t] = {i, pos, n};
}

SOS

子集：

for (int i = 0; i < N; ++i)
    for (int j = (1 << N) - 1; ~j; --j) if ((j >> i) & 1) d[j] += d[j ^ (1 << i)];

超集：

for (int i = 0; i < N; ++i)
    for (int j = (1 << N) - 1; ~j; --j) if (!(j >> i) & 1) d[j] += d[j ^ (1 << i)];

期望

$\begin{array}{r} E (a x + b) = a E (x) + b \\ D (a x + b) = a^{2} D (x) \\ D (x) = E (x^{2}) - E^{2} (x) \end{array}$

网络流

最大流（ Dinic ）：

bool bfs()
{
    STC int q[N];
    int hh = 1, tt = 1, x, y;
	memset(dep, 0, sizeof dep), q[dep[S] = 1] = S, cur[S] = h[S]
    while (hh <= tt)
        for (int i = h[x = q[hh++]]; ~i; i = e[i].ne) if (!dep[y = e[i].ver] && e[i].w)
		{
			dep[y] = dep[x] + 1, cur[y] = h[y];
			if (y == T) return true;
			q[++tt] = y;
		}
    return false;
}
int find(int x, int lim)
{
    if (x == T) return lim;
    int flow = 0, y, t;
    for (int i = cur[x]; i != -1 && flow < lim;  i = e[i].ne)
    {
        cur[x] = i; //这里非常玄学,一定要这样写,压行的话可能会TLE
        if (dep[y = e[i].ver] == dep[x] + 1 && e[i].w)
        {
            if (!(t = find(y, std::min(lim - flow, e[i].w)))) dep[y] = 0;
            e[i].w -= t, e[i ^ 1].w += t, flow += t;
        }
    }
    return flow;
}
LL dinic()
{
    LL res = 0, flow;
    while (bfs()) while(flow = find(S, INF)) res += flow;
    return res;
}

最大流（ HLPP ）：

int hi[N], ex[N], gap[N]; //hi:高度,ex:超额流,gap[i]:高度为i的节点的数量
vector<int> B[N]; // 桶B[i]中记录所有hi[x]=i的x
int level = 0; //溢出节点的最高高度
bool bfs()
{
	queue<int> q;
	for (int i = 1; i <= n; ++i) hi[i] = INF;
	hi[T] = 0;
	q.push(T);
	int x, y;
	while (!q.empty())
	{
		x = q.front(), q.pop();
		for (int i = h[x]; i != -1; i = e[i].ne)
		{
			y = e[i].ver;
			if (e[i ^ 1].w && hi[y] > hi[x] + 1) hi[y] = hi[x] + 1, q.push(y); //从T倒着搜回去走的是反向边,^1以后就变回正向边
		}
	}
	return hi[S] != INF;
}
int push(int x) //尽可能通过能够推送的边推送超额流
{
	bool init = x == S;
	for (int i = h[x], y, k; i != -1; i = e[i].ne)
	{
		y = e[i].ver;
		if (!e[i].w || (init == false && hi[x] != hi[y] + 1)) continue; //初始化时不考虑高度差为1
		k = init ? e[i].w : min(e[i].w, ex[x]); //取到剩余容量和超额流的最小值初始化时可以使源的溢出量为负数
		if (y != S && y != T && !ex[y]) B[hi[y]].push_back(y), level = max(level, hi[y]);
		ex[x] -= k, ex[y] += k, e[i].w -=k, e[i ^ 1].w += k;
		if (!ex[x]) return 0; //如果已经推送完就返回
	}
	return 1;
}
void relabel(int x)  //重贴标签(高度)
{
  	hi[x] = INF;
 	for (int i = h[x]; i != -1; i = e[i].ne)if (e[i].w) hi[x] = min(hi[x], hi[e[i].ver]);
  	if (++hi[x] < n) //只处理高度小于n的节点
  	{
	  	//新的高度,更新gap
	  	B[hi[x]].push_back(x);
	  	level = max(level, hi[x]);
	  	++gap[hi[x]];  
  	}
}
int find_max() //选出当前高度最大的节点之一,如果已经没有溢出节点返回0
{
	while (B[level].empty() && level > -1) --level;
	return level == -1 ? 0 : B[level].back();
}
int hlpp()
{
	if (!bfs()) return 0;
	for (int i = 1; i <= n + 1; ++i) gap[i] = 0;
	for (int i = 1; i <= n; ++i) if (hi[i] != INF) ++gap[hi[i]];
	hi[S] = n;
	push(S); //初始化预流
	int x;
	while (x = find_max())
	{
		B[level].pop_back();
		if (push(x)) //仍然溢出
		{
			if (!--gap[hi[x]])
				for (int i = 1; i <= n; ++i)
					if (i != S && i != T && hi[i] > hi[x] && hi[i] < n + 1)
						hi[i] = n + 1;  // 这里重贴成 n+1 的节点都不是溢出节点
      		relabel(x);
		}
	}
	return ex[T];
}

费用流

bool spfa()
{
    for (int i = 1; i <= n; ++i) dis[i] = INF, cur[i] = h[i];
    std::queue<int> q; //这里只能stl,因为spfa一个点可能入队多次,空间大小未知
    int x, y;
    for (dis[S] = 0, q.push(S), vis[S] = true; !q.empty(); )
    {
        vis[x = q.front()] = false, q.pop();
        for (int i = h[x]; i != -1; i = e[i].ne) if (dis[y = e[i].ver] > dis[x] + e[i].c && e[i].w)
        {
            dis[y] = dis[x] + e[i].c;
            if (!vis[y]) vis[y] = true, q.push(y);
        }
    }
    return dis[T] != INF;
}
int find(int x, int lim)
{
    if (x == T) return lim;
    vis[x] = true;
    int flow = 0, y, t;
    for (int i = cur[x]; i != -1 && flow < lim; i = e[i].ne)
    {
        cur[x] = i;
        if (!vis[y = e[i].ver] && dis[y] == dis[x] + e[i].c && e[i].w)
        {
            if (!(t = find(y, std::min(lim - flow, e[i].w)))) continue;
            e[i].w -= t, e[i ^ 1].w += t, flow += t, mincost += t * e[i].c;
        }
    }
    vis[x] = false;
    return flow;
}
void mcmf()
{
    maxflow = mincost = 0;
    int flow;
    while (spfa()) while(flow = find(S, INF)) maxflow += flow;
}

最小割树

把 Dinic 的函数改一下：

void init(int _s, int _t)
{
    S = _s, T = _t;
    for (int i = 0; i < idx; i += 2) e[i].w = (e[i].w + e[i ^ 1].w), e[i ^ 1].w = 0;
}
int dinic(int _s, int _t)
{
    init(_s, _t);
    int res = 0, flow;
    while (bfs()) while (flow = find(S, INF)) res += flow;
    return res;
}

再加上：

namespace GHT //Gomory-Hu Tree
{
    const int D = 10;
    int nd[N], h[N], idx = 0, dep[N], f[N][D], mn[N][D];
    std::mt19937 rud(114514);
    Edge e[N << 1];
    void add(int x, int y, int z){ e[idx] = {h[x], y, z}, h[x] = idx++; }
    void build(int l, int r)
    {
        if (l == r) return ;
        STC int tp1[N], tp2[N];
        int s, t, flow, ct1 = 0, ct2 = 0;
        s = nd[l], t = nd[l + 1];
        flow = Dinic::dinic(s, t);
        add(s, t, flow), add(t, s, flow);
        for (int i = l; i <= r; ++i) (Dinic::dep[nd[i]] ? tp1[++ct1] : tp2[++ct2]) = nd[i];
        for (int i = 1; i <= ct1; ++i) nd[i + l - 1] = tp1[i];
        for (int i = 1; i <= ct2; ++i) nd[i + l + ct1 - 1] = tp2[i];
        build(l, l + ct1 - 1), build(l + ct1, r);
    }
    void bfs()
    {
        std::queue<int> q;
        for (q.push(1), dep[1] = 1; !q.empty(); )
        {
            int x = q.front(); q.pop();
            for (int i = h[x], y; ~i; i = e[i].ne) if (!dep[y = e[i].ver])
            {
                dep[y] = dep[x] + 1, f[y][0] = x, mn[y][0] = e[i].w;
                q.push(y);
            }
        }
        for (int j = 1; j < D; ++j)
            for (int i = 1; i <= n; ++i)
            {
                mn[i][j] = std::min(mn[i][j - 1], mn[f[i][j - 1]][j - 1]);
                f[i][j] = f[f[i][j - 1]][j - 1];
            }
    }
    void work()
    {
        for (int i = 1; i <= n; ++i) nd[i] = i;
        shuffle(nd + 1, nd + 1 + n, rud); //随机化
        build(1, n), bfs();
    }
    int ask(int x, int y)
    {
        int res = INF;
        if (dep[x] > dep[y]) std::swap(x, y);
        for (int i = D - 1; i >= 0; --i) if (dep[f[y][i]] >= dep[x]) res = std::min(res, mn[y][i]), y = f[y][i];
        if (x == y) return res == INF ? -1 : res;
        for (int i = D - 1; i >= 0; --i) if (f[x][i] != f[y][i])
        {
            res = std::min(res, std::min(mn[x][i], mn[y][i]));
            x = f[x][i], y = f[y][i];
        }
        res = std::min(res, std::min(mn[x][0], mn[y][0]));
        return res == INF ? -1 : res;
    }
}

多项式

拉格朗日插值

一般

void init()
{
    for (int i = 1, t; i <= n; ++i)
    {
        la[i] = 1;
        for (int j = 1; j <= n; ++j) if (j != i)
        {
            adj(t = a[i].fi - a[j].fi);
            la[i] = LL(t) * la[i] % P;
        }
        la[i] = qpow(la[i]);
    }   
}
int lag(int x)
{
    int res = 0;
    for (int i = 1, t, tt; i <= n; ++i)
    {
        tt = la[i];
        for (int j = 1; j <= n; ++j) if (j != i)
        {
            adj(t = x - a[j].fi);
            tt = LL(t) * tt % P;
        }
        adj(res += LL(tt) * a[i].se % P - P);
    }
    return res;
}

线性

void init(int n)
{
    int fac = 1, fi = 0;
    ifac[0] = ifac[1] = 1;
    for (int i = 2; i <= n; ++i) fac = LL(fac) * i % P;
    ifac[n] = qpow(fac);
    for (int i = n - 1; i > 1; --i) ifac[i] = LL(i + 1) * ifac[i + 1] % P;
    for (int i = 1; i <= n; ++i)
    {
        adj(fi += qpow(i, k) - P);
        la[i] = LL(fi) * ifac[i - 1] % P * ifac[n - i] % P;
        if ((n - i) & 1) la[i] = P - la[i];
    }
}
int lag(int x, int n)
{
    int res = 0;
    for (int i = 1, t = 1; i <= n; ++i)
    {
        la2[i] = t;
        adj(t = LL(x - i) * t % P);    
    }
    for (int i = n, t = 1; i; --i)
    {
        la2[i] = LL(t) * la2[i] % P;
        adj(t = LL(x - i) * t % P);    
    }
    for (int i = 1; i <= n; ++i) adj(res += LL(la2[i]) * la[i] % P - P); 
    return res;
}

FFT

const int N = 3000000 + 5; //注意N要大于二倍n
const DB PI = acos(-1);
struct Complex //定义复数
{ 
	DB a, b;
	Complex make_C(const DB _a, const DB _b) const
	{
		Complex res;
		res.a = _a, res.b = _b;
		return res;
	}
	Complex operator+(const Complex &_t) const { return make_C(a + _t.a, b + _t.b); }
	Complex operator-(const Complex &_t) const { return make_C(a - _t.a, b - _t.b); }
	Complex operator*(const Complex &_t) const { return make_C(a * _t.a - b * _t.b, a * _t.b + b * _t.a); }
} a[N], b[N];
int r[N], bit, tot;
void fft(Complex x[], int inv)
{
	for (int i = 0; i < tot; ++i) if (i < r[i]) std::swap(x[i], x[r[i]]);
	Complex w1, wk, a1, a2;
	for (int mid = 1; mid < tot; mid <<= 1)
	{
		w1 = w1.make_C(cos(PI / mid), inv * sin(PI / mid)); //由于cos正负相同,不必乘inv
		for (int i = 0; i < tot; i += (mid << 1))
		{
			wk = wk.make_C(1, 0);
			for (int j = 0; j < mid; ++j, wk = wk * w1)
			{
				a1 = x[i + j], a2 = wk * x[i + j + mid];
				x[i + j] = a1 + a2, x[i + j + mid] = a1 - a2;
			}
		}
	}
}
while ((1 << bit) < n + m + 1) ++bit;
tot = 1 << bit;
for (int i = 0; i < tot; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (bit - 1));

NTT + 全家桶

超长警告

const int P = 998244353, I = 86583718, G = 3; //模数,二次剩余,原根
namespace Poly
{
    namespace Cipolla
    {
        int w;
		std::mt19937 rud(114514);
        struct Complex
        {
            int x, y;
            Complex operator * (const Complex t) const
            {
                return (Complex){((LL)x * t.x % P + (LL)y * t.y % P * w % P) % P, ((LL)x * t.y % P + (LL)y * t.x % P) % P};
            }
        } ;
        Complex Cqpow(Complex x, int y)
        {
            Complex res = (Complex){1, 0};
			for (; y; y >>= 1, x = x * x) if (y & 1) res = res * x;
            return res;
        }
        int Csqrt(int x)
        {
            if(qpow(x, (P - 1) >> 1) == P - 1) return -1;
            int t;
            while (true)
            {
                t = rud();
                w = ((LL)t * t % P - x + P) % P;
                if (qpow(w, (P - 1) >> 1) == P - 1) break;
            }
            int res = Cqpow((Complex){t, 1}, (P + 1) >> 1).x;
            return min(res, P - res);
        }
    }
    int r[N];
    void fill(int x[], int y, int l, int r){ for (int i = l; i < r; ++i) x[i] = y; }
    void fill(int x[], int y[], int l, int r){ for (int i = l; i < r; ++i) x[i] = y[i]; }
    void ready(int &bit, int &tot, int len){ for (tot = 1, bit = 0; tot < (len << 1); ) tot <<= 1, ++bit; }
    void get_r(int bit, int tot){ for (int i = 0; i < tot; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (bit - 1)); }
    void ntt(int *x, int tot, int op)
    {
        static int gn[N];
        for (int i = 1; i < tot; ++i) if (i < r[i]) std::swap(x[i], x[r[i]]);
        for (int mid = 1; mid < tot; mid <<= 1)
        {
            int g0 = qpow(G, (P - 1) / (mid << 1));
            if (op == -1) g0 = qpow(g0);
            gn[0] = 1;
            for (int i = 1; i < mid; ++i) gn[i] = LL(gn[i - 1]) * g0 % P;
            for (int i = 0; i < tot; i += (mid << 1))
                for (int *x1 = x + i, *x2 = x1 + mid, *ed = x2, *g = gn; x1 != ed; ++x1, ++x2, ++g)
                {
                    int p = *x1, q = LL(*x2) * *g % P;
                    adj(*x1 = p + q - P), adj(*x2 = p - q);
                }
        }
        if (op == 1) return ;
        int t = qpow(tot, P - 2);
        for (int i = 0; i < tot; ++i) x[i] = LL(x[i]) * t % P;
    }
    void polymul(int x[], int y[], int len)
    {
        int bit, tot;
        ready(bit, tot, len);
        get_r(bit, tot);
        ntt(x, tot, 1), ntt(y, tot, 1);
        for (int i = 0; i < tot; ++i) x[i] = (LL)x[i] * y[i] % P;
        ntt(x, tot, -1);
        //记得把x中不用的清0
    }
    void polyinv(int x[], int y[], int len) //求逆,y记录答案
    {
        if (len == 1) return void(y[0] = qpow(x[0], P - 2));
        polyinv(x, y, (len + 1) >> 1);
        int bit = 0, tot = 1;
        STC int t[N];
        ready(bit, tot, len);
        get_r(bit, tot);
        fill(y, 0, (len + 1) >> 1, tot);
        fill(t, x, 0, len);
        fill(t, 0, len, tot);
        ntt(t, tot, 1), ntt(y, tot, 1);
        for (int i = 0; i < tot; ++i) y[i] = (2 - (LL)t[i] * y[i] % P + P) % P * y[i] % P;
        ntt(y, tot, -1);
        fill(y, 0, len, tot);
    }
    void polydiv(int x[], int n, int y[], int m, int a[], int b[]) //x除以y商a余b
    {
        STC int ta[N], tb[N];
        int dt = n - m + 1, tot, bit;
        ready(bit, tot, n);
        fill(ta, 0, 0, tot);
        fill(tb, 0, 0, tot);
        for (int i = 0; i < m; ++i) ta[i] = y[m - i - 1];
        polyinv(ta, tb, dt);
        get_r(bit, tot);
        for (int i = 0; i < n; ++i) ta[i] = x[n - i - 1];
        ntt(ta, tot, 1), ntt(tb, tot, 1);
        for (int i = 0; i < tot; ++i) ta[i] = (LL)ta[i] * tb[i] %P;
        ntt(ta, tot, -1);
        for (int i = 0; i < dt; ++i) a[i] = ta[dt - i - 1];
        fill(ta, 0, 0, tot);
        fill(tb, 0, 0, tot);
        fill(ta, a, 0, dt);
        fill(tb, y, 0, m);
        ntt(ta, tot, 1), ntt(tb, tot, 1);
        for (int i = 0; i < tot; ++i) ta[i] = (LL)ta[i] * tb[i] % P;
        ntt(ta, tot, -1);
        for (int i = 0; i < m - 1; ++i) b[i] = (x[i] - ta[i] + P) % P;
    }
    void polydif(int x[], int y[], int len) //求导,y记录答案
    {
        for (int i = 1; i < len; ++i) y[i - 1] = (LL)x[i] * i % P;
        y[len - 1] = 0;
    }
    void polyint(int x[], int y[], int len) //积分,y记录答案
    {
        for (int i = 1; i < len; ++i) y[i] = (LL)x[i - 1] * qpow(i, P - 2) % P;
        y[0] = 0;
    }
    void polyln(int x[], int y[], int len)
    {
        STC int a[N], b[N];
        polydif(x, a, len);
        polyinv(x, b, len);
        int bit, tot;
        ready(bit, tot, len);
        get_r(bit,tot);
        fill(a, 0, len, tot);
        fill(b, 0, len, tot);
        ntt(a, tot, 1), ntt(b, tot, 1);
        for (int i = 0; i < tot; ++i) a[i] = (LL)a[i] * b[i] % P;
        ntt(a, tot, -1);
        fill(a, 0, len, tot);
        polyint(a, y, len);
        fill(y, 0, len, tot);
    }
    void polyexp(int x[], int y[], int len)
    {
        if (len == 1) return void(y[0] = 1);
        polyexp(x, y, (len + 1) >> 1);
        int bit, tot;
        STC int t[N];
        ready(bit, tot, len);
        fill(t, 0, 0, tot);
        polyln(y, t, len);
        get_r(bit, tot);
        t[0] = (x[0] + 1 - t[0] + P) % P;
        for (int i = 1; i < len; ++i) t[i] = (x[i] - t[i] + P) % P;
        fill(t, 0, len, tot);
        ntt(t, tot, 1), ntt(y, tot, 1);
        for (int i = 0; i < tot; ++i) y[i] = (LL)y[i] * t[i] % P;
        ntt(y, tot, -1);
        fill(y, 0, len, tot);
    }
    /*
	k1是真实指数(可以是模后的)
	k2是真实指数模P - 1(欧拉定理)
	k3用于确定前导0个数
    */
    void polypow(int x[], int y[], int k1, int k2, int k3, int len)
    {
        int num = 0;
        while (!x[num] && num < len) ++num;
        if ((LL)num * k3 >= len) return fill(y, 0, 0, len);
        STC int t[N];
        int x0 = x[num], inv = qpow(x0, P - 2);
        len -= num;
        for (int i = 0; i < len; ++i) x[i] = (LL)x[i + num] * inv % P;
        int bit, tot;
        ready(bit, tot, len);
        fill(t, 0, 0, tot);
        fill(x, 0, len, tot);
        polyln(x, t, len);
        for (int i = 0; i < len; ++i) t[i] = (LL)t[i] * k1 % P;
        fill(t, 0, len, tot);
        polyexp(t, y, len);
        len += num;
        x0 = qpow(x0, k2);
        num = num * k3;
        for (int i = len - 1; i >= num; --i) y[i] = (LL)y[i - num] * x0 % P;
        fill(y, 0, 0, num);
    }
    void ready_for_pow(char *k, int &k1, int &k2, int &k3) //k太大,计算k1,k2,k3
    {
        k1 = k2 = k3 = 0;
        for (int i = 1, l = strlen(k + 1); i <= l; ++i)
        {
            k1 = ((LL)k1 * 10 + (k[i] ^ 48)) % P;
            k2 = ((LL)k2 * 10 + (k[i] ^ 48)) % (P - 1);
            if ((LL)k3 * 10 + (k[i] ^ 48) <= P) k3 = (LL)k3 * 10 + (k[i] ^ 48);
        }
    }
    void polysqrt(int x[], int y[], int len)
    {
        int sq = Cipolla::Csqrt(x[0]), inv = qpow(x[0], P - 2);
        for (int i = 0; i < len; ++i) x[i] = (LL)x[i] * inv % P;
        polypow(x, y, (P + 1) >> 1, (P + 1) >> 1, 1, len);
        for (int i = 0; i < len; ++i) y[i] = (LL)y[i] * sq % P;
    }
    void polysin(int x[], int y[], int len)
    {
        STC int a[N], b[N], c[N];
        for (int i = 0; i < len; ++i) a[i] = (LL)x[i] * I % P;
        polyexp(a, b, len);
        polyinv(b, c, len);
        for (int i = 0; i < len; ++i) b[i] = (b[i] - c[i] + P) % P;
        int inv = qpow((I << 1) % P, P - 2);
        for (int i = 0; i < len; ++i) y[i] = (LL)b[i] * inv % P;
    }
    void polycos(int x[], int y[], int len)
    {
        STC int a[N], b[N], c[N];
        for (int i = 0; i < len; ++i) a[i] = (LL)x[i] * I % P;
        polyexp(a, b, len);
        polyinv(b, c, len);
        for (int i = 0; i < len; ++i) b[i] = (b[i] + c[i]) % P;
        int inv = qpow(2, P - 2);
        for (int i = 0; i < len; ++i) y[i] = (LL)b[i] * inv % P;
    }
    void polytan(int x[], int y[], int len)
    {
        STC int a[N], b[N], c[N];
        polysin(x, a, len);
        polycos(x, b, len);
        polyinv(b, c, len);
        for (int i = 0; i < len; ++i) y[i] = a[i] * c[i] % P;
    }
    void polyasin(int x[], int y[], int len)
    {
        STC int a[N], b[N], c[N];
        polydif(x, a, len);
        int bit, tot;
        ready(bit, tot, len);
        get_r(bit, tot);
        ntt(x, tot, 1);
        for (int i = 0; i < tot; ++i) b[i] = (1 - (LL)x[i] * x[i]% P + P) % P;
        ntt(b, tot, -1);
        fill(b, 0, len, tot);
        polysqrt(b, c, len);
        fill(b, 0, 0, tot);
        polyinv(c, b, len);
        ntt(a, tot, 1), ntt(b, tot, 1);
        for (int i = 0; i < tot; ++i) a[i] = (LL)a[i] * b[i] % P;
        ntt(a, tot, -1);
        polyint(a, y, len);
    }
    void polyacos(int x[], int y[], int len)
    {
        polyasin(x, y, len);
        for (int i = 0; i < len; ++i) y[i] = y[i] ? P - y[i] : 0;
    }
    void polyatan(int x[], int y[], int len)
    {
        STC int a[N], b[N], c[N];
        polydif(x, a, len);
        int bit, tot;
        ready(bit, tot, len);
        get_r(bit, tot);
        ntt(x, tot, 1);
        for (int i = 0; i < tot; ++i) b[i] = (1 + (LL)x[i] * x[i]% P) % P;
        ntt(b, tot, -1);
        fill(b, 0, len, tot);
        polyinv(b, c, len);
        ntt(a, tot, 1), ntt(c, tot, 1);
        for (int i = 0; i < tot; ++i) a[i] = (LL)a[i] * c[i] % P;
        ntt(a, tot, -1);
        polyint(a, y, len);
    }
}

upd 2022/7/23 想改成 std::vector 写发，先放一个 exp 其它后面补

namespace Poly
{
    int r[N], iv[N];
    void rdy(int &bit, int &tot, int len){ for (bit = 0, tot =1; tot < len + 1; tot <<= 1, ++bit); }
    void get_r(int bit, int tot){ for (int i = 1; i < tot; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (bit - 1)); }
    void ntt(int *x, int tot, int op)
    {
        static int gn[N];
        for (int i = 1; i < tot; ++i) if (i < r[i]) std::swap(x[i], x[r[i]]);
        for (int mid = 1; mid < tot; mid <<= 1)
        {
            int g0 = qpow(G, (P - 1) / (mid << 1));
            if (op == -1) g0 = qpow(g0);
            gn[0] = 1;
            for (int i = 1; i < mid; ++i) gn[i] = LL(gn[i - 1]) * g0 % P;
            for (int i = 0; i < tot; i += (mid << 1))
                for (int *x1 = x + i, *x2 = x + i + mid, *ed = x2, *g = gn; x1 != ed; ++x1, ++x2, ++g)
                {
                    int p = *x1, q = LL(*x2) * *g % P;
                    adj(*x1 = p + q - P), adj(*x2 = p - q);
                }
        }
        if (op == 1) return ;
        int t = qpow(tot);
        for (int i = 0; i < tot; ++i) x[i] = LL(x[i]) * t % P;
    }
    poly operator * (poly x, poly y)
    {
        if (x.empty() || y.empty()) return {};
        int n = x.size(), m = y.size(), bit, tot;
        rdy(bit, tot, n + m), get_r(bit, tot);
        x.resize(tot), y.resize(tot);
        if (x != y) ntt(x.data(), tot, 1), ntt(y.data(), tot, 1);
        else ntt(x.data(), tot, 1), y = x;
        for (int i = 0; i < tot; ++i) x[i] = LL(x[i]) * y[i] % P;
        ntt(x.data(), tot, -1), x.resize(n + m - 1);
        return x;
    }
    poly operator - (poly x, poly y)
    {
        if (x.size() < y.size()) x.resize(y.size());
        for (int i = y.size() - 1; ~i; --i) adj(x[i] -= y[i]);
        return x;
    }
    poly inv(poly x)
    {
        int n = x.size();
        if (n == 1) return {qpow(x[0])};
        int bit, tot;
        rdy(bit, tot, n << 1);
        poly y = inv(poly(x.begin(), x.begin() + ((n + 1) >> 1))), z = y * y * x, res(n);
        y.resize(n), z.resize(n);
        for (int i = 0; i < n; ++i) adj(res[i] = 2ll * y[i] - z[i]);
        return res;
    }
    poly dif(poly x)
    {
        poly res(x.size() - 1);
        for (int i = x.size() - 1; i; --i) res[i - 1] = LL(i) * x[i] % P;
        return res;
    }
    poly inte(poly x)
    {
        poly res(x.size() + 1);
        if (!iv[1])
        {
            iv[1] = 1;
            for (int i = 2; i < N; ++i) iv[i] = LL(P - P / i) * iv[P % i] % P;
        }
        for (int i = x.size(); i; --i) res[i] = LL(x[i - 1]) * iv[i] % P;
        return res;
    }
    poly ln(poly x)
    {
        poly res(dif(x) * inv(x));
        res.resize(x.size()), res = inte(res);
        return res.resize(x.size()), res;
    }
    poly exp(poly x)
    {
        if (x.size() == 1) return {1};
        int n = x.size();
        poly y = exp(poly(x.begin(), x.begin() + ((n + 1) >> 1)));
        y.resize(n);
        poly z = ln(y);
        x = x - z, ++x[0];
        return x = x * y, x.resize(n), x;
    }
}

MTT

#include <bits/stdc++.h>
#define STC static
using LL = long long;
using DB = double;
using CP = std::complex<double>;
const int N = 1e5 + 100;
const CP I(0, 1);
int tot, bit, r[N << 2], P, M;
void fft(CP *x, int op)
{
    STC CP wn[N << 2];
    int i, mid;
    CP *x1, *x2, *ed, *w;
    for (i = 1; i < tot; ++i) if (i < r[i]) std::swap(x[i], x[r[i]]);
    for (mid = 1; mid < tot; mid <<= 1)
    {
        CP w0(std::cos(M_PI / mid), std::sin(M_PI / mid * op));
        wn[0] = {1, 0};
        for (i = mid - 2; i >= 0; i -= 2) wn[i + 1] = (wn[i] = wn[i >> 1]) * w0; //这里不能写~i
        for (i = 0; i < tot; i += (mid << 1))
            for (x1 = x + i, x2 = x1 + mid, ed = x2, w = wn; x1 != ed; ++x1, ++x2, ++w)
            {
                CP p = *x1, q = *x2 * *w;
                *x1 = p + q, *x2 = p - q;
            }
    }
    if (op == 1) return ;
    DB t = DB(1) / tot;
    for (i = 0; i < tot; ++i) x[i] = x[i] * t;
}
void dfft(CP *x, CP *y)
{
    int i;
    for (i = 0; i < tot; ++i) x[i] = x[i] + I * y[i];
    fft(x, 1);
    for (i = 0; i < tot; ++i) y[i] = std::conj(x[i ? tot - i : 0]);
    for (i = 0; i < tot; ++i)
    {
        CP p = x[i], q = y[i];
        x[i] = (p + q) * DB(0.5);
        y[i] = (q - p) * DB(0.5) * I;
    }
}
LL rod(CP x)
{
    DB t = x.real();
    return t < 0 ? LL(t - 0.5) % P : LL(t + 0.5) % P;
}
void polymul(int *f, int *g, int lf, int lg)
{
    STC CP p[N << 2], q[N << 2], f0[N << 2], f1[N << 2], g0[N << 2], g1[N << 2];
    int i;
    tot = 1, bit = 0;
    while (tot < lf + lg + 1) tot <<= 1, ++bit;
    for (i = 1; i < tot; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (bit - 1));
    for (i = 0; i <= lf; ++i) f0[i] = f[i] / M, f1[i] = f[i] % M;
    for (i = 0; i <= lg; ++i) g0[i] = g[i] / M, g1[i] = g[i] % M;
    dfft(f0, f1), dfft(g0, g1);
    for (i = 0; i < tot; ++i)
    {
        p[i] = f0[i] * g0[i] + I * f1[i] * g0[i];
        q[i] = f0[i] * g1[i] + I * f1[i] * g1[i];
    }
    fft(p, -1), fft(q, -1);
    for (i = lf + lg; ~i; --i) f[i] = (M * M * rod(p[i].real()) % P + M * (rod(p[i].imag()) + rod(q[i].real())) % P + rod(q[i].imag())) % P;
}
int f[N << 2], g[N << 2], n, m;
int main()
{
    scanf("%d %d %d", &n, &m, &P);
    M = std::sqrt(P) + 1;
    for (int i = 0; i <= n; ++i) scanf("%d", &f[i]), f[i] %= P;
    for (int i = 0; i <= m; ++i) scanf("%d", &g[i]), g[i] %= P;
    polymul(f, g, n, m);
    for (int i = 0; i <= n + m; ++i) printf("%d ", f[i]);
    puts("");
    return 0;
}

计算几何

浮点数比较

int cmp(DB x, DB y)
{
    if (fabs(x - y) < eps) return 0;
    return x > y ? 1 : -1;
}

平面最近点对

struct Point
{
    LDB p[4];
    bool operator < (const Point &t) const { return p[0] * p[1] < t.p[0] * t.p[1]; }
} p[N];
std::mt19937 rud(114514);
LDB th = rud(), ans = INF;
LDB z = sin(th), w = cos(th);
LDB a, b, c, d;
for (int i = 1; i <= n; ++i)
{
    scanf("%Lf %Lf", &a, &b);
    p[i] = {a * w + b * z, -a * z + b * w, a, b};
}
stable_sort(p + 1, p + 1 + n); //stable是稳定排序
for (int i = 1; i <= n; ++i)
{
    a = p[i].p[2], b = p[i].p[3];
    for (int j = 1; j <= K && i + j <= n; ++j)
    {
        c = p[i + j].p[2], d = p[i + j].p[3];
        ans = min(ans, (a - c) * (a - c) + (b - d) * (b - d));
    }
}

点间距离

DB dist(Point x, Point y)
{
    Point t = x - y;
    return sqrt(t.x * t.x + t.y * t.y);
}

向量

用点表示：

struct Point
{
	DB x, y;
	Point operator + (Point t){ return (Point){x + t.x, y + t.y}; }
	Point operator - (Point t){ return (Point){x - t.x, y - t.y}; }
	Point operator * (DB t){ return (Point){x * t, y * t}; }
	DB operator & (Point t){ return x * t.x + y * t.y; } //点乘
	DB operator * (Point t){ return x * t.y - y * t.x; } //叉乘
}
DB mo(Point x){ return std::sqrt(x & x); } //模长
DB angle(Point x, Point y){ return acos((x & y) / mo(x) / mo(y)); } //计算向量夹角
Point rot(Point x, DB theta) //向量(点)顺时针旋转角度
{
	return {x.x * cos(theta) + x.y * sin(theta), -x.x * sin(theta) + x.y * cos(theta)};
}
DB area(Point x, Point y, Point z){ return (y - x) * (z - x); } //计算XY,XZ围成平行四边形面积

点与线

点到直线距离：

DB dis_z(Point p, Point x, Point y) //p到直线(x->y)的距离
{
    Point u = y - x, v = p - x;
    return fabs((u * v) / mo(u));
}

点到线段距离：

DB dis_x(Point p, Point x, Point y)
{
    if (x == y) return mo(p - x);
    Point u = y - x, v = p - x, w = p - y;
    if (cmp(u & v, 0) < 0) return mo(v);
    if (cmp(u & w, 0) > 0) return mo(w);
    return dis_z(p, x, y);
}

点在直线上的投影：

DB proj(Point p, Point x, Point y)
{
    Point u = y - x;
    return x + u * (u & (p - x)) / (u & u));
}

点是否在直线上：

bool is_on(Point p, Point x, Point y)
{
    return !cmp((p - x) * (p - y), 0) && cmp((p - x) & (p - y), 0) <= 0;
}

线与线

直线交点：

注意点向式表达直线： $p = p_{0} + t \vec{v}$

Point jiao(Point p, Point u, Point q, Point v) //点项式
{
    if (u * v == 0) return {INF, INF}; //平行或者重合
    DB t = (p - q) * v / (u * v);
    return p + u * t;
}

判断线段是否相交：

bool is_jiao(Point x_1, Point y_1, Point x_2, Point y_2)
{
    double c1 = cross(y_1 - x_1, x_2 - x_1), c2 = cross(y_1 - x_1, y_2 - x_1);
    double c3 = cross(y_2 - x_2, y_1 - x_2), c4 = cross(y_2 - x_2, x_1 - x_2);
    return cmp(c1, 0) * cmp(c2, 0) <= 0 && cmp(c3, 0) * cmp(c4, 0) <= 0;
}

多边形

按逆时针存储所有点

面积：

DB pgarea(Point p[], int n) //polygon area
{
    DB res = 0;
    for (int i = 1; i < n - 1; ++i) res += (p[i] - p[0]) * (p[i + 1] - p[0]); // //这里点编号为0~n-1
    return res / 2;
}

判断点是否在多边形内：

射线法，从该点任意做一条和所有边都不平行的射线，交点个数为偶数，则在多边形外，为奇数，则在多边形内

最小圆覆盖

std::mt19937 rud(114514);
struct Circle{ Point p; DB r; } ;
PR<Point, Point> get_line(Point x, Point y) { return {(x + y) / 2, rotate(y - x, PI / 2)}; } //找中垂线
Circle get_c(Point x, Point y, Point z)
{
    auto u = get_line(x, y), v = get_line(x, z);
    auto p = jiao(u.first, u.second, v.first, v.second);
    return {p, dist(p, x)};
}
void work(Point p[], int n)
{
	std::shuffle(q, q + n, rud);
    Circle c({q[0], 0});
    for (int i = 1; i < n; ++i) if (cmp(c.r, dist(c.p, q[i])) < 0)
    {
        c = {q[i], 0};
        for (int j = 0; j < i; ++j) if (cmp(c.r, dist(c.p, q[j])) < 0)
        {
            c = {(q[i] + q[j]) / 2, dist(q[i], q[j]) / 2};
            for (int k = 0; k < j; ++k) if (cmp(c.r, dist(c.p, q[k])) < 0) c = get_c(q[i], q[j], q[k]);
        }
    }
}

凸包

DB andrew(Point x[])
{
    STC int stk[N];
    STC bool used[N];
    std::sort(x, x + n);
    int top = 0;
    for (int i = 0, t; i < n; ++i)
    {
        while (top >= 2 && area(x[stk[top - 1]], x[stk[top]], x[i]) <= 0)
        {
            // 凸包边界上的点即使被从栈中删掉，也不能删掉used上的标记
            if (!area(x[stk[top - 1]], x[stk[top]], x[i])) --top;
            else used[stk[top--]] = false;
        }
        stk[++top] = i;
        used[i] = true;
    }
    used[0] = false;
    for (int i = n - 1; i >= 0; --i)
    {
        if (used[i]) continue;
        //为了应对所有点共线的情况,这里不能取<=
        while (top >= 2 && area(x[stk[top - 1]], x[stk[top]], x[i]) < 0) --top;
        stk[++top] = i;
    }
    DB res = 0;
    for (int i = 2; i <= top; ++i) res += dist(x[stk[i - 1]], x[stk[i]]);
    return res;
}

该函数也叫 convex(int x[], int n)

半平面交

struct Line
{
	Point st, ed;
	DB angle(){ return atan2(ed.y - st.y, ed.x - st.x); }
} ;
Point jiao(Line x, Line y){ return jiao(x.st, x.ed - x.st, y.st, y.ed - y.st); }
bool on_r(Line &x, Line y, Line z)
{
	Point o = jiao(y, z);
	return cmp(area(x.st, x.ed, o), 0) <= 0; //这里取不取等依题意
}
DB halfp(Line x[], int len)
{
	sort(x, x + len);
	int hh = 0, tt = -1;
	STC int q[N];
	for (int i = 0; i < len; ++i)
	{
		if (i && !cmp(x[i].angle(), x[i - 1].angle())) continue;
		while (hh < tt && on_r(x[i], x[q[tt - 1]], x[q[tt]])) --tt;
		while (hh < tt && on_r(x[i], x[q[hh + 1]], x[q[hh]])) ++hh;
		q[++tt] = i;
	}
	while (hh < tt && on_r(x[q[hh]], x[q[tt - 1]], x[q[tt]])) --tt;
	while (hh < tt && on_r(x[q[tt]], x[q[hh + 1]], x[q[hh]])) ++hh;
	q[++tt] = q[hh];
	int k = 0;
    for (int i = hh; i < tt; ++i) ans[k++] = jiao(x[q[i]], x[q[i + 1]]);
   	DB res = 0;
    for (int i = 1; i + 1 < k; ++i) res += area(ans[0], ans[i], ans[i + 1]);
    return res / 2;
}

旋转卡壳

DB rot_cal(Point x[], int len)
{
    convex(x, len);
    if (top <= 2) return dist(x[0], x[len - 1]);
    DB res = 0;
    for (int i = 0, j = 2; i < top; ++i)
    {
        auto d = x[stk[i]], e = x[stk[i + 1]];
        while (area(d, e, x[stk[j]]) < area(d, e, x[stk[j + 1]])) j = (j + 1) % top;
        res = max(res, max(dist(d, x[stk[j]]), dist(e, x[stk[j]])));
    }
    return res;
}

数论

快速幂

int qpow(int x, int y)
{
    int res = 1;
    for (; y; y >>= 1, x = LL(x) * x % P) if (y & 1) res = LL(res) * x % P;
    return res;
}

光速幂

const int BL = (1 << 16) + 5, B = sqrt(P);
int qp[BL][2], ph;
int phi(int x)
{
    int res = x;
    for (int i = 2; i * i <= x; i++)
    {
        if (x % i == 0) res = res / i * (i - 1);
        while (x % i == 0) x /= i;
    }
    if (x > 1) res = res / x * (x - 1);
    return res;
}
void init(int x)
{
    ph = phi(P);
    qp[0][0] = qp[0][1] = 1;
    for (int i = 1; i <= B; ++i) qp[i][0] = qp[i - 1][0] * x % P;
    for (int i = 1; i <= B; ++i) qp[i][1] = qp[i - 1][1] * qp[B][0] % P;
}
int qqpow(int y)
{
    y %= ph;
    return qp[y % B][0] * qp[y / B][1] % P;
}

龟速乘

LL mul(LL x, LL y, LL p)
{
	LL res = 0;
	for (; y; y >>= 1, x = (x + x) % P) if (y & 1) res = (res + x) % P;
	return res;
}

线性筛

质数：

for (int i = 2; i <= n; ++i)
{
	if (!vis[i]) pri[++cnt] = i;
	for (int j = 1; j <= cnt && LL(pri[j]) * i <= n; ++j)
	{
		vis[pri[j] * i] = true;
		if (i % pri[j] == 0) break;
	}
}

莫比乌斯函数：

mu[1] = 1; // 1特判
for (int i = 2; i <= n; ++i)
{
	if (!vis[i]) pri[++cnt] = i, mu[i] = -1; //质数
	for (int j = 1; j <= cnt && LL(pri[j]) * i <= n; ++j)
	{
		vis[pri[j] * i] = true;
		if (i % pri[j] == 0) //若有一个质因数指数大于1
		{ 
			mu[i * pri[j]] = 0;
			break;
		}
		mu[i * pri[j]] = -mu[i];
	}
}

欧拉函数：

phi[1] = 1;
for (int i = 2; i <= n; ++i)
{
	if (!vis[i]) pri[++cnt] = i, phi[i] = i - 1;
	for (int j = 1; j <= cnt && LL(pri[j]) * i <= n; ++j)
	{
		vis[pri[j] * i] = true;
		if (i % pri[j] == 0)
		{
			phi[i * pri[j]] = phi[i] * pri[j];
			break;
		}
		phi[i * pri[j]] = phi[i] * (pri[j] - 1);
	}
}

其它

pri[1] = low[1] = 1;
f[1] = 对1直接定义;
for (int i = 2; i <= n; ++i)
{
    if (!pri[i]) low[i] = pri[++cnt] = i, f[i] = 对质数直接定义;
    for (int j = 1; j <= cnt && LL(i) * pri[j] <= n; ++j)
    {
        pri[i * pri[j]] = 1;
        if (i % pri[j] == 0)
        {
            low[i * pri[j]] = low[i] * pri[j];
            if (low[i] ^ i) f[i * pri[j]] = f[i / low[i]] * f[low[i] * pri[j]];
            else f[i * pri[j]] = 对质数的若干次幂进行定义(一般由f[i]递推);
            break;
        }
        low[i * pri[j]] = pri[j];
        f[i * pri[j]] = f[i] * f[pri[j]];
    }
}

杜教筛

式子： $g (1) S (n) = \sum_{i = 1}^{n} (f * g) (i) - \sum_{d = 2}^{n} g (d) S (⌊ \frac{n}{d} ⌋)$

其中 $S$ 是 $f$ 的前缀和，也就是目标，直接筛复杂度 $O (n^{\frac{3}{4}})$ ，预处理 $n^{\frac{2}{3}}$ 个可以降为 $O (n^{\frac{2}{3}})$

#include <bits/stdc++.h>
using LL = long long;
const int NN = 1664510;
LL phi[NN];
int mu[NN], pri[NN], ct;
std::map<int, LL> Phi;
std::map<int, int> Mu;
bool vis[NN];
void prev()
{
    mu[1] = phi[1] = 1;
    for (int i = 2; i < NN; ++i)
    {
        if (!vis[i]) pri[++ct] = i, mu[i] = -1, phi[i] = i - 1;
        for (int j = 1; j <= ct && LL(i) * pri[j] < NN; ++j)
        {
            vis[i * pri[j]] = true;
            if (i % pri[j] == 0)
            {
                mu[i * pri[j]] = 0;
                phi[i * pri[j]] = phi[i] * pri[j]; 
                break;
            }
            mu[i * pri[j]] = -mu[i];
            phi[i * pri[j]] = phi[i] * (pri[j] - 1);
        }
    }
    for (int i = 2; i < NN; ++i) mu[i] += mu[i - 1], phi[i] += phi[i - 1];
}
LL calphi(int x)
{
    if (x < NN) return phi[x];
    if (Phi.find(x) != Phi.end()) return Phi[x];
    LL res = (LL(x) + 1) * x / 2;
    for (LL l = 2, r; l <= x; l = r + 1)
    {
        r = x / (x / l);
        res -= calphi(x / l) * (r - l + 1);
    }
    return Phi[x] = res;
}
int calmu(int x)
{
    if (x < NN) return mu[x];
    if (Mu.find(x) != Mu.end()) return Mu[x];
    int res = 1;
    for (LL l = 2, r; l <= x; l = r + 1)
    {
        r = x / (x / l);
        res -= calmu(x / l) * (r - l + 1);
    }
    return Mu[x] = res;
}
int main()
{
    prev();
    int T, n;
    for (scanf("%d", &T); T--; printf("%lld %d\n", calphi(n), calmu(n))) scanf("%d", &n);
    return 0;
}

min 25 筛

$\begin{aligned} g (n, j) = \sum_{i = 2}^{n} f (i) [i \in p r i m e s \lor R (i) > p_{j}] \\ g (n, j) = {\begin{cases} g (n, j - 1) & p_{j}^{2} \geq n \\ g (n, j - 1) - f (p_{j}) * (g (\frac{n}{p_{j}}, j - 1) - \sum_{k = 1}^{j - 1} f (p_{k})) & o t h e r w i s e \end{cases} \\ S (n, j) = \sum_{i = 2}^{n} F (i) [R (i) \geq p_{j}] \\ S (n, j) = g (n, c n t) - \sum_{i = 1}^{j - 1} F (p_{i}) + \sum_{p_{k}}^{p_{k}^{2} \leq n} \sum_{e}^{p_{k}^{e + 1} \leq n} F (p_{k}^{e}) \times S (\frac{n}{p_{k}^{e}}, k + 1) + F (p_{k}^{e + 1}) \end{aligned}$

void prev(int n)
{
    for (int i = 2; i <= n; ++i)
    {
        if (!pri[i])
        {
            pri[++cnt] = i;
            sq1[cnt] = i;
            sq2[cnt] = LL(i) * i % P;    
        }
        for (int j = 1; j <= cnt && LL(i) * pri[j] <= n; ++j)
        {
            pri[i * pri[j]] = -1;
            if (i % pri[j] == 0) break;
        }
    }
    for (int i = 2; i <= n; ++i) adj(sq1[i] += sq1[i - 1] - P);
    for (int i = 2; i <= n; ++i) adj(sq2[i] += sq2[i - 1] - P);
}
int S(LL x, int j)
{
    if (x == 1 || pri[j] > x) return 0;
    int k = x <= sqt ? id[0][x] : id[1][n / x], res, t, t2;
    adj(res = g2[k] - g1[k]), adj(t = sq2[j - 1] - sq1[j - 1]);
    adj(res -= t);
    for (int i = j; i <= cnt && LL(pri[i]) * pri[i] <= x; ++i)
    {
        LL pe = pri[i], pe2 = LL(pri[i]) * pri[i];
        for (int e = 1; pe2 <= x; ++e, pe *= pri[i], pe2 *= pri[i])
        {
            t = pe % P, t2 = pe2 % P;
            t2 = t2 * LL(t2 - 1) % P, t = t * LL(t - 1) % P;
            t = LL(t) * S(x / pe, i + 1) % P;
            adj(t += t2 - P);
            adj(res += t - P);
        }
    }
    return res;
}
int min_25(LL n)
{
    for (LL l = 1, r; l <= n; l = r + 1)
    {
        r = n / (n / l);
        w[++tot] = n / l;
        g1[tot] = w[tot] % P;
        g2[tot] = g1[tot] * LL(g1[tot] + 1) / 2 % P * (g1[tot] * 2 + 1) % P * iv3 % P;
        g1[tot] = g1[tot] * LL(g1[tot] + 1) / 2 % P;
        adj(g1[tot] -= 1);
        adj(g2[tot] -= 1);
        if (w[tot] <= sqt) id[0][w[tot]] = tot;
        else id[1][r] = tot;
    }
    for (int i = 1; i <= cnt; ++i)
        for (int j = 1; j <= tot && LL(pri[i]) * pri[i] <= w[j]; ++j)
        {
            int k = w[j] / pri[i] <= sqt ? id[0][w[j] / pri[i]] : id[1][n / (w[j] / pri[i])], t;
            adj(t = g1[k] - sq1[i - 1]);
            adj(g1[j] -= LL(pri[i]) * t % P);
            adj(t = g2[k] - sq2[i - 1]);
            adj(g2[j] -= LL(pri[i]) * pri[i] % P * t % P);
        }
    int res = S(n, 1);
    adj(res += 1 - P);
    return res;
}

分解因数/质因数

根号暴力即可

数论分块

for (int l = 1, r; l <= n; l = r + 1)
{
	r = n / (n / l);
	[l, r]之间的数的(n/i)都相等
}

欧几里得算法

int gcd(int x, int y){ return y ? gcd(y, x % y) : x; }

拓展版：

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

BSGS

int bsgs(int a, int b, int p)
{
	if (1 % p == b % p) return 0;
	int k = sqrt(p) + 1;
	std::map<int, int> ha;
	for (int i = 0, j = b % p; i < k; ++i)
	{
		ha[j] = i;
		j = (LL)j * a % p;
	}
	int ak = 1;
	for (int i = 0; i < k; ++i) ak = (LL)ak * a % p;
	for (int i = 1, j = ak; i <= k; ++i)
	{
		if (ha.find(j) != ha.end()) return i * k - ha[j];
		j = (LL)j * ak % p;
	}
	return -INF;
}

拓展版：

int exbsgs(int a, int b, int p)
{
	b = (b % p + p) % p; //保证b为正数
	if (1 % p == b % p) return 0;
	int x, y;
	int d = exgcd(a, p, x, y);
	if (d > 1)
	{
		if (b % d) return -INF;
		exgcd(a / d, p / d, x, y);
		return exbsgs(a, (LL)b / d * x % (p / d), p / d) + 1; //注意加1 
	}
	return bsgs(a, b, p);
}

中国剩余定理

LL crt(int m[], int a[], int n)
{
	LL M = 1, res = 0, mt, x, y;
	for (int i = 1; i <= n; ++i) M *= m[i];
	for (int i = 1; i <= n; ++i)
	{
		mt = M / m[i];
		exgcd(mt, m[i], x, y);
		res += mt * a[i] * (x < 0 ? x + m[t] : x);
	}
	return res;
}

拓展：

LL excrt()
{
	LL x, y, k, M = m[1], res = a[1]; //第一个方程的解特判
	for (int i = 2; i <= n; i++)
	{
		LL a = M, b = m[i], c = (a[i] - res % b + b) % b; // ax = c (p b)
		LL d = exgcd(a, b, x, y), bg = b / d;
		if (c % d != 0) return -1; //判断是否无解
		x = mul(x, c / d, bg); //龟速乘
		res += x * M; //更新前k个方程组的答案
		M *= bg;	  // M为前k个m的lcm
		res = (res % M + M) % M;
	}
	return (res % M + M) % M;
}

逆元递推式

inv[1] = 1;
for (int i = 2; i <= n; ++i) inv[i] = -(P / i) * inv[P % i];

斐波拉契数列推导

$\begin{aligned} 设系数 r, s 使得 : \\ F (n) - r F (n - 1) = s [F (n - 1) - r F (n - 2)] \\ F (n) = (s + r) F (n - 1) - s r F (n - 2) \\ 那么有 : \\ r + s = 1, r s = - 1 \\ 再考虑这些式子 : \\ {\begin{cases} F (n) - r F (n - 1) = s [F (n - 1) - r F (n - 2)] \\ F (n - 1) - r F (n - 2) = s [F (n - 2) - r F (n - 3)] \\ \dots \\ F (3) - F (2) = s [F (2) - r F (1)] \end{cases} \\ 联立得 : \\ F (n) - r F (n - 1) = s^{n - 2} [F (2) - F (1)] \\ 又因为 : s = 1 - r, F (1) = F (2) = 1 \\ 有 : F (n) = s^{n - 1} + r F (n - 1) \\ F (n) = s^{n - 1} + r F (n - 1) \\ F (n) = s^{n - 1} + r s^{n - 2} + r^{2} F (n - 2) \\ \dots \\ F (n) = s^{n - 1} + r s^{n - 2} + r^{2} s^{n - 3} + \dots + r^{n - 2} s + r^{n - 1} \\ 等比数列求和得 : F (n) = \frac{s^{n - 1} - r^{n - 1} \frac{r}{s}}{1 - \frac{r}{s}} \\ F (n) = \frac{s^{n} - r^{n}}{s - r} \\ 再由 : r + s = 1, r s = - 1 得 : \\ {\begin{cases} s = \frac{1 + \sqrt{5}}{2} \\ r = \frac{1 - \sqrt{5}}{2} \end{cases} \\ 于是 F (n) = \frac{\sqrt{5}}{5} [(\frac{1 + \sqrt{5}}{2})^{n} - (\frac{1 - \sqrt{5}}{2})^{n}] \end{aligned}$

威尔逊定理

$(P - 1)! \equiv - 1 (\mod P)$

欧拉定理

$a^{b} \equiv a^{b \mod φ (P)} (\mod P)$

顺便还有欧拉函数的一个运用：
$[1 \sim n] 之间与 m 互质的数的个数为 A n s = \frac{n}{m} φ (m)$
再给出计算式： $φ (x) = x \prod \frac{p - 1}{p}, 其中 p 是 x 的质因数$

Miller-Rabin 素数测试

const int count = 10;
std::mt19937 rud(114514);
int exp(int a, int m, int n)
{
    if (!m) return 1;
    if (m == 1) return a % p;
    int w = exp(a, m / 2, p);
    w = LL(w) * w % p;
    if (m & 1) w = LL(w) * a % p;
    return w;
}
bool miller_rabin(int n)
{
    if (n == 2) return true;
    for (int i = 1; i <= count; ++i)
    {
        int a = rud() % (n - 2) + 2;
        if (exp(a, n, n) != a) return false;
    }
    return true;
}

调和级数求 $g c d == k$ 的个数

rt，设 $f [k]$ 表示 $g c d (i, j) == k$ 的个数， $g [k]$ 表示 $k ∣ g c d (i, j)$ 的个数，那么 $g [k] = f [k] + f [2 k] + \dots$ ，又有 $g [k] = ⌊ \frac{n}{k} ⌋^{2}$ ，那么 $f [k] = g [k] - (f [2 k] + f [3 k] + \dots)$ ，时间为 $O (n H (n))$ ，由于常数小比莫反略快，而且好打

for (int i = n; i; --i)
{
	f[i] = (n / i) * (n / i);
	for (int j = i << 1; j <= n; j += i) f[i] -= f[j];
}

组合计数

组合数计算

$A_{n}^{m} = \frac{n!}{(n - m)!}$

$C_{n}^{m} = (\binom{n}{m}) = \frac{A_{n}^{m}}{m!} = \frac{n!}{m! (n - m)!}$

特别的，当 $m > n$ 时， $C_{n}^{m} = A_{n}^{m} = 0$

多重排列： $(\binom{n}{n_{1}, n_{2}, \dots, n_{k}}) = \frac{n!}{\prod n_{i}!}$

错位排列： $f (n) = (n - 1) (f (n - 1) + f (n - 2))$

错位排列2 ： $f (n) = n! (\frac{1}{1!} - \frac{1}{2!} + \frac{1}{3!} - \dots + (- 1)^{n - 1} \frac{1}{n!})$

圆排： $Q_{n}^{r} = \frac{A_{n}^{r}}{r}$

组合数的一些性质：
$\begin{aligned} (\binom{n}{m}) = (\binom{n}{n - m}) \\ (\binom{n}{k}) = \frac{n}{k} (\binom{n - 1}{k - 1}) \\ (\binom{n}{m}) = (\binom{n - 1}{m}) + (\binom{n - 1}{m}) \\ (\binom{n}{0}) + (\binom{n}{1}) + \dots + (\binom{n}{n}) = 2^{n} \\ \sum_{0}^{n} (- 1)^{i} (\binom{n}{i}) = [n == 0] & \sum_{i = 0}^{m} (\binom{n}{i}) (\binom{m}{m - i}) = (\binom{m + n}{m}) (n \geq m) \\ \sum_{i = 0}^{n} {(\binom{n}{i})}^{2} = (\binom{2 n}{n}) \\ \sum_{i = 0}^{n} i (\binom{n}{i}) = n 2^{n - 1} \\ \sum_{i = 0}^{n} i^{2} (\binom{n}{i}) = n (n + 1) 2^{n - 2} \\ \sum_{i = 0}^{n} (\binom{i}{k}) = (\binom{n + 1}{k + 1}) \\ (\binom{n}{t}) (\binom{t}{k}) = (\binom{n}{k}) = (\binom{n - k}{t - k}) \\ \sum_{i = 0}^{n} (\binom{n - i}{i}) = F (n + 1) (其中 F (n + 1) 表示斐波拉契数列) \end{aligned}$

做 $k$ 次前缀异或和，对于最后一个数，第 $i$ 个数被计算次数为 $(\binom{n - i + k - 1}{k - 1}) = (\binom{n - i + k - 1}{n - i})$

Lucas 定理

$(\binom{n}{m}) \mod P = (\binom{⌊ n / P ⌋}{⌊ m / P ⌋}) * (\binom{n \mod P}{m \mod P}) \mod P$

推论： $(\binom{n}{m}) \equiv 1 (\mod 2)$ 的充要条件是 $m \subseteq n$

卡特兰数

$\begin{aligned} C a t (n) = \frac{(\binom{2 n}{n})}{n + 1} \\ C a t (n) = {\begin{cases} \sum_{i = 1}^{n} C a t (i - 1) C a t (n - i) & n \geq 2 \\ 1 & n = 0, 1 \end{cases} \\ C a t (n) = \frac{C a t (n - 1) (4 n - 2)}{n + 1} \\ C a t (n) = (\binom{2 n}{n}) - (\binom{2 n}{n - 1}) \end{aligned}$

莫比乌斯反演

$\begin{aligned} F (n) = \sum_{d ∣ n} f (d) \Rightarrow f (n) = \sum_{d ∣ n} μ (d) F (\frac{n}{d}) \\ F (n) = \sum_{n ∣ d} f (d) \Rightarrow f (n) = \sum_{n ∣ d} μ (\frac{d}{n}) F (d) \\ \sum_{d ∣ n} μ (d) = [n == 1] \\ \sum_{d ∣ n} \frac{μ (d)}{d} = \frac{φ (n)}{n} \\ d (n m) = \sum_{i ∣ n} \sum_{j ∣ m} [gcd (i, j) == 1] (其中 d (x) 表示 x 的约数个数) \end{aligned}$

欧拉反演

$\begin{aligned} φ * I = i d \\ \sum_{d ∣ n} μ (d) \frac{n}{d} = φ (n) \\ n = \sum_{d ∣ n} φ (d) \\ \sum_{i = 1}^{n} gcd (i, n) = \sum_{d ∣ n} \frac{n}{d} φ (d) \end{aligned}$

Dirichlet前缀和

前缀：

for (int i = 1; i <= ct && pri[i] <= n; ++i)
    for (int j = 1; LL(j) * pri[i] <= n; ++j) b[j * pri[i]] += b[j];

后缀：

for (int i = 1; i <= ct && pri[i] <= n; ++i)
    for (int j = n / pri[i]; j; --j) b[j] += b[j * pri[i]];

逆前缀：

for (int i = ct; i; ++i)
    for (int j = n / pri[i]; j; --j) a[j * pri[i]] -= a[j];

逆后缀：

for (int i = ct; i; ++i)
     for (int j = 1; LL(j) * pri[i] <= n; ++j) a[j] -= a[j * pri[i]];

生成函数

普通型 OGF ：
$\begin{aligned} \prod_{i = 1}^{n} (\sum_{m \in M_{i}} x^{m}) (其中 M_{i} 是 a_{i} 的出现次数集合) \\ 常见的有 : \\ \frac{1}{(1 - x)^{n}} = 1 + n x + \frac{n * (n + 1)}{2!} x^{2} + \frac{n * (n + 1) * (n + 2)}{3!} + \dots \\ \frac{1}{1 - x} = 1 + x + x^{2} + x^{3} + \dots \end{aligned}$
指数型 EGF ：
$\begin{aligned} \prod_{i = 1}^{n} (\sum_{m \in M_{i}} \frac{x^{m}}{m!}) (其中 M_{i} 是 a_{i} 的出现次数集合) \\ 常见的有 : \\ e^{x} = \sum_{n = 0}^{\infty} \frac{x^{n}}{n!} = 1 + x + \frac{x^{2}}{2!} + \dots \\ \frac{e^{x} + e - x}{2} = \sum_{n = 0}^{\infty} \frac{x^{2 n}}{(2 n)!} = 1 + \frac{x^{2}}{2!} + \frac{x^{4}}{4!} + \dots \\ \frac{e^{x} - e^{- x}}{2} = \sum_{n = 0}^{\infty} \frac{x^{2 n + 1}}{(2 n + 1)!} = x + \frac{x^{3}}{3!} + \frac{x^{5}}{5!} + \dots \end{aligned}$

群论

置换群

$n$ 个元素 $1, 2, \dots, n$ 之间的一个置换 $f = (\binom{1, 2, 3, \dots, n}{a_{1}, a_{2}, a_{3}, \dots, a_{n}})$ ，表示“ $1$ 被 $a_{1}$ 取代， $2$ 被 $a_{2}$ 取代，依此类推”，其中 $a_{1}, a_{2}, \dots, a_{n}$ 是 $1 \sim n$ 的一个排列

Burnside 引理

$L = \frac{1}{∣ G ∣} \sum_{j = 1}^{s} D (a_{j})$

其中 $L$ 表示本质不同的方案数， $D (a_{j})$ 表示在置换 $a_{i}$ 下不变的元素个数， $∣ G ∣$ 是置换群大小

Polya 定理

记 $c (f)$ 为置换 $f$ 的循环节个数， . $m$ 为颜色总数，有 $D (f) = m^{c (f)}$ ，则有：
$L = \frac{1}{∣ G ∣} (\sum_{j = 1}^{s} m^{c (a_{j})})$

矩阵

存储

struct Mtx
{
    DB x[N][N];
    DB* operator [] (int id){ return x[id]; }
} a;

LU分解

namespace DLT //Doolittle
{
    Mtx l, u;
    DB X[N], Y[N];
    int get_lu(Mtx x, int len)
    {
        int k, i, j, r;
        for (k = 1; k <= len; ++k)
        {
            for (j = k; j <= len; ++j)
            {
                u[k][j] = x[k][j];
                for (r = k - 1; r; --r) u[k][j] -= l[k][r] * u[r][j];
                if (fabs(u[k][j]) < eps) return -1;
                else if (!(fabs(u[k][j]) > eps)) return 1;
            }
            for (i = k; i <= len; ++i)
            {
                l[i][k] = x[i][k];
                for (r = k - 1; r; --r) l[i][k] -= l[i][r] * u[r][k];
                l[i][k] /= u[k][k];
            }
            l[k][k] = 1;
        }
        return 0;
    }
    void calc(DB x[], int len)
    {
        int k, r;
        for (k = 1; k <= len; ++k)
        {
            Y[k] = x[k];
            for (r = k - 1; r; --r) Y[k] -= l[k][r] * Y[r];
        }
        for (k = len; k; --k)
        {
            X[k] = Y[k];
            for (r = k + 1; r <= len; ++r) X[k] -= u[k][r] * X[r];
            X[k] /= u[k][k];
            if (fabs(X[k]) < eps) X[k] = 0;
        }
    }
}

高斯消元

int guass(Mtx &x, int len) //注意传实参
{
    int i, j, k, t, now;
    for (i = now = 1; i <= len; ++i)
    {
        t = now;
        for (j = i; j <= len; ++j) if (fabs(x[j][i]) > fabs(x[t][i])) t = j;
        if (fabs(x[t][i]) < eps) continue;
        if (t != now) std::swap(x.x[t], x.x[now]);
        for (j = len + 1; j >= i; --j) x[now][j] /= x[now][i];
        for (j = now + 1; j <= len; ++j) if (fabs(x[j][i]))
            for (k = len + 1; k >= i; --k) x[j][k] -= x[j][i] * x[now][k];
        ++now;
    }
    if (now <= len)
    {
        for (i = now; i <= len; ++i) if (fabs(x[i][len + 1]) > eps) return -1;
        return len - now + 1;
    }
    for (i = len; i; --i)
        for (j = i + 1; j <= len; ++j) x[i][len + 1] -= x[i][j] * x[j][len + 1];
    for (i = len; i; --i) if (fabs(x[i][len + 1]) < eps) x[i][len + 1] = 0; //防止出现-0.00
    return 0;
}

矩阵求逆

bool mtxinv(Mtx &x, Mtx &as, int len)
{
    int i, j, k, t;
    for (i = 1; i <= len; ++i)
    {
        for (t = i; t <= len; ++t) if (x[t][i]) break;
        if (t > len) return false;
        if (t != i) std::swap(x.x[t], x.x[i]), std::swap(as.x[t], as.x[i]);
        if (x[i][i] != 1)
        {
            for (j = len, t = qpow(x[i][i], P - 2); j >= 1; --j) as[i][j] = LL(t) * as[i][j] % P;
            for (j = len, t = qpow(x[i][i], P - 2); j >= i; --j) x[i][j] = LL(t) * x[i][j] % P;
        }
        for (j = i + 1; j <= len; ++j) if (x[j][i])
            for (k = len; k >= 1; --k) adj(as[j][k] -= LL(x[j][i]) * as[i][k] % P);
        for (j = i + 1; j <= len; ++j) if (x[j][i])
            for (k = len; k >= i; --k) adj(x[j][k] -= LL(x[j][i]) * x[i][k] % P);
    }
    for (i = len; i; --i)
        for (j = i + 1; j <= len; ++j)
        {
            for (k = len; k >= 1; --k) adj(as[i][k] -= LL(x[i][j]) * as[j][k] % P);
            adj(x[i][len + 1] -= LL(x[i][j]) * x[j][len + 1] % P);
        }
    return true;
}

行列式

int det(Mtx x)
{
    int res = 1, i, j, t, k, f = 1;
    for (i = 1; i <= n; ++i)
    {
        for (j = i + 1; j <= n; ++j)
        {
            while (x[i][i]) //对第i行和第j行做辗转相减
            {
                t = x[j][i] / x[i][i];
                for (k = i; k <= n; ++k) adj(x[j][k] -= LL(t) * x[i][k] % p);
                std::swap(x.x[i], x.x[j]), f ^= 1;
            }
            std::swap(x.x[i], x.x[j]), f ^= 1;
        }
        res = LL(res) * x[i][i] % p;
    }
    if (!f) adj(res = -res); //注意res=0时
    return res;
}

调用前要保证是正数

Matrix-Tree

int det(int x[][N])
{
	int res = 1, w = 1;
	for (int i =2; i <= n; ++i) //以1为根,故删掉1行1列
		for (int j = i + 1; j <= n; ++j)
		{
			while (x[i][i])
			{
				int div = x[j][i] / x[i][i];
				for (int k = i; k <= n; ++k)
					x[j][k] = (x[j][k] - (LL)div * x[i][k] % P + P) % P;
				swap(x[i], x[j]);
				w = -w;
			}
			swap(x[i], x[j]);
			w = -w;
		}
	for (int i = 2; i <= n; ++i)
		res = (LL)x[i][i] * res % P;
	res *= w;
	return (res + P) % P;
}

$k$ 是度数矩阵减邻接矩阵

其它

快读快输

namespace FIO
{
	const int L = (1 << 20) + 100;
	char buf[L], out[L], *S, *E;
	int l = 0;
	#define gh() (S == E ? E = (S = buf) + fread(buf, 1, L, stdin), (S == E ? EOF : *S++) : *S++)
	void flus(){ fwrite(out, 1, l, stdout), l = 0; }
	void chk(){ if (l >= L - 100) flus(); }
	void putc(char x){ out[l++] = x, chk(); }
	void rd(char *s)
	{
		char ch = gh();
		while (ch < 33 || ch > 126) ch = gh();
		for (; ch >= 33 && ch <= 126; ch = gh()) *s++ = ch;
		*s = '\0';
	}
	void wt(char *s){ while (*s != '\0') putc(*s++); }
	void wt(const char *s){ while (*s != '\0') putc(*s++); } //这是为了可以直接""构造字符串输出
	template<typename T>
	void rd(T &x)
	{
		char ch = gh(), t = 0;
		for (; ch < '0' || ch > '9'; ch = gh()) t |= ch == '-';
		for (x = 0; ch >= '0' && ch <= '9'; ch = gh()) x = x * 10 + (ch ^ 48);
		if (t) x = -x;
	}
	template<typename T>
	void wt(T x)
	{
		if (x < 0) putc('-'), x = -x;
		if (x > 9) wt(x / 10);
		out[l++] = x % 10 + 48, chk();
	}
	template<typename T, typename ...Args>
	void rd(T &x, Args &...args){ rd(x), rd(args...); }
	template<typename ...Args>
	void rd(char *x, Args ...args){ rd(x), rd(args...); }
	template<typename T, typename ...Args>
	void wt(T x, Args ...args){ wt(x), wt(args...); }
	#undef gh
}
using FIO::flus;
using FIO::rd;
using FIO::wt;

无法读入浮点数；不可以字符串和整型一起读入（但可以一起输出）；注意最后要 flus() 一下；只能文件输入（但可以随意输出），如果要本地输入请 #define gh() getchar()

二分

只会很不优美的写法

int l, r, mid, res;
while (l <= r)
{
    mid = (l + r) >> 1;
    if (chk(mid)) l = mid + 1, res = mid;
    else r = mid - 1;
}
return res;

三分

int l, r, lm, rm, res, len;
while (l <= r)
{
    len = (r - l + 1) / 3;
    lm = l + len;
    rm = lm + len;
    if (f(lm) < f(rm)) res = rm, l = lm + 1;
    else if (f(lm) > f(rm)) res = lm, r = rm - 1;
}
return res;

模拟退火

const DB T0 = 1e4, TE = 1e-4, C = 0.99, SP = 1e3; //这是参数,影响时间和精度
void E(){ 这是一个估计函数(同时会跟新ans),越优的状态其估计越小 }
void simulate_anneal()
{
    预处理
    DB now = E(), np, dt, ct;
    for (DB t = E0; t > TE; t *= C)
    {
        随机进入新的状态,新状态与现状态的差异大小最好和t正相关
        np = E();
        dt = np - now;
        if (exp(-dt / t) > 生成的一个(0, 1)之间的随机数)
        {
            跳至新状态
           	now = np；
        }
        else
        {
            恢复原状态
            if ((++ct) > SP) return ; //一个优化:多次为转移就直接以当前状态做最优解
        }
    }
}
一般会多次调用simulate_anneal或调小C以保证正确性

取模优化

void adj(int &x){ x += (x >> 31) & P; }

仅限 $x$ 为负数时可用，当 $x$ 是 LL 时把 $31$ 改成 $63$

Min-Max 容斥

$\begin{aligned} max (S) = \sum_{T \subseteq S} (- 1)^{∣ T ∣ - 1} min (T) \\ min (S) = \sum_{T \subseteq S} (- 1)^{∣ T ∣ - 1} max (T) \\ k m a x (S) = \sum_{T \subseteq S} (- 1)^{∣ T ∣ - k} (\binom{∣ T ∣ - 1}{k - 1}) min (T) \end{aligned}$

FWT

namespace FWT
{
	const int iv2 = 499122177; //2的逆元
	void _or(int x[], int len)
	{
		for (int i = 2; i <= len; i <<= 1) //当前区间长度
			for (int mid = i >> 1, j = 0; j < len; j += i) //j当前区间前端
				for (int k = j; k < j + mid; ++k) adj(x[k + mid] += x[k] - P);
	}
	void u_or(int x[], int len)
	{
		for (int i = 2; i <= len; i <<= 1)
			for (int mid = i >> 1, j = 0; j < len; j += i)
				for (int k = j; k < j + mid; ++k) adj(x[k + mid] -= x[k]);
	}
	void _and(int x[], int len)
	{
		for (int i = 2; i <= len; i <<= 1)
			for (int mid = i >> 1, j = 0; j < len; j += i)
				for (int k = j; k < j + mid; ++k) adj(x[k] += x[k + mid] - P);
	}
	void u_and(int x[], int len)
	{
		for (int i = 2; i <= len; i <<= 1)
			for (int mid = i >> 1, j = 0; j < len; j += i)
				for (int k = j; k < j + mid; ++k) adj(x[k] -= x[k + mid]);
	}
	void _xor(int x[], int len)
	{
		for (int i = 2, t1, t2; i <= len; i <<= 1)
			for (int mid = i >> 1, j = 0; j < len; j += i)
				for (int k = j; k < j + mid; ++k)
				{
					t1 = x[k], t2 = x[k + mid];
					adj(x[k] = t1 + t2 - P), adj(x[k + mid] = t1 - t2);
				}
	}
	void u_xor(int x[], int len)
	{
		for (int i = 2, t1, t2; i <= len; i <<= 1)
			for (int mid = i >> 1, j = 0; j < len; j += i)
				for (int k = j; k < j + mid; ++k)
				{
					t1 = x[k], t2 = x[k + mid];
					adj(x[k] = t1 + t2 - P), adj(x[k + mid] = t1 - t2);
					x[k] = LL(iv2) * x[k] % P, x[k + mid] = LL(iv2) * x[k + mid] % P;
				}
	}
}

子集卷积

#define pct(x) __builtin_popcount(x)
int main()
{
	scanf("%d", &bit), n = (1 << bit);
	for (int i = 0; i < n; ++i) scanf("%d", &f[pct(i)][i]);
	for (int i = 0; i < n; ++i) scanf("%d", &g[pct(i)][i]);
	for (int i = 0; i <= bit; ++i) fwt(f[i], n), fwtor(g[i], n);
	for (int i = 0; i <= bit; ++i)
		for (int j = 0; j + i <= bit; ++j)
			for (int s = 0; s < n; ++s) adj(h[i + j][s] += LL(f[i][s]) * g[j][s] % P - P);
	for (int i = 0; i <= bit; ++i) ufwtor(h[i], n);
	for (int i = 0; i < n; ++i) printf("%d ", h[pct(i)][i]);
	return 0;
}

线性基

#include <bits/stdc++.h>
#define STC static
using LL = long long;
int n; //n是题目中插入到线性基里的个数
namespace LB  //Linear Basis
{
    const int L = 63;
    LL a[L + 5], si;
    void clear(){ memset(a, 0, sizeof a), si = 0; }
    void ins(LL  x)
    {
        for (int i = L; ~i; --i) if ((x >> i) & 1)
            if (!a[i]) return ++si, void(a[i] = x);
            else x ^= a[i];
    }
    LL gmx() //get max
    {
        LL res = 0;
        for (int i = L; ~i; --i) res = std::max(res ^ a[i], res);
        return res;
    }
    LL gmn() //get min
    {
        if (si < n) return 0;
        for (int i = 0; i <= L; ++i) if (a[i]) return a[i];
    }
    bool chk(LL x)
    {
        for (int i = L; ~i; --i) if ((x >> i) & 1)
            if (!a[i]) return false;
            else x ^= a[i];
        return true;
    }
    void reb() //rebuild
    {
        STC int tp[L + 5];
        si = 0;
        for (int i = 0; i <= L; ++i)
        {
            for (int j = i - 1; ~j; --j) if ((a[i] >> j) & 1) a[i] ^= a[j];
            if (a[i]) tp[si++] = a[i];
        }
        for (int i = 0; i < si; ++i) a[i] = tp[i];
    }
    LL gk(LL k) //get k
    {
        LL res = 0;
        if (si < n && !(--k)) return 0;
        if (k >= (1ll << si)) return -1;
        for (int i = 0; i < si; ++i) if ((k >> i) & 1) res ^= a[i];
        return res;
    }
}

sqrt

雷神之锤 3 的神仙开根法：

float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y   = number;
    i   = * ( long * ) &y;   // evil floating point bit level hacking
    i   = 0x5f3759df - ( i >> 1 ); // what the fuck?
    y   = * ( float * ) &i;
    y   = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
    // y   = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed

    #ifndef Q3_VM
    #ifdef __linux__
         assert( !isnan(y) ); // bk010122 - FPE?
    #endif
    #endif
    return y;
}

不知道有啥用

斐波那契数列循环

求斐波那契数列在模 $p$ 意义下的循环节

循环节长度上界是 $6 \times p$ ，那么每次随机两个 pos 检验该 pos 起始的两位是否出现过（光速幂预处理矩阵），由生日悖论，期望下只要 $O (\sqrt{p})$ 次即可得到一个不一定是最小的循环节，然后枚举其因数验证即可

也可以对矩阵做 bsgs ，设转移矩阵为 $A$ ，那么就是 $A^{k} = I$ ，由斐波那契定义只 $A$ 一定有逆

$p = 2, 5$ 手玩
否则，若 $p$ 是奇质数：
- 若 $5$ 是模 $p$ 意义下的二次剩余，循环节长度一定是 $p - 1$ 的约数
- 否则，循环节长度一定是 $2 p + 2$ 的约数
否则， $p$ 是合数，也有结论，但还不如上两个做法

脚本和指令

win：

g++ %1.cpp -o %1.exe -O2 -std=c++14 -Wall -Wextra -Wl,--stack=1145141919
if "%errorlevel%" == "0" (
    %1.exe
)

linux：

g++ $1.cpp -o $1 -O2 -std=c++14 -Wall -Wshadow -Wextra -Wunreachable-code -Winline -Wpointer-arith
if [ $? -eq 0 ]
then 
    ./$1
else
    echo "CE"
fi

高精

没写高精除高精

#define eb emplace_back
using LL = long long;
namespace BigNum
{
    const int P = 998244353;
    int r[1 << 20 | 100], gn[1 << 20 | 100];
    int qpow(int x, int y = P - 2)
    {
        int res = 1;
        for (; y; y >>= 1, x = LL(x) * x % P) if (y & 1) res = LL(x) * res % P;
        return res;
    }
    void adj(int &x){ x += (x >> 31) & P; }
    void ntt(int *x, int tot, int op)
    {
        for (int i = 1; i < tot; ++i) if (i < r[i]) std::swap(x[i], x[r[i]]);
        for (int mid = 1; mid < tot; mid <<= 1)
        {
            int g0 = qpow(3, (P - 1) / (mid << 1));
            if (op == -1) g0 = qpow(g0);
            gn[0] = 1;
            for (int i = 1; i < mid; ++i) gn[i] = LL(g0) * gn[i - 1] % P;
            for (int i = 0; i < tot; i += (mid << 1))
                for (int *x1 = x + i, *x2 = x + mid + i, *ed = x2, *g = gn; x1 != ed; ++x1, ++x2, ++g)
                {
                    int p = *x1, q = LL(*x2) * *g % P;
                    adj(*x1 = p + q - P), adj(*x2 = p - q);
                }
        }
        if (op == 1) return ;
        int t = qpow(tot);
        for (int i = 0; i < tot; ++i) x[i] = LL(t) * x[i] % P;
    }
    struct Big
    {
        
        std::vector<int> v;
        bool sign;
        int& operator [] (const int id){ return v[id]; }
        void init(LL val)
        {
            v.clear(), sign = false;
            if (val < 0) sign = true, val = -val;
            for (; val; val /= 10) v.eb(val % 10);
        }
        void init(char *s, int l, int r)
        {
            v.clear(), sign = false;
            if (s[l] == '-') sign = true, ++l;
            for (int i = r; i >= l; --i) v.eb(s[i] - '0');
        }
        void out()
        {
            if (v.size() == 1 && !v[0]) return void(putchar('0'));
            if (sign) putchar('-');
            for (int i = v.size() - 1; ~i; --i) putchar(v[i] + '0');
        }
    } ;
    bool operator == (Big x, Big y)
    {
        if (x.sign != y.sign) return false;
        if (x.v.size() != y.v.size()) return false;
        for (int i = x.v.size() - 1; ~i; --i) if (x[i] != y[i]) return false;
        return true;
    }
    bool operator < (Big x, Big y)
    {
        if (x.sign ^ y.sign) return x.sign;
        if (x.v.size() != y.v.size()) return x.sign ^ (x.v.size() < y.v.size());
        for (int i = x.v.size() - 1; ~i; --i) if (x[i] != y[i]) return x.sign ^ (x[i] < y[i]);
        return false;
    }
    bool operator > (Big x, Big y){ return y < x; }
    bool operator <= (Big x, Big y){ return x == y || x < y; }
    bool operator >= (Big x, Big y){ return x == y || y < x; }
    Big operator * (Big x, Big y)
    {
        if (x.v.empty() || y.v.empty()) return {{}, false};
        int n = x.v.size(), m = y.v.size(), bit = 0, tot = 1;
        for (; tot < n + m + 1; tot <<= 1, ++bit);
        for (int i = 1; i < tot; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (bit - 1));
        x.v.resize(tot), y.v.resize(tot);
        if (x.v != y.v) ntt(x.v.data(), tot, 1), ntt(y.v.data(), tot, 1);
        else ntt(x.v.data(), tot, 1), y.v = x.v;
        for (int i = 0; i < tot; ++i) x[i] = LL(x[i]) * y[i] % P;
        ntt(x.v.data(), tot, -1), x.v.resize(n + m);
        tot = 0;
        for (int &t : x.v) t += tot, tot = t / 10, t %= 10;
        n += m;
        while (n > 1 && !x[n - 1]) --n;
        x.v.resize(n);
        x.sign ^= y.sign;
        return x;
    }
    Big operator * (Big x, LL y)
    {
        if (y < 0) y = -y, x.sign ^= 1;
        int n = x.v.size(), tot = 0;
        for (int i = 0; i < n; i++)
        {
            tot += x[i] * y;
            x[i] = tot % 10;
            tot /= 10;
        }
        for (; tot; tot /= 10) x.v.eb(tot % 10);
        while (n > 1 && !x[n - 1]) --n;
        x.v.resize(n);
        return x;
    }
    Big operator + (Big x, Big y)
    {
        int n = std::max(x.v.size(), y.v.size()), tot = 0;
        x.v.resize(n), y.v.resize(n);
        if (x.sign == y.sign)
        {
            for (int i = 0; i < n; ++i)
            {
                x[i] += tot + y[i], tot = 0;
                if (x[i] >= 10) tot = 1, x[i] -= 10;
            }
            if (tot) x.v.eb(tot);
            return x;
        }
        for (int i = n - 1; ~i; --i)
            if (x[i] != y[i])
            {
                if (x[i] < y[i]) std::swap(x, y);
                break;
            }
        for (int i = 0; i < n; ++i)
        {
            x[i] -= y[i] + tot, tot = 0;
            if (x[i] < 0) tot = 1, x[i] += 10;
        }
        while (n > 1 && !x[n - 1]) --n;
        x.v.resize(n);
        return x; 
    }
    Big operator - (Big x, Big y){ return y.sign ^= 1, x + y; }
    Big operator / (Big x, LL y)
    {
        if (!y)
        {
            puts("RE");
            return {{}, false};
        }
        if (y < 0) y = -y, x.sign ^= 1;
        int n = x.v.size();
        LL tot = 0;
        for (int i = n - 1; ~i; --i)
        {
            tot = tot * 10 + x[i];
            x[i] = tot / y;
            tot %= y;
        }
        while (n > 1 && !x[n - 1]) --n;
        x.v.resize(n);
        return x;
    }
    LL  operator % (Big x, LL y)
    {
        if (!y)
        {
            puts("RE");
            return 0;
        }
        if (y < 0) y = -y, x.sign ^= 1;
        int tot = 0;
        for (int i = x.v.size() - 1; ~i; --i)
        {
            tot = tot * 10 + x[i];
            tot %= y;
        }
        return x.sign ? -tot : tot;
    }
    void operator *= (Big &x, Big y){ x = x * y; }
    void operator *= (Big &x, LL y){ x = x * y; }
    void operator += (Big &x, Big y){ x = x + y; }
    void operator -= (Big &x, Big y){ x = x - y; }
    void operator /= (Big &x, LL y){ x = x / y; }
}