【模板库】线段树合并

参考例题:http://www.lydsy.com/JudgeOnline/problem.php?id=4530

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

const int N = 200009; 
const int M = N * 21;

int n, m, vis[N], head[N], nxt[N], to[N];
int dep[N], beg[N], out[N], sz[N], fa[N];
struct Data{
	int t, x, y;
	inline Data() {
	}
	inline Data(bool a, int b, int c):t(a), x(b), y(c) {
	} 
}opt[N];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

inline void AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

inline void DFS(int w, int f) {
	static int D = 0;
	vis[w] = 1;
	beg[w] = ++D;
	dep[w] = dep[f] + 1;
	for (int i = head[w]; i; i = nxt[i]) {
		if (to[i] != f) {
			DFS(to[i], w);
		}
	}
	out[w] = D;
}

inline int find(int x) {
	return fa[x] == x? x: fa[x] = find(fa[x]);
}

class SegmentTree{
int cnt, ch[M][2], sum[M], root[N];
public:
	inline void insert(int p, int v) {
		insert(root[p], 1, n, v);
	}
	inline void merge(int a, int b) {
		root[a] = Merge(root[a], root[b]);
	}
	inline int query(int p, int l, int r) {
		return query(root[p], 1, n, l, r);
	}
private:
	inline int Merge(int a, int b) {
		if (!a || !b) {
			return a + b;
		} else {
			sum[a] += sum[b];
			ch[a][0] = Merge(ch[a][0], ch[b][0]);
			ch[a][1] = Merge(ch[a][1], ch[b][1]);
			return a;
		}
	}
	inline void insert(int &w, int l, int r, int p) {
		sum[w = ++cnt] = 1;
		if (l < r) {
			int mid = l + r + 1 >> 1;
			if (p < mid) {
				insert(ch[w][0], l, mid - 1, p);
			} else {
				insert(ch[w][1], mid, r, p);
			}
		}
	} 
	inline int query(int w, int l, int r, int L, int R) {
		if (!w) {
			return 0;
		} else if (L <= l && r <= R) {
			return sum[w];
		} else {
			int mid = l + r + 1 >> 1, ret = 0;
			ret += L < mid? query(ch[w][0], l, mid - 1, L, R): 0;
			ret += mid <= R? query(ch[w][1], mid, r, L, R): 0;
			return ret;
		}
	}
}SGT;

int main() {
	n = read(); m = read();
	for (int i = 1; i <= m; i++) {
		char cmd[3]; 
		scanf("%s", cmd);
		int u = read(), v = read();
		if (cmd[0] == 'A') {
			AddEdge(u, v);
		}
		opt[i] = Data(cmd[0] == 'A', u, v);
	}
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			DFS(i, i);
		}
	}
	for (int i = 1; i <= n; i++) {
		sz[i] = 1;
		fa[i] = i;
		SGT.insert(i, beg[i]);
	}
	for (int i = 1; i <= m; i++) {
		int u = opt[i].x, v = opt[i].y;
		if (opt[i].t == 1) {
			SGT.merge(find(u), find(v));
			sz[find(u)] += sz[find(v)];
			fa[find(v)] = find(u);
		} else {
			if (dep[u] < dep[v]) {
				swap(u, v);
			}
			int p1 = SGT.query(find(u), beg[u], out[u]);
			int p2 = sz[find(u)] - p1;
			printf("%lld\n", (LL)p1 * p2);
		}
	}
	return 0;
}

【模板库】拉格朗日插值法

参考例题:https://oi.qizy.tech/?p=3191

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

const int N = 200;
const int MOD = 1000000007;

int n,m,K,r[N],u[N],f[N],g[N],h[N],alpha[N],C[N][N]; 

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
} 

inline int Pow(int w, int t) {
	int ret = 1;
	for (;t;t>>=1,w=(LL)w*w%MOD) {
		if (t & 1) {
			ret = (LL)ret * w % MOD;
		} 
	}
	return ret;
}

inline int LagrangePolynomial(int x, int len, int *ff, int *xx) {
	int ret = 0;
	for (int i=1;i<=len;i++) {
		int tmp = ff[i];
		for (int j=1;j<=len;j++) {
			if (i == j) continue;
			tmp = (LL)tmp * (x - xx[j]) % MOD;
			tmp = (LL)tmp * Pow(xx[i] - xx[j], MOD-2) % MOD;
		}
		ret = (ret + tmp) % MOD;
	}
	return (ret + MOD) % MOD;
} 

