刷板题系列

发表于 更新于 分类于 阅读次数：

我已经菜到只能刷板题了 QwQ 。

愈发意识到，会和熟练是两码事，熟练与不熟练的差距真的很大。

半平面交
  • 可用交点 + 叉积判断是否弹栈。
  • 先弹队尾，后弹队首。
  • 加完所有直线后还要用队首来弹队尾。
  • 注意处理平行线。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <cstdio>
#include <algorithm>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;
typedef double ld;

inline bool z (ld x) { return x <= 0 and x >= 0; }
/* struct T { ld x, y; }; */
/* typedef T vector, point; */
struct vector { ld x, y; };
struct point { ld x, y; };
vector operator - (point a, point b) { return {a.x - b.x, a.y - b.y}; }
point operator + (point a, vector b) { return {a.x + b.x, a.y + b.y}; }
int from (vector a) { return a.x > 0 or (z(a.x) and a.y > 0); }
ld cross (vector a, vector b) { return a.x * b.y - a.y * b.x; }
vector operator * (vector a, ld b) { return {a.x * b, a.y * b}; }

static struct {
	inline operator int () { int x; return scanf("%d", &x), x; }
	inline operator point () { point a; return scanf("%lf %lf", &a.x, &a.y), a; }
} read;

struct line { point p; vector v; };
ld cross (line l, point p) { return cross(l.v, p - l.p); }
point inter (line a, line b) {
	return a.p + a.v * (cross(b, a.p) / cross(a.v, b.v));
}

const int maxn = 505;
line li[maxn], q[maxn];
point p[maxn];

int main () {
	int m = read, lp = 0, l = 1, r = 0;
	while (m --) {
		int k = read;
		point a = read, b = a;
		while (-- k) {
			point c = read;
			li[++ lp] = {c, b - c};
			b = c;
		}
		li[++ lp] = {a, b - a};
	}

	std::sort(li + 1, li + lp + 1, [] (line a, line b) {
				if (from(a.v) != from(b.v)) return from(a.v) > from(b.v);
				ld tmp = cross(a.v, b.v);
				if (z(tmp)) return cross(a, b.p) >= 0;
				return tmp <= 0;
			});

	for (int i = 1; i <= lp; i ++) {
		if (i > 1 and z(cross(li[i].v, li[i - 1].v))) continue;
		while (r > l and cross(li[i], p[r]) >= 0) -- r;
		while (r > l and cross(li[i], p[l + 1]) >= 0) ++ l;
		q[++ r] = li[i];
		if (r > l) p[r] = inter(q[r - 1], q[r]);
	}
	while (r > l and cross(q[l], p[r]) >= 0) -- r;
	p[l] = inter(q[r], q[l]);

	ld ans = 0;
	for (int i = l + 2; i <= r; i ++)
		ans += cross(p[i] - p[l], p[i - 1] - p[l]);
	printf("%.3lf\n", ans / 2);
}

扩展卢卡斯
  • 算阶乘之前预处理 mod 以内的前缀积。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <cstdio>
#include <algorithm>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;

static struct {
	inline operator int () { int x; return scanf("%d", &x), x; }
	inline operator ll () { ll x; return scanf("%lld", &x), x; }
} read;

ll power (ll x, ll k, int mod) {
	ll res = 1;
	while (k) {
		if (k & 1) (res *= x) %= mod;
		(x *= x) %= mod;
		k >>= 1;
	}
	return res;
}

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

ll inv (ll a, ll mod) {
	ll x, y;
	exgcd(a, mod, x, y);
	x %= mod;
	return x < 0 ? x + mod : x;
}

struct shit { ll x, y; };
const int maxn = 1000005;
ll pre[maxn];

shit fact (ll n, int p, int k) {
	if (!n) return {1, 0};
	int mod = int(power(p, k, maxn));
	shit res = fact(n / p, p, k);
	res.y += n / p;
	(res.x *= power(pre[mod], n / mod, mod)) %= mod;
	(res.x *= pre[n % mod]) %= mod;
	return res;
}

