voidquick_sort(int q[], int l, int r) { if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1]; while (i < j) { do i ++ ; while (q[i] < x); do j -- ; while (q[j] > x); if (i < j) swap(q[i], q[j]); } quick_sort(q, l, j), quick_sort(q, j + 1, r); }
归并排序算法模板 —— 模板题 AcWing 787. 归并排序
voidmerge_sort(int q[], int l, int r) { if (l >= r) return;
int mid = l + r >> 1; merge_sort(q, l, mid); merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1; while (i <= mid && j <= r) if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ]; else tmp[k ++ ] = q[j ++ ];
while (i <= mid) tmp[k ++ ] = q[i ++ ]; while (j <= r) tmp[k ++ ] = q[j ++ ];
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j]; }
整数二分算法模板 —— 模板题 AcWing 789. 数的范围
boolcheck(int x){/* ... */} // 检查 x 是否满足某种性质
// 区间 [l, r] 被划分成 [l, mid] 和 [mid + 1, r] 时使用： intbsearch_1(int l, int r) { while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; // check()判断 mid 是否满足性质 else l = mid + 1; } return l; } // 区间 [l, r] 被划分成 [l, mid - 1] 和 [mid, r] 时使用： intbsearch_2(int l, int r) { while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) l = mid; else r = mid - 1; } return l; } ``````
doublebsearch_3(double l, double r) { constdouble eps = 1e-6; // eps 表示精度，取决于题目对精度的要求 while (r - l > eps) { double mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; } return l; } ``````
## 高精度加法 —— 模板题 AcWing 791. 高精度加法 ```c++ // C = A + B, A >= 0, B >= 0 vector<int> add(vector<int> &A, vector<int> &B) { if (A.size() < B.size()) returnadd(B, A);
vector<int> C; int t = 0; for (int i = 0; i < A.size(); i ++ ) { t += A[i]; if (i < B.size()) t += B[i]; C.push_back(t % 10); t /= 10; }
if (t) C.push_back(t); return C; } ``````
## 高精度减法 —— 模板题 AcWing 792. 高精度减法 ```c++ // C = A - B, 满足 A >= B, A >= 0, B >= 0 vector<int> sub(vector<int> &A, vector<int> &B) { vector<int> C; for (int i = 0, t = 0; i < A.size(); i ++ ) { t = A[i] - t; if (i < B.size()) t -= B[i]; C.push_back((t + 10) % 10); if (t < 0) t = 1; else t = 0; }
// C = A * b, A >= 0, b >= 0 vector<int> mul(vector<int> &A, int b) { vector<int> C;
int t = 0; for (int i = 0; i < A.size() || t; i ++ ) { if (i < A.size()) t += A[i] * b; C.push_back(t % 10); t /= 10; }
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C; }
高精度除以低精度 —— 模板题 AcWing 794. 高精度除法
// A / b = C ... r, A >= 0, b > 0 vector<int> div(vector<int> &A, int b, int &r) { vector<int> C; r = 0; for (int i = A.size() - 1; i >= 0; i -- ) { r = r * 10 + A[i]; C.push_back(r / b); r %= b; } reverse(C.begin(), C.end()); while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; }
// 二分求出 x 对应的离散化的值 intfind(int x)// 找到第一个大于等于 x 的位置 { int l = 0, r = alls.size() - 1; while (l < r) { int mid = l + r >> 1; if (alls[mid] >= x) r = mid; else l = mid + 1; } return r + 1; // 映射到 1, 2, ...n }
int st = -2e9, ed = -2e9; for (auto seg : segs) if (ed < seg.first) { if (st != -2e9) res.push_back({st, ed}); st = seg.first, ed = seg.second; } else ed = max(ed, seg.second);
if (st != -2e9) res.push_back({st, ed});
segs = res; }
单链表 —— 模板题 AcWing 826. 单链表
// head 存储链表头，e [] 存储节点的值，ne [] 存储节点的 next 指针，idx 表示当前用到了哪个节点 int head, e[N], ne[N], idx;
// 初始化 voidinit() { head = -1; idx = 0; } // 在链表头插入一个数 a voidinsert(int a) { e[idx] = a, ne[idx] = head, head = idx ++ ; }
// 将头结点删除，需要保证头结点存在 voidremove() { head = ne[head]; }
双链表 —— 模板题 AcWing 827. 双链表
// e [] 表示节点的值，l [] 表示节点的左指针，r [] 表示节点的右指针，idx 表示当前用到了哪个节点 int e[N], l[N], r[N], idx;
int tt = 0; for (int i = 1; i <= n; i ++ ) { while (tt && check(stk[tt], i)) tt -- ; stk[ ++ tt] = i; }
单调队列 —— 模板题 AcWing 154. 滑动窗口
常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1; for (int i = 0; i < n; i ++ ) { while (hh <= tt && check_out(q[hh])) hh ++ ; // 判断队头是否滑出窗口 while (hh <= tt && check(q[tt], i)) tt -- ; q[ ++ tt] = i; }
KMP —— 模板题 AcWing 831. KMP 字符串
// s [] 是长文本，p [] 是模式串，n 是 s 的长度，m 是 p 的长度 求模式串的Next数组： for (int i = 2, j = 0; i <= m; i ++ ) { while (j && p[i] != p[j + 1]) j = ne[j]; if (p[i] == p[j + 1]) j ++ ; ne[i] = j; }
// 匹配 for (int i = 1, j = 0; i <= n; i ++ ) { while (j && s[i] != p[j + 1]) j = ne[j]; if (s[i] == p[j + 1]) j ++ ; if (j == m) { j = ne[j]; // 匹配成功后的逻辑 } }
Trie 树 —— 模板题 AcWing 835. Trie 字符串统计
int son[N][26], cnt[N], idx; // 0 号点既是根节点，又是空节点 // son [][] 存储树中每个节点的子节点 // cnt [] 存储以每个节点结尾的单词数量
// 插入一个字符串 voidinsert(char *str) { int p = 0; for (int i = 0; str[i]; i ++ ) { int u = str[i] - 'a'; if (!son[p][u]) son[p][u] = ++ idx; p = son[p][u]; } cnt[p] ++ ; } // 查询字符串出现的次数 intquery(char *str) { int p = 0; for (int i = 0; str[i]; i ++ ) { int u = str[i] - 'a'; if (!son[p][u]) return0; p = son[p][u]; } return cnt[p]; }
并查集 —— 模板题 AcWing 836. 合并集合, AcWing 837. 连通块中点的数量
(1)朴素并查集：
int p[N]; //存储每个点的祖宗节点
// 返回 x 的祖宗节点 intfind(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; }
// 初始化，假定节点编号是 1~n for (int i = 1; i <= n; i ++ ) p[i] = i;
// 合并 a 和 b 所在的两个集合： p[find(a)] = find(b);
(2)维护size的并查集：
int p[N], size[N]; //p [] 存储每个点的祖宗节点, size [] 只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
// 返回 x 的祖宗节点 intfind(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; }
// 初始化，假定节点编号是 1~n for (int i = 1; i <= n; i ++ ) { p[i] = i; size[i] = 1; }
// 合并 a 和 b 所在的两个集合： size[find(b)] += size[find(a)]; p[find(a)] = find(b);
(3)维护到祖宗节点距离的并查集：
int p[N], d[N]; //p [] 存储每个点的祖宗节点, d [x] 存储 x 到 p [x] 的距离
// 返回 x 的祖宗节点 intfind(int x) { if (p[x] != x) { int u = find(p[x]); d[x] += d[p[x]]; p[x] = u; } return p[x]; }
// 初始化，假定节点编号是 1~n for (int i = 1; i <= n; i ++ ) { p[i] = i; d[i] = 0; }
// 合并 a 和 b 所在的两个集合： p[find(a)] = find(b); d[find(a)] = distance; // 根据具体问题，初始化 find(a)的偏移量
堆 —— 模板题 AcWing 838. 堆排序, AcWing 839. 模拟堆
// h [N] 存储堆中的值, h [1] 是堆顶，x 的左儿子是 2x, 右儿子是 2x + 1 // ph [k] 存储第 k 个插入的点在堆中的位置 // hp [k] 存储堆中下标是 k 的点是第几个插入的 int h[N], ph[N], hp[N], size;
// 交换两个点，及其映射关系 voidheap_swap(int a, int b) { swap(ph[hp[a]],ph[hp[b]]); swap(hp[a], hp[b]); swap(h[a], h[b]); }
voiddown(int u) { int t = u; if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2; if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1; if (u != t) { heap_swap(u, t); down(t); } }
voidup(int u) { while (u / 2 && h[u] < h[u / 2]) { heap_swap(u, u / 2); u >>= 1; } }
// O(n)建堆 for (int i = n / 2; i; i -- ) down(i);
一般哈希 —— 模板题 AcWing 840. 模拟散列表
(1) 拉链法 int h[N], e[N], ne[N], idx;
// 向哈希表中插入一个数 voidinsert(int x) { int k = (x % N + N) % N; e[idx] = x; ne[idx] = h[k]; h[k] = idx ++ ; }
// 在哈希表中查询某个数是否存在 boolfind(int x) { int k = (x % N + N) % N; for (int i = h[k]; i != -1; i = ne[i]) if (e[i] == x) returntrue;
returnfalse; }
(2) 开放寻址法 int h[N];
// 如果 x 在哈希表中，返回 x 的下标；如果 x 不在哈希表中，返回 x 应该插入的位置 intfind(int x) { int t = (x % N + N) % N; while (h[t] != null && h[t] != x) { t ++ ; if (t == N) t = 0; } return t; }
字符串哈希 —— 模板题 AcWing 841. 字符串哈希
核心思想：将字符串看成 P 进制数，P 的经验值是 131 或 13331，取这两个值的冲突概率低 小技巧：取模的数用 2^64，这样直接用 unsigned long long 存储，溢出的结果就是取模的结果
typedefunsignedlonglong ULL; ULL h[N], p[N]; // h [k] 存储字符串前 k 个字母的哈希值, p [k] 存储 P^k mod 2^64
// 初始化 p[0] = 1; for (int i = 1; i <= n; i ++ ) { h[i] = h[i - 1] * P + str[i]; p[i] = p[i - 1] * P; }
for (int i = 0; i < n - 1; i ++ ) { int t = -1; // 在还未确定最短路的点中，寻找距离最小的点 for (int j = 1; j <= n; j ++ ) if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
// 如果第 n 次迭代仍然会松弛三角不等式，就说明存在一条长度是 n+1 的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。 for (int i = 0; i < n; i ++ ) { for (int j = 0; j < m; j ++ ) { int a = edges[j].a, b = edges[j].b, w = edges[j].w; if (dist[b] > dist[a] + w) dist[b] = dist[a] + w; } }
if (dist[n] > 0x3f3f3f3f / 2) return-1; return dist[n]; }
时间复杂度 平均情况下 O(m)O(m)，最坏情况下 O(nm)O(nm), nn 表示点数，mm 表示边数
int n; // 总点数 int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边 int dist[N]; // 存储每个点到 1 号点的最短距离 bool st[N]; // 存储每个点是否在队列中
// 求 1 号点到 n 号点的最短路距离，如果从 1 号点无法走到 n 号点则返回-1 intspfa() { memset(dist, 0x3f, sizeof dist); dist[1] = 0;
queue<int> q; q.push(1); st[1] = true;
while (q.size()) { auto t = q.front(); q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; if (!st[j]) // 如果队列中已存在 j，则不需要将 j 重复插入 { q.push(j); st[j] = true; } } } }
if (dist[n] == 0x3f3f3f3f) return-1; return dist[n]; }
spfa 判断图中是否存在负环 —— 模板题 AcWing 852. spfa 判断负环
时间复杂度是 O(nm)O(nm), nn 表示点数，mm 表示边数
int n; // 总点数 int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边 int dist[N], cnt[N]; // dist [x] 存储 1 号点到 x 的最短距离，cnt [x] 存储 1 到 x 的最短路中经过的点数 bool st[N]; // 存储每个点是否在队列中
// 如果存在负环，则返回 true，否则返回 false。 boolspfa() { // 不需要初始化 dist 数组 // 原理：如果某条最短路径上有 n 个点（除了自己），那么加上自己之后一共有 n+1 个点，由抽屉原理一定有两个点相同，所以存在环。 queue<int> q; for (int i = 1; i <= n; i ++ ) { q.push(i); st[i] = true; } while (q.size()) { auto t = q.front(); q.pop(); st[t] = false; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; cnt[j] = cnt[t] + 1; if (cnt[j] >= n) returntrue; // 如果从 1 号点到 x 的最短路中包含至少 n 个点（不包括自己），则说明存在环 if (!st[j]) { q.push(j); st[j] = true; } } } } returnfalse; }
floyd 算法 —— 模板题 AcWing 854. Floyd 求最短路
时间复杂度是 O(n3)O(n3), nn 表示点数
初始化： for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) if (i == j) d[i][j] = 0; else d[i][j] = INF;
// 算法结束后，d [a][b] 表示 a 到 b 的最短距离 voidfloyd() { for (int k = 1; k <= n; k ++ ) for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); }
朴素版 prim 算法 —— 模板题 AcWing 858. Prim 算法求最小生成树
时间复杂度是 O(n2+m)O(n2+m), nn 表示点数，mm 表示边数
int n; // n 表示点数 int g[N][N]; // 邻接矩阵，存储所有边 int dist[N]; // 存储其他点到当前最小生成树的距离 bool st[N]; // 存储每个点是否已经在生成树中
int res = 0; for (int i = 0; i < n; i ++ ) { int t = -1; for (int j = 1; j <= n; j ++ ) if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j; if (i && dist[t] == INF) return INF; if (i) res += dist[t]; st[t] = true; for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]); }
for (int i = 1; i <= n; i ++ ) p[i] = i; // 初始化并查集
int res = 0, cnt = 0; for (int i = 0; i < m; i ++ ) { int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a), b = find(b); if (a != b) // 如果两个连通块不连通，则将这两个连通块合并 { p[a] = b; res += w; cnt ++ ; } }
if (cnt < n - 1) return INF; return res; }
染色法判别二分图 —— 模板题 AcWing 860. 染色法判定二分图
时间复杂度是 O(n+m)O(n+m), nn 表示点数，mm 表示边数
int n; // n 表示点数 int h[N], e[M], ne[M], idx; // 邻接表存储图 int color[N]; // 表示每个点的颜色，-1 表示未染色，0 表示白色，1 表示黑色
// 参数：u 表示当前节点，c 表示当前点的颜色 booldfs(int u, int c) { color[u] = c; for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (color[j] == -1) { if (!dfs(j, !c)) returnfalse; } elseif (color[j] == c) returnfalse; }
returntrue; }
boolcheck() { memset(color, -1, sizeof color); bool flag = true; for (int i = 1; i <= n; i ++ ) if (color[i] == -1) if (!dfs(i, 0)) { flag = false; break; } return flag; }
匈牙利算法 —— 模板题 AcWing 861. 二分图的最大匹配
时间复杂度是 O(nm)O(nm), nn 表示点数，mm 表示边数
int n1, n2; // n1 表示第一个集合中的点数，n2 表示第二个集合中的点数 int h[N], e[M], ne[M], idx; // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边 int match[N]; // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个 bool st[N]; // 表示第二个集合中的每个点是否已经被遍历过
boolfind(int x) { for (int i = h[x]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) { st[j] = true; if (match[j] == 0 || find(match[j])) { match[j] = x; returntrue; } } }
returnfalse; }
求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0; for (int i = 1; i <= n1; i ++ ) { memset(st, false, sizeof st); if (find(i)) res ++ ; }
试除法判定质数 —— 模板题 AcWing 866. 试除法判定质数
boolis_prime(int x) { if (x < 2) returnfalse; for (int i = 2; i <= x / i; i ++ ) if (x % i == 0) returnfalse; returntrue; }
试除法分解质因数 —— 模板题 AcWing 867. 分解质因数
voiddivide(int x) { for (int i = 2; i <= x / i; i ++ ) if (x % i == 0) { int s = 0; while (x % i == 0) x /= i, s ++ ; cout << i << ' ' << s << endl; } if (x > 1) cout << x << ' ' << 1 << endl; cout << endl; }
朴素筛法求素数 —— 模板题 AcWing 868. 筛质数
int primes[N], cnt; // primes [] 存储所有素数 bool st[N]; // st [x] 存储 x 是否被筛掉
voidget_primes(int n) { for (int i = 2; i <= n; i ++ ) { if (st[i]) continue; primes[cnt ++ ] = i; for (int j = i + i; j <= n; j += i) st[j] = true; } }
线性筛法求素数 —— 模板题 AcWing 868. 筛质数
int primes[N], cnt; // primes [] 存储所有素数 bool st[N]; // st [x] 存储 x 是否被筛掉
voidget_primes(int n) { for (int i = 2; i <= n; i ++ ) { if (!st[i]) primes[cnt ++ ] = i; for (int j = 0; primes[j] <= n / i; j ++ ) { st[primes[j] * i] = true; if (i % primes[j] == 0) break; } } }
试除法求所有约数 —— 模板题 AcWing 869. 试除法求约数
vector<int> get_divisors(int x) { vector<int> res; for (int i = 1; i <= x / i; i ++ ) if (x % i == 0) { res.push_back(i); if (i != x / i) res.push_back(x / i); } sort(res.begin(), res.end()); return res; }
intgcd(int a, int b) { return b ? gcd(b, a % b) : a; }
求欧拉函数 —— 模板题 AcWing 873. 欧拉函数
intphi(int x) { int res = x; for (int i = 2; i <= x / i; 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; }
筛法求欧拉函数 —— 模板题 AcWing 874. 筛法求欧拉函数
int primes[N], cnt; // primes [] 存储所有素数 int euler[N]; // 存储每个数的欧拉函数 bool st[N]; // st [x] 存储 x 是否被筛掉
voidget_eulers(int n) { euler[1] = 1; for (int i = 2; i <= n; i ++ ) { if (!st[i]) { primes[cnt ++ ] = i; euler[i] = i - 1; } for (int j = 0; primes[j] <= n / i; j ++ ) { int t = primes[j] * i; st[t] = true; if (i % primes[j] == 0) { euler[t] = euler[i] * primes[j]; break; } euler[t] = euler[i] * (primes[j] - 1); } } }
快速幂 —— 模板题 AcWing 875. 快速幂
求 m^k mod p，时间复杂度 O(logk)。
intqmi(int m, int k, int p) { int res = 1 % p, t = m; while (k) { if (k&1) res = res * t % p; t = t * t % p; k >>= 1; } return res; }
扩展欧几里得算法 —— 模板题 AcWing 877. 扩展欧几里得算法
求 x, y，使得 ax + by = gcd(a, b)
intexgcd(int a, int b, int &x, int &y) { if (!b) { x = 1; y = 0; return a; } int d = exgcd(b, a % b, y, x); y -= (a/b) * x; return d; }
高斯消元 —— 模板题 AcWing 883. 高斯消元解线性方程组
a [N][N] 是增广矩阵
intgauss() { int c, r; for (c = 0, r = 0; c < n; c ++ ) { int t = r; for (int i = r; i < n; i ++ ) // 找到绝对值最大的行 if (fabs(a[i][c]) > fabs(a[t][c])) t = i;
if (fabs(a[t][c]) < eps) continue;
for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]); // 将绝对值最大的行换到最顶端 for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c]; // 将当前行的首位变成 1 for (int i = r + 1; i < n; i ++ ) // 用当前行将下面所有的列消成 0 if (fabs(a[i][c]) > eps) for (int j = n; j >= c; j -- ) a[i][j] -= a[r][j] * a[i][c];
r ++ ; }
if (r < n) { for (int i = r; i < n; i ++ ) if (fabs(a[i][n]) > eps) return2; // 无解 return1; // 有无穷多组解 }
for (int i = n - 1; i >= 0; i -- ) for (int j = i + 1; j < n; j ++ ) a[i][n] -= a[i][j] * a[j][n];
return0; // 有唯一解 }
递推法求组合数 —— 模板题 AcWing 885. 求组合数 I
c [a][b] 表示从 a 个苹果中选 b 个的方案数
for (int i = 0; i < N; i ++ ) for (int j = 0; j <= i; j ++ ) if (!j) c[i][j] = 1; else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
intqmi(int a, int k, int p)// 快速幂模板 { int res = 1; while (k) { if (k & 1) res = (LL)res * a % p; a = (LL)a * a % p; k >>= 1; } return res; }
// 预处理阶乘的余数和阶乘逆元的余数
fact[0] = infact[0] = 1; for (int i = 1; i < N; i ++ ) { fact[i] = (LL)fact[i - 1] * i % mod; infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod; }
Lucas 定理 —— 模板题 AcWing 887. 求组合数 III
若 p 是质数，则对于任意整数 1 <= m <= n，有：
C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p)
intqmi(int a, int k, int p)// 快速幂模板 { int res = 1 % p; while (k) { if (k & 1) res = (LL)res * a % p; a = (LL)a * a % p; k >>= 1; } return res; }
intC(int a, int b, int p)// 通过定理求组合数 C(a, b) { if (a < b) return0;
LL x = 1, y = 1; // x 是分子，y 是分母 for (int i = a, j = 1; j <= b; i --, j ++ ) { x = (LL)x * i % p; y = (LL) y * j % p; }
return x * (LL)qmi(y, p - 2, p) % p; }
intlucas(LL a, LL b, int p) { if (a < p && b < p) returnC(a, b, p); return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p; }
分解质因数法求组合数 —— 模板题 AcWing 888. 求组合数 IV
当我们需要求出组合数的真实值，而非对某个数的余数时，分解质因数的方式比较好用： 1. 筛法求出范围内的所有质数 2. 通过 C(a, b) = a! / b! / (a - b)! 这个公式求出每个质因子的次数。 n! 中 p 的次数是 n / p + n / p^2 + n / p^3 + … 3. 用高精度乘法将所有质因子相乘
int primes[N], cnt; // 存储所有质数 int sum[N]; // 存储每个质数的次数 bool st[N]; // 存储每个数是否已被筛掉
voidget_primes(int n)// 线性筛法求素数 { for (int i = 2; i <= n; i ++ ) { if (!st[i]) primes[cnt ++ ] = i; for (int j = 0; primes[j] <= n / i; j ++ ) { st[primes[j] * i] = true; if (i % primes[j] == 0) break; } } }
intget(int n, int p)// 求 n！中的次数 { int res = 0; while (n) { res += n / p; n /= p; } return res; }
vector<int> mul(vector<int> a, int b)// 高精度乘低精度模板 { vector<int> c; int t = 0; for (int i = 0; i < a.size(); i ++ ) { t += a[i] * b; c.push_back(t % 10); t /= 10; }
while (t) { c.push_back(t % 10); t /= 10; }
return c; }
get_primes(a); // 预处理范围内的所有质数
for (int i = 0; i < cnt; i ++ ) // 求每个质因数的次数 { int p = primes[i]; sum[i] = get(a, p) - get(b, p) - get(a - b, p); }
vector<int> res; res.push_back(1);
for (int i = 0; i < cnt; i ++ ) // 用高精度乘法将所有质因子相乘 for (int j = 0; j < sum[i]; j ++ ) res = mul(res, primes[i]);
卡特兰数 —— 模板题 AcWing 889. 满足条件的 01 序列
给定 n 个 0 和 n 个 1，它们按照某种顺序排成长度为 2n 的序列，满足任意前缀中 0 的个数都不少于 1 的个数的序列的数量为： Cat(n) = C(2n, n) / (n + 1) NIM 游戏 —— 模板题 AcWing 891. Nim 游戏 给定 N 堆物品，第 i 堆物品有 Ai 个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取最优策略，问先手是否必胜。
我们把这种游戏称为 NIM 博弈。把游戏过程中面临的状态称为局面。整局游戏第一个行动的称为先手，第二个行动的称为后手。若在某一局面下无论采取何种行动，都会输掉游戏，则称该局面必败。 所谓采取最优策略是指，若在某一局面下存在某种行动，使得行动后对面面临必败局面，则优先采取该行动。同时，这样的局面被称为必胜。我们讨论的博弈问题一般都只考虑理想情况，即两人均无失误，都采取最优策略行动时游戏的结果。 NIM 博弈不存在平局，只有先手必胜和先手必败两种情况。
定理： NIM 博弈先手必胜，当且仅当 A1 ^ A2 ^ … ^ An != 0
公平组合游戏 ICG
若一个游戏满足：
由两名玩家交替行动； 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关； 不能行动的玩家判负； 则称该游戏为一个公平组合游戏。 NIM 博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件 2 和条件 3。
微信