int main() {
	n = read(); m = read(); K = read();
	for (int i=1;i<=m;i++) {
		u[i] = read();
	}
	for (int i=1;i<=m;i++) {
		r[i] = read();
	}
	//预处理组合数 
	C[0][0] = 1;
	for (int i=1;i<=n;i++) {
		C[i][0] = 1;
		for (int j=1;j<=i;j++) {
			C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
		}
	}
	//拉格朗日插值
	for (int w=1;w<=m;w++) {
		for (int i=1;i<=n+1;i++) {
			f[i] = 0; h[i] = i;
			for (int j=1;j<=i;j++) {
				f[i] = (f[i] + (LL)Pow(i-j, r[w]-1) * Pow(j, n-r[w])) % MOD;
			}
		}  
		g[w] = LagrangePolynomial(u[w], n+1, f, h);
	}
	//广义容斥原理 
	int ans = 0;
	for (int i=K,t=1;i<=n;i++,t*=-1) {
		alpha[i] = C[n-1][i];
		for (int j=1;j<=m;j++) {
			alpha[i] = (LL)alpha[i] * C[n-1-i][r[j]-1] % MOD * g[j] % MOD;
		}
		ans = (ans + t * (LL)C[i][K] * alpha[i]) % MOD;
	}
	printf("%d\n",(ans+MOD)%MOD);
	return 0;
}

【模板库】半平面交

参考例题:http://www.lydsy.com/JudgeOnline/problem.php?id=2618
参考资料:http://foenix.top/2015/03/17/半平面交nlogn方法小结/
备注:这份代码不能处理退化成一个点或一条线的情况,如果实在要处理这种情况,请自行将直线平移适当距离

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

const int N = 10000;
const double EPS = 1e-8;

int n,m;

struct Point{
	double x,y;
	inline Point() {}
	inline Point(double a, double b):x(a),y(b) {}
	inline Point operator + (const Point &P) const {return Point(x+P.x, y+P.y);}
	inline Point operator - (const Point &P) const {return Point(x-P.x, y-P.y);}
	inline Point operator * (double d) const {return Point(x*d, y*d);}
	inline Point operator / (double d) const {return Point(x/d, y/d);}
	inline double operator * (const Point &P) const {return x*P.x + y*P.y;}
	inline double operator ^ (const Point &P) const {return x*P.y - P.x*y;} 
}p[N],cvx[N];