ll C (ll n, ll m, int p, int k) {
	int mod = int(power(p, k, maxn));
	pre[0] = 1;
	for (int i = 1; i <= mod; i ++)
		pre[i] = i % p ? pre[i - 1] * i % mod : pre[i - 1];
	shit a = fact(n, p, k), b = fact(m, p, k), c = fact(n - m, p, k);
	(a.x *= inv(b.x * c.x % mod, mod)) %= mod;
	a.y -= b.y + c.y;
	return a.x * power(p, a.y, mod);
}

int A[100], M[100], p;
int main () {
	ll n = read, m = read;
	int mod = read;
	for (int i = 2, x = mod; i <= x; i ++)
		if (x % i == 0) {
			M[++ p] = 1;
			int k = 0;
			while (x % i == 0) x /= i, ++ k, M[p] *= i;
			A[p] = int(C(n, m, i, k));
		}
	ll ans = 0;
	for (int i = 1; i <= p; i ++) {
		ll t = mod / M[i];
		(ans += t * inv(t, M[i]) % mod * A[i]) %= mod;
	}
	printf("%lld\n", ans);
}

后缀排序
  • 重新计算 rank 之前要把 rank 拷贝到 tmp 数组用于比较。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <cstdio>
#include <cstring>
#include <algorithm>
#define debug(...) fprintf(stderr, __VA_ARGS__)

const int maxn = 1000005;
char s[maxn];
int sa[maxn], rank[maxn];
int tmp[maxn], t[maxn], sa2[maxn];

void build (int n) {
	for (int i = 1; i <= n; i ++) ++ t[int(s[i])];
	for (int i = 1; i <= 256; i ++) t[i] += t[i - 1];
	for (int i = n; i; i --) sa[t[int(s[i])] --] = i;
	int max = rank[sa[1]] = 1;
	for (int i = 2; i <= n; i ++)
		rank[sa[i]] = s[sa[i]] == s[sa[i - 1]] ? max : ++ max;

	for (int m = 1; max < n; m <<= 1) {
		int p = 0;
		for (int i = 0; i < m; i ++) sa2[++ p] = n - i;
		for (int i = 1; i <= n; i ++) if (sa[i] > m) sa2[++ p] = sa[i] - m;
		std::fill(t, t + max + 1, 0);
		for (int i = 1; i <= n; i ++) ++ t[rank[i]];
		for (int i = 1; i <= max; i ++) t[i] += t[i - 1];
		for (int i = n; i; i --) sa[t[rank[sa2[i]]] --] = sa2[i];
		std::copy(rank, rank + n + 1, tmp);
		max = rank[sa[1]] = 1;
		for (int i = 2; i <= n; i ++)
			rank[sa[i]] = (tmp[sa[i]] == tmp[sa[i - 1]] and
					tmp[sa[i] + m] == tmp[sa[i - 1] + m]) ? max : ++ max;
	}
}

int main () {
	scanf("%s", s + 1);
	int n = int(strlen(s + 1));
	build(n);
	for (int i = 1; i <= n; i ++) printf("%d%c", sa[i], " \n"[i == n]);
}

带花树
  • 缩花的时候必须跳 pre 更新而不能跳并查集。
  • 缩花前先判断两个点是否已经在一个花里了（不判也不影响正确性）。
  • bfs 的点必须是非匹配点。
  • 缩花的时候要把黑点染成白点并加入队列（事实上任何把点染白的操作都要入队）。
  • 白点搜到黑点啥事没有。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <cstdio>
#include <algorithm>
#include <queue>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;

static struct {
	inline operator int () { int x; return scanf("%d", &x), x; }
} read;

const int maxn = 1005;
std::vector<int> G[maxn];
int match[maxn];
int pre[maxn], bas[maxn], col[maxn];
std::queue<int> q;

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

int getbase (int x, int y) {
	static int mark[maxn], mp;
	++ mp;
	while (1) {
		if (!x) std::swap(x, y);
		x = find(x);
		if (mark[x] == mp) return x;
		mark[x] = mp;
		x = pre[x], std::swap(x, y);
	}
}

void blossom (int x, int z, int rt) {
	while (find(x) != rt) {
		int y = match[x];
		if (col[y] == 1) col[y] = 0, q.push(y);
		pre[y] = z, z = y;
		bas[x] = bas[y] = rt;
		x = pre[x];
	}
}

bool bfs (int s, int n) {
	std::fill(col, col + n + 1, -1);
	std::fill(pre, pre + n + 1, 0);
	for (int i = 1; i <= n; i ++) bas[i] = i;
	while (!q.empty()) q.pop();
	col[s] = 0;
	q.push(s);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int v : G[u])
			if (col[v] == -1) {
				if (!match[v]) {
					for (int x = u, y = v; x; x = pre[x])
						match[y] = x, std::swap(match[x], y);
					return 1;
				}
				col[v] = 1;
				col[match[v]] = 0;
				pre[match[v]] = u;
				q.push(match[v]);
			} else if (col[v] == 0) {
				int b = getbase(u, v);
				blossom(u, v, b);
				blossom(v, u, b);
			}
	}
	return 0;
}

int main () {
	int n = read, m = read;
	for (int i = 1; i <= m; i ++) {
		int u = read, v = read;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	int ans = 0;
	for (int i = 1; i <= n; i ++)
		if (!match[i])
			ans += bfs(i, n);
	printf("%d\n", ans);
	for (int i = 1; i <= n; i ++)
		printf("%d ", match[i]);
	puts("");
}

KM
  • 要等队列全部弹空了再更新顶标。
  • 由于是 bfs ，也要记 pre 以便在找到増广路后交错更新，但这里的 pre 只需要记从右边到左边的点，表示的是更新其 slack 的点。
  • 只能找 slack 为零的点尝试増广。
  • l, r 很容易混淆，需要注意。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <cstdio>
#include <algorithm>
#include <queue>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;

static struct {
	inline operator int () { int x; return scanf("%d", &x), x; }
} read;

const int maxn = 505, inf = 1000000000;
int val[maxn][maxn];
bool lvi[maxn], rvi[maxn];
int pre[maxn];
int slk[maxn];
int lma[maxn], rma[maxn], lh[maxn], rh[maxn];
std::queue<int> q;

bool add (int v) {
	rvi[v] = 1;
	if (rma[v]) return lvi[rma[v]] = 1, q.push(rma[v]), 0;
	while (v) std::swap(lma[rma[v] = pre[v]], v);
	return 1;
}

#define check for (int v = 1; v <= n; v ++) if (!rvi[v] and slk[v] == 0 and add(v)) return
void bfs (int s, int n) {
	std::fill(lvi, lvi + n + 1, 0);
	std::fill(rvi, rvi + n + 1, 0);
	std::fill(pre, pre + n + 1, 0);
	std::fill(slk,slk + n + 1, inf);
	while (!q.empty()) q.pop();
	q.push(s);
	lvi[s] = 1;
	while (1) {
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (int v = 1; v <= n; v ++)
				if (!rvi[v]) {
					int dt = lh[u] + rh[v] - val[u][v];
					if (dt <= slk[v]) slk[v] = dt, pre[v] = u;
				}
			check;
		}
		int dt = inf;
		for (int v = 1; v <= n; v ++) if (!rvi[v]) dt = std::min(dt, slk[v]);
		for (int u = 1; u <= n; u ++) if (lvi[u]) lh[u] -= dt;
		for (int v = 1; v <= n; v ++) rvi[v] ? rh[v] += dt : slk[v] -= dt;
		check;
	}
}

int main () {
	int n = read, m = read;
	for (int u = 1; u <= n; u ++)
		for (int v = 1; v <= n; v ++)
			val[u][v] = -inf;
	while (m --) {
		int u = read, v = read, w = read;
		val[u][v] = std::max(val[u][v], w);
	}
	for (int u = 1; u <= n; u ++) {
		lh[u] = -inf;
		for (int v = 1; v <= n; v ++)
			lh[u] = std::max(lh[u], val[u][v]);
	}
	for (int u = 1; u <= n; u ++) bfs(u, n);
	ll ans = 0;
	for (int i = 1; i <= n; i ++) ans += lh[i] + rh[i];
	printf("%lld\n", ans);
	for (int v = 1; v <= n; v ++) printf("%d ", rma[v]);
}

半在线卷积
  • 可以预处理转移数组 \(b\) 的点值表示，从而把两个 log 的瓶颈之一卡成一个 log 。
  • 用 long long 存的话加法就不需要取模，但是不在瓶颈。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <cstdio>
#include <algorithm>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;
typedef unsigned long long ull;