struct Line{
	Point a,b; double slp;
	inline Line() {}
	inline Line(const Point &x, const Point &y) {a = x; b = y; slp = atan2(b.y-a.y, b.x-a.x);}
	inline bool operator < (const Line &L) const {return slp < L.slp - EPS || (fabs(slp-L.slp) < EPS && ((b-a)^(L.b-a)) < -EPS);}
	inline bool operator != (const Line &L) {return fabs(slp - L.slp) > EPS;}
	inline bool onleft(const Point &P) {return ((b - a) ^ (P - a)) > EPS;}
	inline double len() {return sqrt((b - a) * (b - a));}
	inline Point ins(const Line &L) {
		double s1 = (b - L.b) ^ (L.a - L.b);
		double s2 = (a - L.a) ^ (L.b - L.a);
		Point tmp = a + (((b - a) * s2) / (s1 + s2));
		return a + (((b - a) * s2) / (s1 + s2));
	}
}l[N],que[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void HalfPlaneIntersection(int tot, Line *a, int &cnt, Line *b, Point *c) {
	sort(a+1, a+1+tot); cnt = tot; tot = 1; 
	for (int i=2;i<=cnt;i++) if (a[i] != a[i-1]) a[++tot] = a[i]; 
	b[1] = a[1]; b[2] = a[2]; int l=1,r=2;
	for (int i=3;i<=tot;i++) {
		while (l < r && !a[i].onleft(b[r-1].ins(b[r]))) r--;
		while (l < r && !a[i].onleft(b[l].ins(b[l+1]))) l++;
		b[++r] = a[i];
	} 
	while (l < r && !b[l].onleft(b[r].ins(b[r-1]))) r--;
	while (l < r && !b[r].onleft(b[l].ins(b[l+1]))) l++;
	cnt = 0; b[0] = b[r];
	for (int i=l;i<=r;i++) b[++cnt] = b[i];
	for (int i=1;i<=cnt;i++) c[i] = b[i].ins(b[i-1]); 
}

int main() {
	n = read(); int tot=0,cnt=0;
	for (int i=1;i<=n;i++) {
		m = read();
		for (int j=1;j<=m;j++) p[j].x = read(), p[j].y = read();
		p[m+1] = p[1];
		for (int j=1;j<=m;j++) l[++tot] = Line(p[j], p[j+1]);
	}
	HalfPlaneIntersection(tot, l, cnt, que, cvx);
	double vout = 0;
	for (int i=2;i<cnt;i++) vout += (cvx[i] - cvx[1]) ^ (cvx[i+1] - cvx[1]);
	printf("%.3lf\n",vout/2);
	return 0;
}

【模板库】二维凸包

参考例题:http://poj.org/problem?id=3348
备注:可以处理重点,坐标值可以是整数和小数

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define LL long long
using namespace std;

const int N = 100000;
const double EPS = 1e-8;

int n,cnt;

struct Point{
	double x,y;
	inline Point() {}
	inline Point(double a, double b):x(a),y(b) {}
	inline Point operator + (const Point &A) {return Point(x+A.x, y+A.y);}
	inline Point operator - (const Point &A) {return Point(x-A.x, y-A.y);}
	inline Point operator / (double A) {return Point(x/A, y/A);}
	inline Point operator * (double A) {return Point(x*A, y*A);}
	inline double operator * (const Point &A) {return x*A.x + y*A.y;}
	inline double operator ^ (const Point &A) {return x*A.y - A.x*y;}
	inline bool operator < (const Point &B) const {return x < B.x - EPS || (fabs(x-B.x) < EPS && y < B.y - EPS);}
	inline bool operator == (const Point &B) const {return fabs(x - B.x) + fabs(y - B.y) < EPS;}
}p[N],cvx[N]; 

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void ConvexHull(int tot, Point *a, int &sz, Point *ret) {
	if (!tot) {sz = 0; return;}
	sort(a+1, a+1+tot); ret[sz=1] = a[1];
	tot = unique(a+1, a+1+tot) - a - 1;
	for (int i=2;i<=tot;i++) {
		while (sz > 1 && ((ret[sz] - ret[sz-1]) ^ (a[i] - ret[sz])) < EPS) sz--;
		ret[++sz] = a[i];	
	}
	for (int i=tot-1,mn=sz;i>0;i--) {
		while (sz > mn && ((ret[sz] - ret[sz-1]) ^ (a[i] - ret[sz])) < EPS) sz--;
		ret[++sz] = a[i];
	} 
	sz -= sz > 2;
} 

int main() {
	n = read();
	for (int i=1;i<=n;i++) p[i].x = read(), p[i].y = read();
	ConvexHull(n, p, cnt, cvx);
	double vout = 0; 
	for (int i=2;i<cnt;i++) 
		vout += (cvx[i] - cvx[1]) ^ (cvx[i+1] - cvx[1]) / 2;
	printf("%d\n",(int)(vout/50));
	return 0;
}

【模板库】FWT

参考例题:http://www.lydsy.com/JudgeOnline/problem.php?id=4589

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

const int N = 100009; 
const int MOD = 1000000007;
const int REV = 500000004;

bool vis[N];
int arr[N];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

inline int Pow(int w, int t) {
	int ret = 1;
	for (; t; t >>= 1, w = (LL)w * w % MOD) {
		if (t & 1) {
			ret = (LL)ret * w % MOD;
		}
	}
	return ret;
}

inline void FWT(int *a, int len, int opt = 1) {
	for (int d = 1; d < len; d <<= 1) {
		for (int i = 0; i < len; i += d << 1) {
			for (int j = 0; j < d; j++) {
				int t1 = a[i + j], t2 = a[i + j + d];
				//XOR
				if (opt == 1) {
					a[i + j] = (t1 + t2) % MOD;
					a[i + j + d] = (t1 - t2) % MOD;
				} else {
					a[i + j] = (LL)(t1 + t2) * REV % MOD;
					a[i + j + d] = (LL)(t1 - t2) * REV % MOD;
				}
				/*
				AND
				if (opt == 1) {
					arr[i + j] = t1 + t2;
					//arr[i + j + d] = t2;
				} else {
					arr[i + j] = t1 - r2;
					//arr[i + j + d] = t2;
				}
				*/
				/*
				OR
				if (opt == 1) {
					//arr[i + j] = t1;
					arr[i + j + d] = t2 + t1;
				} else {
					//arr[i + j] = t1;
					arr[i + j + d] = t2 - t1;
				}
				*/
			}
		}
	}
}

int main() {
	for (int n, m; ~scanf("%d %d", &n, &m); ) {
		memset(arr, 0, sizeof(arr));
		for (int i = 2; i <= m; i++) {
			if (!vis[i]) {
				arr[i] = 1;
				for (int j = i << 1; 0 <= j && j <= m; j += i) {
					vis[j] = 1;
				}
			}
		}
		int len = 1; 
		for (; len <= m; len <<= 1);
		FWT(arr, len);
		for (int i = 0; i < len; i++) {
			arr[i] = Pow(arr[i], n);
		}
		FWT(arr, len, -1);
		printf("%d\n", (arr[0] + MOD) % MOD);
	}
	return 0;
}

【模板库】Splay

参考例题:http://www.lydsy.com/JudgeOnline/problem.php?id=1895

#include<bits/stdc++.h>
#define LL long long
using namespace std;
  
const int INF = 0x7fffffff;
const int N = 200009;
  
inline int read() {
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret*f;
}
  
class Splay{
    struct Node{int ch[2],val,mn,sz,fa,delta,rev;}p[N]; int cnt;
    public:
        inline Splay() { //init the splay and place begining(1) and ending(2) of the sequence
            cnt = 2; p[1].ch[1] = 2;
            p[1].val = p[1].mn = INF;
            p[2].val = p[2].mn = INF;
            p[1].sz = 2; p[2].sz = 1;
            p[1].fa = p[2].fa = 1;
        }
        inline void insert(int pos, int v) { ++pos; //insert a new node with value v as ths (pos + 1) node
            int w; splay(w=rank(1, pos), 1);
            int nw; splay(nw=rank(1, pos+1), w);
            p[nw].ch[0] = ++cnt; p[cnt].fa = nw;
            p[cnt].mn = p[cnt].val = v; p[cnt].sz = 1;
            maintain(nw); maintain(w); maintain(1);
        }
        inline void add(int l, int r, int v) { ++l; ++r; //add value v to elements of range[l,r]
            int w; splay(w=rank(1, l-1), 1);
            int nw; splay(nw=rank(1, r+1), w);
            p[p[nw].ch[0]].delta += v; 
            PushDown(p[nw].ch[0]); maintain(nw);
            maintain(w); maintain(1); 
        }
        inline int query(int l, int r) { ++l; ++r; //query the min element in range[l,r]
            int w; splay(w=rank(1, l-1), 1); 
            int nw; splay(nw=rank(1, r+1), w);
            return PushDown(p[nw].ch[0]), p[p[nw].ch[0]].mn;
        }
        inline void remove(int r) { ++r; //remove the r node
            int w; splay(w=rank(1, r-1), 1);
            int nw; splay(nw=rank(1, r+1), w);
            p[nw].ch[0] = 0; maintain(nw);
            maintain(w); maintain(1);
        } 
        inline void reverse(int l, int r) { ++l; ++r; //reverse the elements in range[l,r]
            int w; splay(w=rank(1, l-1), 1);
            int nw; splay(nw=rank(1, r+1), w);
            p[p[nw].ch[0]].rev ^= 1;
        }
        inline void Rotate(int l, int r, int t) { //rotate the elements in range[l,r] t steps
            if (l==r||!(t%=((++r) - (++l) + 1))) return;
            int w; splay(w=rank(1, l-1), 1); 
            int nw; splay(nw=rank(1, r+1), w);
            int nnw; splay(nnw=rank(p[nw].ch[0], r-l-t+1), nw); 
            int nnnw; splay(nnnw=rank(p[nnw].ch[1], t), nnw); 
            p[nw].ch[0] = nnnw; p[nnnw].ch[1] = nnw; p[nnw].ch[1] = 0;
            p[nnw].fa = nnnw; p[nnnw].fa = nw;
            maintain(nnw); maintain(nnnw); 
        }
    private:
        inline void PushDown(int w) {
            if (p[w].delta) {
                p[w].mn += p[w].delta; p[w].val += p[w].delta;
                p[p[w].ch[1]].delta += p[w].delta;
                p[p[w].ch[0]].delta += p[w].delta;
                p[w].delta = 0;
            }
            if (p[w].rev) {
                swap(p[w].ch[0], p[w].ch[1]); p[w].rev = 0;
                p[p[w].ch[0]].rev ^= 1; p[p[w].ch[1]].rev ^= 1;
            }
        }
        inline void maintain(int w) {
            p[w].mn = p[w].val; p[w].sz = p[p[w].ch[0]].sz + p[p[w].ch[1]].sz + 1;
            if (p[w].ch[0]) PushDown(p[w].ch[0]), p[w].mn = min(p[w].mn, p[p[w].ch[0]].mn);
            if (p[w].ch[1]) PushDown(p[w].ch[1]), p[w].mn = min(p[w].mn, p[p[w].ch[1]].mn); 
        }
        inline void rotate(int w) { //rotate w to its father
            int f=p[w].fa,t=p[f].ch[1]==w,ff=p[f].fa; 
            p[f].ch[t] = p[w].ch[t^1]; p[p[w].ch[t^1]].fa = f;
            p[w].ch[t^1] = f; p[w].fa = p[f].fa; p[f].fa = w; 
            if (ff != f) p[ff].ch[p[ff].ch[1]==f] = w;
            maintain(f); maintain(w);
        }
        inline void splay(int w, int pur) { //splay w to pur's son
            if (w == pur) return;
            for (int f,ff;f=p[w].fa,p[w].fa!=pur;) {
                ((ff=p[f].fa) == pur)? rotate(w):
                (((p[f].ch[1]==w)^(p[ff].ch[1]==f))?rotate(w),rotate(f):rotate(f),rotate(w));
            }
        }
        int rank(int w, int t) { //function rank is needed to be called before each splay operation to push down tags
            PushDown(w); if (t<=0) return w; int szt = p[p[w].ch[0]].sz;
            if (szt >= t) return rank(p[w].ch[0], t);
            else if (szt + 1 == t) return w;
            else return rank(p[w].ch[1], t-1-szt);
        }
}SP; 
  
int main() {
    int n = read(); char opt[10]; 
    for (int i=1;i<=n;i++) SP.insert(i-1, read());
    for (int m=read(),l,r,x;m;--m) {
        scanf("%s",opt+1);
        if (opt[1] == 'A') {
            l = read(); r = read();
            SP.add(l, r, read());
        } else if (opt[1] == 'R' && opt[4] == 'E') {
            l = read(); r = read();
            SP.reverse(l, r);
        } else if (opt[1] == 'R') {
            l = read(); r = read();
            SP.Rotate(l, r, read());
        } else if (opt[1] == 'I') {
            l = read(); r = read();
            SP.insert(l, r);
        } else if (opt[1] == 'D') {
            SP.remove(read());
        } else {
            l = read(); r = read();
            printf("%d\n",SP.query(l,r));
        } 
    }
    return 0;
}

【模板库】原根

参考例题:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1135
时间复杂度:能跑1e9
相关限制:此份代码仅能求素数的原根,合数的原根还需要求一个欧拉函数
参考代码:

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
inline int read() {
    char c=getchar(); int f=1,ret=0;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret * f;
}
 
inline int Get_Primitive_Root(int w) {
    vector<int> pri;
    for (int i=2,lim=ceil(sqrt(w)),cur=w-1;i<lim;i++) {
        if (cur % i == 0) {
            pri.push_back(i);
            while (cur % i == 0) 
                cur /= i;
        }
        if (cur > 1 && i == lim - 1) 
            pri.push_back(cur);
    }
    static auto Pow = [](int w, int t, int MOD) {
        int ret = 1;
        for (;t;t>>=1,w=(LL)w*w%MOD) 
            if (t & 1) ret = (LL)ret * w % MOD;
        return ret;
    };
    if (!pri.size()) return 2;
    for (int i=2;i<=w;i++) {
        for (int j=pri.size()-1;~j;j--) {
            if (Pow(i,w/pri[j],w) == 1) break;
            if (!j) return i;
        }
    }
}
 
int main() {
    printf("%d\n",Get_Primitive_Root(read())); 
    return 0;
}

【51NOD 1135】原根

相关链接

题目传送门:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1135
神犇题解Ⅰ:http://blog.csdn.net/u013486414/article/details/47781857
神犇题解Ⅱ:http://littleclown.github.io/2016/05/16/Study-Math-Mod-Root/

解题报告

就是一个求原根的模板题
相关的证明在这里:http://blog.csdn.net/zhang20072844/article/details/11541133

值得注意的是,验证原根现在可以做到$O(logn)$了
不过找原根的复杂度似乎没有比较紧的上界?
wiki上给出了这样一个上界:$O(n^{0.499})$,但$n$要大于$e^{e^{24}}$,所以对于OI题没什么用QwQ
不过一般来讲,质数的原根都比较小,就直接枚举加验证啦!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
inline int read() {
    char c=getchar(); int f=1,ret=0;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret * f;
}
 
inline int Get_Primitive_Root(int w) {
    vector<int> pri;
    for (int i=2,lim=ceil(sqrt(w)),cur=w-1;i<lim;i++) {
        if (cur % i == 0) {
            pri.push_back(i);
            while (cur % i == 0) 
                cur /= i;
        }
        if (cur > 1 && i == lim - 1) 
            pri.push_back(cur);
    }
    static auto Pow = [](int w, int t, int MOD) {
        int ret = 1;
        for (;t;t>>=1,w=(LL)w*w%MOD) 
            if (t & 1) ret = (LL)ret * w % MOD;
        return ret;
    };
    if (!pri.size()) return 2;
    for (int i=2;i<=w;i++) {
        for (int j=pri.size()-1;~j;j--) {
            if (Pow(i,w/pri[j],w) == 1) break;
            if (!j) return i;
        }
    }
}
 
int main() {
    printf("%d\n",Get_Primitive_Root(read())); 
    return 0;
}

【模板库】一般图最大匹配

参考例题:http://uoj.ac/problem/79
参考代码:

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

const int N = 501;
const int MOD = 998244353;

int n,m;

class Maximum_Matchings_in_General_Graph{
	int a[N][N],b[N][N],G[N][N];
	int tot,pat[N],id[N],num[N];
	bool del_x[N],del_y[N];
	public:
		inline void Add_Edge(int u, int v) {
			G[u][v] = a[u][v] = rand() % (MOD - 1) + 1;
			G[v][u] = a[v][u] = -a[u][v];
		}
		inline int solve() {
			for (int i=1;i<=n;i++) id[i] = i;
			Gauss(n);
			for (int i=1;i<=n;i++) 
				if (a[id[i]][id[i]]) 
					num[++tot] = i;
			for (int i=1;i<=tot;i++)
				for (int j=1;j<=tot;j++) 
					a[i][j] = G[num[i]][num[j]];
			Gauss(tot, 1);
			for (int i=1;i<=tot;i++) {
				if (!del_x[i]) {
					for (int j=1;j<=tot;j++) {
						if (!del_x[j] && G[num[i]][num[j]] && b[i][j]) {
							pat[num[i]] = num[j];
							pat[num[j]] = num[i];
							Eliminat(i, j);
							Eliminat(j, i);
							break;
						}
					}
				}
			}
			return tot;
		}
		inline void print() {
			printf("%d\n",tot>>1);
			for (int i=1;i<=n;i++) 
				printf("%d ",pat[i]);
		}
	private:
		inline int Pow(int w, int t) {
			int ret = 1;
			for (;t;t>>=1,w=(LL)w*w%MOD)
				if (t & 1) ret = (LL)ret * w % MOD;
			return ret;
		}
		inline void Gauss(int sz, bool I = 0) {
			for (int i=1;i<=sz;++i) b[i][i] = 1;
			for (int i=1;i<=sz;++i) {
				for (int j=i;j<=sz;++j) {
					if (a[j][i]) {
						swap(id[i], id[j]);
						swap(a[i], a[j]);
						if (I) swap(b[i], b[j]);
						break;
					}
				}
				if (!a[i][i]) continue;
				int inv = Pow(a[i][i], MOD - 2);
				for (int j=1;j<=sz;++j) if (a[i][j]) a[i][j] = (LL)a[i][j] * inv % MOD;
				if (I) for (int j=1;j<=sz;++j) if (b[i][j]) b[i][j] = (LL)b[i][j] * inv % MOD;
				for (int j=1;j<=sz;++j) {
					if (j != i && a[j][i]) {
						LL tmp = a[j][i];
						for (int k=1;k<=sz;++k) if (a[i][k]) a[j][k] = (a[j][k] - tmp * a[i][k]) % MOD;
						if (I) for (int k=1;k<=sz;++k) if (b[i][k]) b[j][k] = (b[j][k] - tmp * b[i][k]) % MOD;	
					}
				}
			}
		}
		inline void Eliminat(int x, int y) {
			del_x[x] = del_y[y] = 1;
			LL inv = Pow(b[x][y], MOD - 2);
			for (int i=1;i<=tot;++i) {
				if (!del_y[i]) {
					LL tmp = b[x][i] * inv % MOD;
					for (int j=1;j<=tot;++j) {
						if (!del_x[j] && b[y][j]) {
							b[i][j] = (b[i][j] - tmp * b[y][j]) % MOD;			
						}
					}
				}
			}
		}
}MMGG;

inline char Read(){
	static const int BUF_SIZE = 1000000; 
	static char buf[BUF_SIZE],*p1=0,*p2=0;
    if (p1 == p2){
    	p1=buf; p2=buf+fread(buf,1,BUF_SIZE,stdin);
		if (p2==p1) return -1;
    } return *p1++;
} 

inline int read(){
	char c=Read(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=Read();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=Read();}
	return ret*f;
}

int main() {
	srand(19260817);
   	n = read(); m = read();
   	for (int i=1,u,v;i<=m;i++) {
		u = read(); v = read();
		MMGG.Add_Edge(u, v);
	}
	MMGG.solve();
	MMGG.print();
	return 0;
}

【模板库】树上点分治

参考例题:http://www.lydsy.com/JudgeOnline/problem.php?id=1468
参考代码:

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

const int N = 40000 + 9;
const int M = N << 1;

int head[N],nxt[M],to[M],cost[M]; 
int n,k,vout;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
} 