static struct {
	inline operator int () { int x; return scanf("%d", &x), x; }
	template<class T> inline void operator () (T &x) { x = *this; }
} read;

const int maxl = 1 << 18, mod = 998244353;
int R[maxl << 1], G[maxl + 1];

ll power (ll x, int k) {
	if (k < 0) k += mod - 1;
	ll res = 1;
	while (k) {
		if (k & 1) (res *= x) %= mod;
		(x *= x) %= mod;
		k >>= 1;
	}
	return res;
}

void init () {
	for (int n = 1; n <= maxl; n <<= 1) {
		int *r = R + n;
		for (int i = 1; i < n; i ++)
			r[i] = r[i >> 1] >> 1 | (i & 1) * (n >> 1);
	}
	ll g = power(3, (mod - 1) / maxl);
	G[maxl / 2] = 1;
	for (int i = maxl / 2 + 1; i <= maxl; i ++) G[i] = g * G[i - 1] % mod;
	for (int i = maxl / 2 - 1; i; i --) G[i] = G[i << 1];
}

void dft (int *b, int n) {
	static ull a[maxl];
	for (int i = 0; i < n; i ++) a[i] = ull(b[R[n + i]]);
	for (int m = 1; m < n; m <<= 1)
		for (int i = 0; i < n; i += m << 1)
			for (int k = i; k < i + m; k ++) {
				ull x = a[k], y = a[k + m] * ull(G[m + k - i]) % mod;
				a[k] = x + y, a[k + m] = x + mod - y;
			}
	for (int i = 0; i < n; i ++) b[i] = a[i] % mod;
}

void idft (int *a, int n) {
	std::reverse(a + 1, a + n), dft(a, n);
	ll inv = mod - (mod - 1) / n;
	for (int i = 0; i < n; i ++) a[i] = inv * a[i] % mod;
}

const int force = 8;
void solve (int *a, int *b, int *c, int n) {
	static int d[maxl];
	if (n <= force) {
		for (int i = 0; i < n; i ++) {
			for (int j = 1; j <= i; j ++)
				a[i] = (a[i] + 1ll * a[i - j] * b[j]) % mod;
			a[i] = 1ll * a[i] * c[i] % mod;
		}
		return;
	}
	int m = n >> 1;
	solve(a, b, c, m);
	std::copy(a, a + m, d), std::fill(d + m, d + n, 0);
	dft(d, n);
	for (int i = 0; i < n; i ++) d[i] = 1ll * d[i] * b[n + i] % mod;
	idft(d, n);
	for (int i = m; i < n; i ++) (a[i] += d[i]) >= mod ? a[i] -= mod : a[i];
	solve(a + m, b, c + m, m);
}
void Solve (int *a, int *c, int n) {
	static int b[maxl << 1];
	std::copy(a, a + force, b);
	for (int m = force << 1; m <= n; m <<= 1)
		std::copy(a, a + m, b + m), dft(b + m, m);
	std::fill(a, a + n, 0), a[0] = 1;
	solve(a, b, c, n);
}

int a[maxl], c[maxl];
int main () {
	init();
	int n = read, l = 1;
	while (l < n) l <<= 1;
	for (int i = 1; i < n; i ++) read(a[i]);
	for (int i = 0; i < n; i ++) c[i] = 1;
	Solve(a, c, l);
	for (int i = 0; i < n; i ++) printf("%d ", a[i]); puts("");
}

扩展 BSGS
  • \(b \bot \gcd(a, p)\) 时要及时返回无解。
  • 可能不到 \(\sqrt{p}\) 轮幂次就重复了，要及时退出以防 map 内用大的指标覆盖了小的指标（只是求可行解的话就无所谓）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;

static struct {
	inline operator int () { int x; return scanf("%d", &x), x; }
} read;

inline ll power (ll x, int k, int mod) {
	if (k < 0) k += mod - 1;
	ll res = 1;
	while (k) {
		if (k & 1) (res *= x) %= mod;
		(x *= x) %= mod;
		k >>= 1;
	}
	return res;
}

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

int inv (int a, int p) {
	int x, y;
	exgcd(a, p, x, y);
	x %= p;
	return x < 0 ? x + p : x;
}

int exbsgs (int a, int b, int p) {
	int g = std::__gcd(a, p);
	if (g == 1) {
		std::map<int, int> map;
		int s = int(sqrt(p)) + 1, ia = inv(a, p), x = b;
		for (int i = 0; i < s and !map.count(x); i ++)
			map[x] = i, x = 1ll * x * ia % p;
		int A = int(power(a, s, p));
		x = 1;
		for (int i = 0; i < s; i ++)
			if (map.count(x))
				return i * s + map[x];
			else
				x = 1ll * x * A % p;
		return -1;
	}
	if (b % g) return -1;
	b /= g, p /= g;
	int x = exbsgs(a, 1ll * b * inv(a / g, p) % p, p);
	return x == -1 ? -1 : x + 1;
}

int main () {
	while (1) {
		int a = read, p = read, b = read;
		if (!p) break;
		int x = exbsgs(a, b, p);
		if (x == -1) puts("No Solution");
		else printf("%d\n", x);
	}
}

min25 筛
  • 不需要单独维护质数的函数前缀和，由于需要的质数都不超过根号，直接在 \(g\) 上面就能查到，并且有 id(p) == p 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
#include <cmath>
#include <algorithm>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;

static struct {
	inline operator ll () { ll x; return scanf("%lld", &x), x; }
} read;

const int maxm = 200005, mod = 1000000007;
ll w[maxm], n;
int sq, m;

inline ll id (ll x) { return x <= sq ? x : m - n / x + 1; }
inline ll s (ll x) { x %= mod; return x * (x + 1) / 2 % mod; }

int nop[maxm], pr[maxm], pp;
ll g1[maxm], g2[maxm], g[maxm];

ll S (ll x, int j) {
	if (pr[j] >= x) return 0;
	ll res = g[id(x)] + mod - g[pr[j]];
	for (int i = j + 1; i <= pp and pr[i] <= x / pr[i]; i ++) {
		ll v = pr[i];
		for (int k = 1; v <= x; k ++) {
			(res += (pr[i] ^ k) * (S(x / v, i) + (k > 1))) %= mod;
			v *= pr[i];
		}
	}
	return res;
}

int main () {
	sq = int(std::sqrt(n = read));
	for (ll l = 1, r; l <= n; l = r + 1) {
		w[++ m] = r = n / (n / l);
		g1[m] = r - 1, g2[m] = s(r) - 1;
	}
	for (int i = 2; i <= sq; i ++)
		if (!nop[i]) {
			pr[++ pp] = i;
			if (i <= sq / i)
				for (int j = i * i; j <= sq; j += i)
					nop[j] = 1;
			for (int j = m; i <= w[j] / i; j --) {
				int k1 = int(id(w[j] / i)), k2 = pr[pp - 1];
				(g1[j] += (mod - 1) * (g1[k1] + mod - g1[k2])) %= mod;
				(g2[j] += (mod - i) * (g2[k1] + mod - g2[k2])) %= mod;
			}
		}
	for (int j = 1; j <= m; j ++) g[j] = g2[j] + mod - g1[j] + (w[j] >= 2) * 2;
	printf("%lld\n", (S(n, 0) + 1) % mod);
}

pollard-rho / miller-rabin
  • miller-rabin 选 9 个质数 (2 到 23) 就可以判断 \(10^{18}\) 内所有数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <cstdio>
#include <algorithm>
#include <random>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;
typedef long double ld;

static struct {
	inline operator int () { int x; return scanf("%d", &x), x; }
	inline operator ll () { ll x; return scanf("%lld", &x), x; }
} read;

inline ll mul (ll a, ll b, ll c) {
	ll t = a * b - ll(ld(a) / c * b + 0.5L) * c;
	return t < 0 ? t + c : t;
}

ll power (ll x, ll k, ll m) {
	ll r = 1;
	while (k) {
		if (k & 1) r = mul(r, x, m);
		x = mul(x, x, m);
		k >>= 1;
	}
	return r;
}

ll check (ll n, int p) {
	ll k = n - 1, t = power(p, k, n);
	if (t != 1) return 0;
	while (!(k & 1) and t == 1) {
		t = power(p, k >>= 1, n);
		if (t != 1 and t != n - 1) return 0;
	}
	return 1;
}