inline void Add_Edge(int u, int v, int w) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
	to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}

namespace Node_Decomposition{
	#define ND Node_Decomposition
	const int INF = 10000000;
	int vis[N],dep[N],sum[N];
	int tot,cur,num_node,root;

	void Get_Root(int w, int f) {
		int mx = 0; sum[w] = 1;
		for (int i=head[w];i;i=nxt[i]) {
			if (to[i] != f && !vis[to[i]]) {
				Get_Root(to[i], w);
				mx = max(mx, sum[to[i]]);
				sum[w] += sum[to[i]];
			}
		}
		mx = max(mx, num_node - mx);
		if (mx < cur) root = w, cur = mx;
	}

	void Get_Dep(int w, int f, int bas) {
		for (int i=head[w];i;i=nxt[i]) {
			if (to[i] != f && !vis[to[i]]) {
				dep[++tot] = bas + cost[i];
				Get_Dep(to[i], w, dep[tot]);
			}
		}
	}

	inline int cal(int w, int bas) {
		dep[tot=1] = bas;
		Get_Dep(w, w, bas);
		sort(dep+1, dep+1+tot);
		int r = tot, l = 1, ret = 0;
		while (l < r) {
			while (l < r && dep[l] + dep[r] > k) r--;
			ret += r - l++;
		}
		return ret;
	}

	void solve(int w, int sz) {
		vis[w] = 1; 
		vout += cal(w, 0);
		for (int i=head[w];i;i=nxt[i]) {
			if (!vis[to[i]]) {
				vout -= cal(to[i], cost[i]);
				num_node = sum[to[i]] < sum[w] ? sum[to[i]] : sz - sum[w];
				cur = INF; Get_Root(to[i], w);
				solve(root, num_node);
			}
		}
	}
	
	void solve() {
		num_node = n; cur = INF; 
		Get_Root(1, 1);
		solve(root, n);
	}
}; 

int main() {
	n = read();
	for (int i=1,u,v,w;i<n;i++) {
		u = read(); v = read(); w = read();
		Add_Edge(u, v, w);
	}
	k = read();
	ND::solve();
	printf("%d",vout);
	return 0;
}