ll isp (ll n) {
	int pr[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
	for (int p : pr) if (n == p) return 1;
	for (int p : pr) if (n % p == 0) return 0;
	for (int p : pr) if (!check(n, p)) return 0;
	return 1;
}

ll nxt (ll a, ll c, ll n) {
	ll t = mul(a, a, n) + c;
	return t >= n ? t - n : t;
}

std::mt19937_64 e(2333);
ll getd (ll n) {
	if (n == 4) return 2;
	std::uniform_int_distribution<ll> r(0, n - 1);
	ll c = r(e), a = nxt(r(e), c, n), b = nxt(a, c, n);
	int lim = 1;
	while (a != b) {
		ll v = 1;
		for (int k = 0; k < lim and a != b; k ++) {
			v = mul(v, std::abs(a - b), n);
			a = nxt(a, c, n);
			b = nxt(b, c, n);
			b = nxt(b, c, n);
		}
		ll g = std::__gcd(v, n);
		if (g > 1) return g;
		if (lim < 128) lim <<= 1;
	}
	return getd(n);
}

ll max;
void factor (ll n) {
	if (n == 1 or isp(n)) return max = std::max(max, n), void();
	ll d = getd(n);
	while (n % d == 0) n /= d;
	factor(n), factor(d);
}

int main () {
	int T = read;
	while (T --) {
		ll n = read;
		max = 0, factor(n);
		if (max == n) puts("Prime");
		else printf("%lld\n", max);
	}
}

万能欧几里得
  • \(n\) 在辗转相除后会到 \(lim^2\) 级别。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <cstdio>
#include <algorithm>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;

static struct {
	inline operator int () { int x; return scanf("%d", &x), x; }
} read;

const int mod = 998244353;
struct node {
	ll x, y, s;
	ll a1, a2, a3;
} Z = {0, 0, 0, 0, 0, 0};

node operator + (node a, node b) {
	node c;
	c.a1 = (a.a1 + b.a1 + a.y * b.x) % mod;
	c.a2 = (a.a2 + b.a2 + a.y * a.y % mod * b.x + 2 * a.y * b.a1) % mod;
	c.a3 = (a.a3 + b.a3 + a.x * b.a1 + a.y * b.s + a.x * a.y % mod * b.x) % mod;
	c.x = (a.x + b.x) % mod;
	c.y = (a.y + b.y) % mod;
	c.s = (a.s + b.s + a.x * b.x) % mod;
	return c;
}

node operator * (node a, ll k) {
	node r = Z;
	while (k) {
		if (k & 1) r = r + a;
		a = a + a;
		k >>= 1;
	}
	return r;
}

node F (int a, int b, int c, ll n, node X, node Y) { // 从 0 开始标号！
	if (n == 0) return Y * (b / c) + X;
	if (b >= c) return Y * (b / c) + F(a, b % c, c, n, X, Y);
	if (a >= c) return X + F(a % c, b + a % c, c, n - 1, Y * (a / c) + X, Y);
	ll t = (a * n + b) / c;
	if (t == 0) return X * (n + 1);
	return F(c, a + c - b - 1, a, t - 1, Y, X) + X * (n - (t * c - b - 1) / a);
}

int main () {
	int T = read;
	node X = {1, 0, 0, 0, 0, 0};
	node Y = {0, 1, 0, 0, 0, 0};
	while (T --) {
		int n = read, a = read, b = read, c = read;
		node d = F(a, b, c, n, X, Y);
		printf("%lld %lld %lld\n", d.a1, d.a2, d.a3);
	}
}

来一个从 1 开始标号的简洁版本（适合全文背诵）：

1
2
3
4
5
6
7
8
9
10
node F (int a, int b, int c, ll n, node X, node Y) { // 从 1 标号 (b < c) (a < c)
	ll t = (a * n + b) / c;
	return !t ? X * n :
		X * ((c - b - 1) / a) + Y +
		F(c % a, (c - b - 1) % a, a, t - 1, X * (c / a) + Y, X) +
		X * (n - (c * t - b - 1) / a);
}
inline node f (int a, int b, int c, ll n, node X, node Y) {
	return Y * (b / c) + F(a % c, b % c, c, n, Y * (a / c) + X, Y);
}

多项式求逆

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <cstdio>
#include <algorithm>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;
typedef unsigned long long ull;

static struct {
	inline operator int () { int x; return scanf("%d", &x), x; }
	template<class T> inline void operator () (T &x) { x = *this; }
} read;

const int maxl = 1 << 18, mod = 998244353;
int R[maxl << 1], G[maxl];

inline ll power (ll x, int k) {
	if (k < 0) k += mod - 1;
	ll res = 1;
	while (k) {
		if (k & 1) (res *= x) %= mod;
		(x *= x) %= mod;
		k >>= 1;
	}
	return res;
}

void init () {
	for (int n = 1; n <= maxl; n <<= 1) {
		int *r = R + n;
		for (int i = 1; i < n; i ++)
			r[i] = r[i >> 1] >> 1 | (i & 1) * (n >> 1);
	}
	ll g = power(3, (mod - 1) / maxl);
	G[maxl / 2] = 1;
	for (int i = maxl / 2 + 1; i < maxl; i ++) G[i] = G[i - 1] * g % mod;
	for (int i = maxl / 2 - 1; i; i --) G[i] = G[i << 1];
}

void dft (int *b, int n) {
	static ull a[maxl];
	for (int i = 0; i < n; i ++) a[i] = ull(b[R[n + i]]);
	for (int m = 1; m < n; m <<= 1)
		for (int i = 0; i < n; i += m << 1)
			for (int k = i; k < i + m; k ++) {
				ull x = a[k], y = a[k + m] * ull(G[m + k - i]) % mod;
				a[k] = x + y;
				a[k + m] = x + mod - y;
			}
	for (int i = 0; i < n; i ++) b[i] = a[i] % mod;
}

void idft (int *a, int n) {
	std::reverse(a + 1, a + n), dft(a, n);
	ll in = mod - (mod - 1) / n;
	for (int i = 0; i < n; i ++) a[i] = in * a[i] % mod;
}

void polyinv (int *a, int n) {
	static int t[maxl], b[maxl];
	b[0] = int(power(a[0], -1));
	for (int m = 2; m <= n; m <<= 1) {
		std::copy(a, a + m, t);
		std::fill(t + m, t + (m << 1), 0);
		dft(t, m << 1), dft(b, m << 1);
		for (int i = 0; i < (m << 1); i ++)
			b[i] = ll(2 + ll(mod - t[i]) * b[i]) % mod * b[i] % mod;
		idft(b, m << 1);
		std::fill(b + m, b + (m << 1), 0);
	}
	std::copy(b, b + n, a);
}

int a[maxl];
int main () {
	init();
	int n = read, l = 1;
	while (l < n) l <<= 1;
	for (int i = 0; i < n; i ++) read(a[i]);
	polyinv(a, l);
	for (int i = 0; i < n; i ++) printf("%d ", a[i]); puts("");
}

FFT

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
#include <algorithm>
#include <complex>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;
typedef std::complex<double> com;

static struct {
	inline operator int () { int x; return scanf("%d", &x), x; }
	inline operator double () { double x; return scanf("%lf", &x), x; }
} read;

const int maxl = 1 << 21;
int R[maxl << 1];
com W[maxl];

void init () {
	for (int n = 1; n <= maxl; n <<= 1) {
		int *r = R + n;
		for (int i = 1; i < n; i ++)
			r[i] = r[i >> 1] >> 1 | (i & 1) * (n >> 1);
	}
	for (int i = 0; i < maxl / 2; i ++) W[maxl / 2 + i] =
		com(std::cos(2 * M_PI / maxl * i), std::sin(2 * M_PI / maxl * i));
	for (int i = maxl / 2 - 1; i; i --) W[i] = W[i << 1];
}

void dft (com *a, int n) {
	for (int i = 0; i < n; i ++) if (i < R[n + i]) std::swap(a[i], a[R[n + i]]);
	for (int m = 1; m < n; m <<= 1)
		for (int i = 0; i < n; i += m << 1)
			for (int k = i; k < i + m; k ++) {
				com x = a[k], y = a[k + m] * W[m + k - i];
				a[k] = x + y, a[k + m] = x - y;
			}
}

void idft (com *a, int n) {
	std::reverse(a + 1, a + n), dft(a, n);
	for (int i = 0; i < n; i ++) a[i] /= n;
}

com a[maxl], b[maxl];
int main () {
	init();
	int n = read, m = read, l = 1;
	while (l < n + m + 1) l <<= 1;
	for (int i = 0; i <= n; i ++) a[i] = read;
	for (int i = 0; i <= m; i ++) b[i] = read;
	dft(a, l), dft(b, l);
	for (int i = 0; i < l; i ++) a[i] *= b[i];
	idft(a, l);
	for (int i = 0; i <= n + m; i ++) printf("%d ", int(a[i].real() + 0.5));
}

回文树
  • 与 SAM 不同的是，回文树的比较总是要拿 len 和原串 s 作为依据，而不是仅仅判断 ch[u][x] 是否有值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>
#include <cstring>
#include <algorithm>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;

const int maxn = 500005, maxc = 26;
char s[maxn];
int fail[maxn], ch[maxn][maxc], len[maxn], dep[maxn], cp = 2;

int insert (int pre, int i) {
	int x = s[i] - 'a';
	while (s[i - len[pre] - 1] != s[i]) pre = fail[pre];
	int &now = ch[pre][x];
	if (!now) {
		now = ++ cp;
		len[now] = len[pre] + 2;
		if ((pre = fail[pre]))
			while (s[i - len[pre] - 1] != s[i]) pre = fail[pre];
		fail[now] = ch[pre][x] ? ch[pre][x] : 2;
		dep[now] = dep[fail[now]] + 1;
	}
	return now;
}

int main () {
	scanf("%s", s + 1);
	int n = int(strlen(s + 1));
	len[1] = -1;
	fail[2] = 1;
	for (int i = 1, ans = 0, las = 2; i <= n; i ++) {
		s[i] = (s[i] - 'a' + ans) % maxc + 'a';
		las = insert(las, i);
		printf("%d%c", ans = dep[las], " \n"[i == n]);
	}
}

Manacher

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <cstdio>
#include <cstring>
#include <algorithm>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;

const int maxn = 22000005;
char s[maxn];
int h[maxn];

void manacher (int n) {
	int M = 1, R = 1;
	h[1] = 1;
	for (int i = 2; i <= n; i ++) {
		h[i] = std::min(h[M + M - i], R - i + 1);
		while (s[i - h[i]] == s[i + h[i]]) ++ h[i];
		if (i + h[i] - 1 > R)
			M = i, R = i + h[i] - 1;
	}
}

int main () {
	scanf("%s", s + 1);
	int n = int(strlen(s + 1));
	for (int i = n; i; i --)
		s[i << 1] = s[i], s[i << 1 | 1] = '#';
	s[0] = '$', s[1] = '#';
	manacher(n << 1 | 1);
	int ans = 0;
	for (int i = 1; i <= (n << 1 | 1); i ++) ans = std::max(ans, h[i] - 1);
	printf("%d\n", ans);
}

二次剩余 Cipolla
  • 注意先用欧拉准贼判断无解，以及特判 0 的解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
#include <algorithm>
#include <random>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;

static struct {
	inline operator int () { int x; return scanf("%d", &x), x; }
	template<class T> inline void operator () (T &x) { x = *this; }
} read;

int I2, P;
struct com {
	int x, y;
	com (int x, int y = 0): x(x), y(y) { }
};
inline com operator * (com a, com b) {
	return com((1ll * a.x * b.x + 1ll * a.y * b.y % P * I2) % P,
			(1ll * a.x * b.y + 1ll * a.y * b.x) % P);
}

com power (com x, int k) {
	com r = 1;
	while (k) {
		if (k & 1) r = r * x;
		x = x * x;
		k >>= 1;
	}
	return r;
}

int main () {
	int T = read;
	std::mt19937 e(233);
	while (T --) {
		int n = read;
		read(P);
		if (n == 0) {
			puts("0");
			continue;
		}
		if (power(n, (P - 1) >> 1).x == P - 1) {
			puts("Hola!");
			continue;
		}
		std::uniform_int_distribution<int> r(0, P - 1);
		int a = r(e);
		while (power((1ll * a * a - n + P) % P, (P - 1) >> 1).x == 1) a = r(e);
		I2 = (1ll * a * a - n + P) % P;
		int x = power(com(a, 1), (P + 1) >> 1).x, y = P - x;
		if (x > y) std::swap(x, y);
		printf("%d %d\n", x, y);
	}
}