#include<bits/stdc++.h> usingnamespace std; using ll = longlong;
/* ========== 模板一:getchar 逐字符快读(推荐日常使用) ========== */ inlineintread(){ int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { // 跳过空白符、字母等一切非数字字符 if (c == '-') f = -1; // 遇到负号记录符号 c = getchar(); } while (c >= '0' && c <= '9') { // 逐位累加:x = x * 10 + digit x = x * 10 + (c - '0'); c = getchar(); } return x * f; }
/* ========== 模板二:fread 块读(数据量极大时最快) ========== */ constint BS = 1 << 20; // 缓冲区大小 1MB char buf[BS], *p1 = buf, *p2 = buf; // p1 当前读位置,p2 缓冲末尾 inlinechargetc(){ // 缓冲读空时用 fread 重新填满;读到文件尾返回 EOF if (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, BS, stdin)) == p1) return EOF; return *p1++; } inlineintread2(){ int x = 0, f = 1; char c = getc(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getc(); } while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = getc(); } return x * f; }
/* ========== 快写模板(先写进缓冲区,最后一次性输出) ========== */ char obuf[BS], *op = obuf; inlinevoidwriteInt(int x){ if (x < 0) { *op++ = '-'; x = -x; } char s[12]; int top = 0; // int 最多 10 位,12 足够 if (x == 0) s[top++] = '0'; // 特判 0,否则不会输出任何数字 while (x > 0) { s[top++] = char('0' + x % 10); x /= 10; } while (top > 0) *op++ = s[--top]; // 倒序写入缓冲区 *op++ = '\n'; // 末尾换行 }
intmain(){ int n = read(); // 样例:读入 n 个数并输出 while (n--) writeInt(read()); fwrite(obuf, 1, op - obuf, stdout); // 主函数结束前一次性刷出 return0; }
注意点 / 坑点:
快读遇到 x = -2147483648(INT_MIN)时 -x 会溢出;此时应改用 long long 读入,或单独特判。绝大多数题目的数据用 int 快读即可。
#include<bits/stdc++.h> usingnamespace std; using ll = longlong;
/* ===== 整数二分模板一:求第一个 >= x 的位置(数组 a 升序,返回下标) ===== 收缩规则:a[mid] >= x 时 mid 可能是答案,令 r = mid 保留它; 此时 mid 必须用 (l + r) / 2 向下取整。若错误地向上取整,当 l + 1 == r 时 mid == r,条件成立则 r = mid 不变,死循环。 */ intfirstGE(const vector<int>& a, int x){ int l = 0, r = (int)a.size() - 1; if (a.empty()) return-1; // 空数组特判,防止 a[l] 越界 while (l < r) { int mid = (l + r) / 2; // 向下取整,配套 r = mid if (a[mid] >= x) r = mid; // 答案在 [l, mid] 内 else l = mid + 1; // a[mid] < x,mid 及左侧全部排除 } return a[l] >= x ? l : -1; // 结束时 l == r,检查是否满足 }
/* ===== 整数二分模板二:求最后一个 <= x 的位置(数组 a 升序) ===== 收缩规则:a[mid] <= x 时 mid 可能是答案,令 l = mid 保留它; 此时 mid 必须用 (l + r + 1) / 2 向上取整。若错误地向下取整,当 l + 1 == r 时 mid == l,条件成立则 l = mid 不变,死循环。 */ intlastLE(const vector<int>& a, int x){ int l = 0, r = (int)a.size() - 1; if (a.empty()) return-1; while (l < r) { int mid = (l + r + 1) / 2; // 向上取整,配套 l = mid if (a[mid] <= x) l = mid; // 答案在 [mid, r] 内 else r = mid - 1; // a[mid] > x,mid 及右侧全部排除 } return a[l] <= x ? l : -1; }
/* ===== 实数二分:求单调函数 f 满足 check 的临界点 ===== */ // 写法一:按 eps 控制精度(精度要求 1e-6 时 eps 取 1e-8 才稳) boolcheck(double mid); // 按题目实现的判定函数 doublebsEps(double l, double r){ while (r - l > 1e-8) { // 区间长度小于 eps 停止 double mid = (l + r) / 2; if (check(mid)) r = mid; // 满足条件的区间在左侧 else l = mid; } return (l + r) / 2; } // 写法二:固定迭代 60~100 次(推荐,避免 eps 与浮点误差纠缠) doublebsIter(double l, double r){ for (int i = 0; i < 80; ++i) { // 每次区间减半,80 次足够精确到 1e-20 double mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; } return (l + r) / 2; }
/* ===== 二分答案两种套路(check 是 O(n) 的判定函数) ===== */ // 套路一:最大化最小值 —— 求最大的 x 使 check(x) 为真(x 越大越难满足) // 答案是「可行域的上界」,收缩用 l = mid,mid 需向上取整 intmaxMin(){ int l = 0, r = 1e9; // 上下界按题目范围设定 while (l < r) { int mid = (l + r + 1) / 2; // 配套 l = mid,向上取整 if (check(mid)) l = mid; // mid 可行,答案至少为 mid else r = mid - 1; } return l; } // 套路二:最小化最大值 —— 求最小的 x 使 check(x) 为真(x 越大越容易满足) // 答案是「可行域的下界」,收缩用 r = mid,mid 需向下取整 intminMax(){ int l = 0, r = 1e9; while (l < r) { int mid = (l + r) / 2; // 配套 r = mid,向下取整 if (check(mid)) r = mid; // mid 可行,答案至多为 mid else l = mid + 1; } return l; }
#include<bits/stdc++.h> usingnamespace std; using ll = longlong;
using BigInt = vector<int>; // 低位在前:a[0] 是个位
/* ---------- 字符串读入 ---------- */ BigInt fromString(const string& s){ BigInt a; for (int i = (int)s.size() - 1; i >= 0; --i) a.push_back(s[i] - '0'); // 倒序逐位存入 return a; }
/* ---------- 比较大小:a < b 返回 -1,a == b 返回 0,a > b 返回 1 ---------- */ intcmp(const BigInt& a, const BigInt& b){ if (a.size() != b.size()) return a.size() < b.size() ? -1 : 1; // 位数多的大 for (int i = (int)a.size() - 1; i >= 0; --i) // 从最高位往下比 if (a[i] != b[i]) return a[i] < b[i] ? -1 : 1; return0; }
/* ---------- 高精 + 高精 ---------- */ BigInt add(const BigInt& a, const BigInt& b){ BigInt c; int carry = 0; // 进位 for (size_t i = 0; i < max(a.size(), b.size()); ++i) { int s = carry; if (i < a.size()) s += a[i]; if (i < b.size()) s += b[i]; c.push_back(s % 10); carry = s / 10; } if (carry) c.push_back(carry); // 最高位进位,如 99 + 1 = 100 return c; }
/* ---------- 高精 - 高精(要求 a >= b,调用前用 cmp 判断) ---------- */ BigInt sub(const BigInt& a, const BigInt& b){ BigInt c; int borrow = 0; // 借位 for (size_t i = 0; i < a.size(); ++i) { int s = a[i] - borrow - (i < b.size() ? b[i] : 0); if (s < 0) { s += 10; borrow = 1; } // 不够减,向高位借 1 else borrow = 0; c.push_back(s); } while (c.size() > 1 && c.back() == 0) c.pop_back(); // 去前导零 return c; }
/* ---------- 高精 * 低精(b 用 long long,b 本身不能溢出) ---------- */ BigInt mulSmall(const BigInt& a, ll b){ BigInt c; ll carry = 0; for (size_t i = 0; i < a.size(); ++i) { ll s = a[i] * b + carry; // 单次乘积 ≤ 9e9,必须 long long c.push_back((int)(s % 10)); carry = s / 10; } while (carry) { c.push_back((int)(carry % 10)); carry /= 10; } while (c.size() > 1 && c.back() == 0) c.pop_back(); return c; }
/* ---------- 高精 * 高精(朴素 O(nm),先累加后统一进位) ---------- */ BigInt mul(const BigInt& a, const BigInt& b){ BigInt c(a.size() + b.size() + 1, 0); // 多留一位装最高位进位 for (size_t i = 0; i < a.size(); ++i) for (size_t j = 0; j < b.size(); ++j) c[i + j] += a[i] * b[j]; for (size_t i = 0; i + 1 < c.size(); ++i) { // 逐位进位,一次扫描足够 c[i + 1] += c[i] / 10; c[i] %= 10; } while (c.size() > 1 && c.back() == 0) c.pop_back(); // 去掉多余的最高位 return c; }
/* ---------- 高精 / 低精:返回商,余数通过引用带出 ---------- */ BigInt divSmall(const BigInt& a, ll b, ll& rem){ BigInt q(a.size(), 0); // 商的位数 ≤ 被除数位数 rem = 0; for (int i = (int)a.size() - 1; i >= 0; --i) { // 从最高位开始试商 rem = rem * 10 + a[i]; q[i] = (int)(rem / b); // 商直接写在对应位 rem %= b; } while (q.size() > 1 && q.back() == 0) q.pop_back(); // 去前导零 return q; }
/* ---------- 高精 % 低精(取模) ---------- */ ll modSmall(const BigInt& a, ll b){ ll r = 0; for (int i = (int)a.size() - 1; i >= 0; --i) r = (r * 10 + a[i]) % b; // 边除边取余即可 return r; }
/* ---------- 输出 ---------- */ voidprint(const BigInt& a){ for (int i = (int)a.size() - 1; i >= 0; --i) putchar('0' + a[i]); // 从最高位打印 putchar('\n'); }
intmain(){ string sa, sb; cin >> sa >> sb; print(add(fromString(sa), fromString(sb))); // 大整数加法示例 return0; }
intmain(){ vector<int> a = {1000000000, 5, 5, -3, 42}; discretize(a); // vals = {-3, 5, 42, 1000000000} for (int x : a) printf("%d -> %d\n", x, id(x)); // 5->1, -3->0, 42->2, 1e9->3 return0; }
配合树状数组 / 线段树(典型:离散化 + 树状数组求逆序对):
1 2 3 4 5 6 7 8 9 10 11 12 13 14
/* 思路:树状数组下标范围是 1..m(m 为不同值个数)。从前往后扫描原数组, 每次先查询「已插入且比 x 大的元素个数」累加进答案,再把 x 的排名插入。 值域 1e9 无法直接开数组,必须先离散化。 */ constint MAXN = 100005; int bit[MAXN]; voidadd(int i, int v){ for (; i < MAXN; i += i & (-i)) bit[i] += v; } intquery(int i){ int s = 0; for (; i > 0; i -= i & (-i)) s += bit[i]; return s; } // 逆序对计数主流程(框架,m = vals.size()): // ll ans = 0; // for (int i = 0; i < n; ++i) { // int rk = id(a[i]) + 1; // 树状数组下标从 1 开始 // ans += query(m) - query(rk); // 已插入的、比 a[i] 大的元素个数 // add(rk, 1); // }
算法思想:尺取法(滑动窗口)维护区间 [l, r]:右指针 r 不断右移「扩张」窗口,一旦窗口满足条件就尝试左移 l「收缩」窗口并统计答案。因为统计量单调(如区间和随 r 增大而增大、随 l 增大而减小),每个指针最多移动 n 次,总复杂度 O(n)。「两数之和」类则是左右指针相向移动:和太小右移左指针增大,和太大左移右指针减小。指针永远单向移动、绝不回退,是 O(n) 复杂度的根本保证。
#include<bits/stdc++.h> usingnamespace std; using ll = longlong;
/* ===== 尺取法:求「和 >= S」的最短连续子段长度(POJ 3061) ===== */ intshortestSubarray(vector<int>& a, int S){ int n = (int)a.size(); int l = 0, sum = 0, ans = n + 1; // ans 初始为不可能值,表示暂无答案 for (int r = 0; r < n; ++r) { // 右指针扩张窗口 sum += a[r]; // 窗口变为 [l, r] while (sum >= S) { // 当前窗口满足条件 ans = min(ans, r - l + 1); // 记录长度,并尝试更短 sum -= a[l]; // 左指针收缩:去掉 a[l] ++l; } } return ans == n + 1 ? -1 : ans; // 无解返回 -1 }
/* ===== 两数之和:有序数组找 i < j 使 a[i] + a[j] == target ===== */ booltwoSum(vector<int>& a, int target){ int l = 0, r = (int)a.size() - 1; // 左右指针相向移动 while (l < r) { ll s = (ll)a[l] + a[r]; // long long 防止溢出 if (s == target) returntrue; elseif (s < target) ++l; // 和太小:左指针右移使和变大 else --r; // 和太大:右指针左移使和变小 } returnfalse; }
/* ===== 滑动窗口通用框架:求「满足条件的最长子段」 ===== 例:窗口内不同字符不超过 K 个的最长子串(cnt 统计频次) */ intlongestWindow(const string& s, int K){ int cnt[26] = {0}, diff = 0, l = 0, ans = 0; for (int r = 0; r < (int)s.size(); ++r) { if (++cnt[s[r] - 'a'] == 1) ++diff; // 新字符出现,不同种类 +1 while (diff > K) { // 不满足条件:收缩左端点 if (--cnt[s[l] - 'a'] == 0) --diff; ++l; } ans = max(ans, r - l + 1); // 收缩后窗口重新满足条件 } return ans; }
注意点 / 坑点:
适用前提是「区间单调性」:固定 l 时,随着 r 右移,统计量(和、种类数等)单调不减(或不增)。若统计量可能回退(如区间最大值),就不能用尺取,需考虑单调队列 / 线段树。
#include<bits/stdc++.h> usingnamespace std; using ll = longlong; constint MAXN = 50005; int n, q, block; int a[MAXN], cnt[MAXN]; // a 原序列,cnt 值出现次数 ll cur, ans[MAXN]; // cur 当前区间答案,ans 每问答案 structQuery { int l, r, id; } qs[MAXN];
boolcmp(const Query& x, const Query& y){ int bx = x.l / block, by = y.l / block; if (bx != by) return bx < by; // 第一关键字:左端点所在块 // 奇偶优化:块号奇偶交替排列右端点方向,减少右指针移动 return (bx & 1) ? x.r > y.r : x.r < y.r; } voidadd(int pos){ // 把 a[pos] 加入当前区间 if (cnt[a[pos]] == 0) cur++; // 出现次数从 0 变 1:不同数 +1 cnt[a[pos]]++; } voiddel(int pos){ // 把 a[pos] 移出当前区间 cnt[a[pos]]--; if (cnt[a[pos]] == 0) cur--; // 减到 0:不同数 -1 } intmain(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> q; block = sqrt(n); // 块大小常取 n / sqrt(q) 调优 for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= q; i++) { cin >> qs[i].l >> qs[i].r; qs[i].id = i; } sort(qs + 1, qs + q + 1, cmp); int l = 1, r = 0; // 初始空区间 for (int i = 1; i <= q; i++) { while (l > qs[i].l) add(--l); // 先扩后缩:先加再减,防越界 while (r < qs[i].r) add(++r); while (l < qs[i].l) del(l++); while (r > qs[i].r) del(r--); ans[qs[i].id] = cur; } for (int i = 1; i <= q; i++) cout << ans[i] << '\n'; return0; }
// ========== 1. 字典树:字符串前缀统计 ========== structTrie { int ch[MAXN][26]; // ch[p][k]:p 的第 k 个儿子节点编号,0 表示空 int cnt[MAXN]; // cnt[p]:经过节点 p 的字符串个数(前缀计数) int tot; // 已分配节点数(根为 0) voidinit(){ memset(ch[0], 0, sizeof(ch[0])); cnt[0] = 0; tot = 0; } voidinsert(const string& s){ int p = 0; for (char c : s) { int k = c - 'a'; if (!ch[p][k]) { // 没有该子节点则新建 ch[p][k] = ++tot; memset(ch[tot], 0, sizeof(ch[tot])); // 清空新节点 cnt[tot] = 0; } p = ch[p][k]; cnt[p]++; // 沿途计数:有多少串经过此前缀 } } intquery(const string& s){ // 以 s 为前缀的串个数 int p = 0; for (char c : s) { int k = c - 'a'; if (!ch[p][k]) return0; // 途中断了:无此前缀 p = ch[p][k]; } return cnt[p]; } voidremove(const string& s){ // 删除一个串(计数减一) int p = 0; for (char c : s) { p = ch[p][c - 'a']; if (cnt[p]) cnt[p]--; // 注意:不真正删节点,只减计数 } } } trie;
// ========== 2. 01-Trie:求最大异或对 ========== structTrie01 { int ch[MAXN * 31][2]; // 每个数 31 位,节点数上限 ≈ n * 31 int tot; voidinit(){ memset(ch[0], 0, sizeof(ch[0])); tot = 0; } voidinsert(int x){ // 从高位(30)到低位(0)插入 int p = 0; for (int i = 30; i >= 0; i--) { int b = (x >> i) & 1; // 取出第 i 位 if (!ch[p][b]) { ch[p][b] = ++tot; memset(ch[tot], 0, sizeof(ch[tot])); } p = ch[p][b]; } } intmaxXor(int x){ // 与 x 异或的最大值 int p = 0, res = 0; for (int i = 30; i >= 0; i--) { int b = (x >> i) & 1, want = b ^ 1; // 贪心:优先走相反位 if (ch[p][want]) { // 存在相反位:该位异或得 1 res |= (1 << i); p = ch[p][want]; } else { p = ch[p][b]; // 否则只能走同向位(该位为 0) } } return res; } } trie01; // 最大异或对:把每个数插入后依次取 maxXor(a[i]) 的最大值; // "与当前集合中某个数异或最大"即可 O(31) 回答。
注意点 / 坑点
节点池大小要开”总字符数”级别:n 个长度 L 的串需要 n * L + 1 个节点;01-Trie 每个数 31 位要 n * 31 个节点,开小必 RE。
无旋 Treap(FHQ Treap):用 split / merge 两个操作实现平衡树全部功能(插入、删除、排名、第 k 小、前驱后继),还能轻易支持区间操作(如文艺平衡树的区间翻转),且天然可持久化。
算法思想
每个节点存值 val 与随机优先级 pri,树满足”中序遍历 = 有序序列”且按 pri 满足堆性质。split(p, val, a, b) 把树 p 按值(或按大小)拆成两棵;merge(a, b) 把两棵树合并(要求 a 中所有值 ≤ b 中所有值)。插入 = split 后 merge 三棵;删除 = split 两次取出目标节点再合并左右子树。区间操作用”按大小 split”把区间 [l, r] 独立出来打懒标记再合并回去。
#include<bits/stdc++.h> usingnamespace std; using ll = longlong;
constint N = 505; const ll INF = 0x3f3f3f3f3f3f3f3fLL; ll d[N][N]; // 距离矩阵 int n, m;
voidfloyd(){ for (int k = 1; k <= n; k++) // 中转点 k 必须在最外层 for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (d[i][k] != INF && d[k][j] != INF) // 防溢出 d[i][j] = min(d[i][j], d[i][k] + d[k][j]); }
// ---------- 传递闭包(可达性),bitset 优化 ---------- bitset<N> reach[N]; // reach[i][j] = 1 表示 i 可达 j voidclosure(){ for (int k = 1; k <= n; k++) // k 仍在外层 for (int i = 1; i <= n; i++) if (reach[i][k]) reach[i] |= reach[k]; // 一行位运算代替内层循环 // bitset 版复杂度约 O(n³ / 64) }
intmain(){ cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) d[i][j] = (i == j ? 0 : INF); // 对角线必须为 0 for (int i = 0; i < m; i++) { int u, v; ll w; cin >> u >> v >> w; d[u][v] = min(d[u][v], w); // 重边取最小 } floyd(); return0; }
注意点 / 坑点:
k 必须最外层:写成 i、j 在外的顺序是错的,会导致中转点未完全加入而漏算路径——这是 Floyd 最高频的写错点。
voiddfs(int u, int f){ depth[u] = depth[f] + 1; fa[0][u] = f; // 1 级祖先 for (int k = 1; k < LOG; k++) fa[k][u] = fa[k - 1][fa[k - 1][u]]; // 2^k = 2^(k-1) + 2^(k-1) for (int v : g[u]) if (v != f) dfs(v, u); }
intlca(int u, int v){ if (depth[u] < depth[v]) swap(u, v); int diff = depth[u] - depth[v]; // 第一步:跳到同深度 for (int k = 0; k < LOG; k++) if (diff >> k & 1) u = fa[k][u]; if (u == v) return u; for (int k = LOG - 1; k >= 0; k--) // 第二步:一起跳到 LCA 下方 if (fa[k][u] != fa[k][v]) { u = fa[k][u]; v = fa[k][v]; } return fa[0][u]; }
// ========== Tarjan 离线(并查集) ========== int f[N]; bool vis[N]; vector<pair<int,int>> query[N]; // query[u] = {(v, 询问编号)} int ans[N]; intfind(int x){ return f[x] == x ? x : f[x] = find(f[x]); }
voidtarjan(int u, int fa0){ f[u] = u; vis[u] = true; for (int v : g[u]) if (v != fa0) { tarjan(v, u); f[v] = u; // 子树处理完,并入父节点集合 } for (auto &[v, id] : query[u]) if (vis[v]) ans[id] = find(v); // v 已访问 => 其集合代表元即 LCA }
#include<bits/stdc++.h> usingnamespace std; using ll = longlong;
constint N = 2e5 + 5; vector<int> g[N]; // 无向无权树 int parent[N]; // BFS 树,用于回溯直径路径 int far; // 距离起点最远的点
// BFS 返回从 s 出发的最远距离,并记录 parent intbfs(int s, int n){ vector<int> dist(n + 1, -1); queue<int> q; dist[s] = 0; q.push(s); parent[s] = 0; int best = s; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : g[u]) if (dist[v] == -1) { dist[v] = dist[u] + 1; parent[v] = u; q.push(v); if (dist[v] > dist[best]) best = v; } } far = best; return dist[best]; // 返回最远距离(无权图即边数) }
// 求直径端点 a、b 与路径(顶点序列) voiddiameter(int n, int &a, int &b, vector<int> &path){ bfs(1, n); a = far; // 第一遍:任意点 -> 端点 a bfs(a, n); b = far; // 第二遍:a -> 端点 b for (int x = b; x != 0; x = parent[x]) path.push_back(x); reverse(path.begin(), path.end()); // path 为直径上的顶点序列 }
// ========== 树的重心 ========== int sz[N], mx[N], centroid;
voiddfsC(int u, int f, int n){ sz[u] = 1; mx[u] = 0; for (int v : g[u]) if (v != f) { dfsC(v, u, n); sz[u] += sz[v]; mx[u] = max(mx[u], sz[v]); // 孩子方向的最大子树 } mx[u] = max(mx[u], n - sz[u]); // 父方向那一块(易漏!) if (centroid == 0 || mx[u] < mx[centroid]) centroid = u; }
注意点 / 坑点:
直径定理要求边权非负(一般树题满足);带负权边时两遍 DFS 失效,需改用树形 DP 求直径。
parent 数组来自「从 a 出发」的那次 BFS:回溯必须从 b 沿 parent 走到 0,不要从 a 反向走(parent 不是双向链表)。
#include<bits/stdc++.h> usingnamespace std; using ll = longlong;
constint N = 5e5 + 5, LOG = 20; vector<int> g[N]; int depth[N], fa[LOG][N]; ll diff[N]; // 差分标记
voiddfs(int u, int f){ // 预处理深度与倍增表(同 3.8) depth[u] = depth[f] + 1; fa[0][u] = f; for (int k = 1; k < LOG; k++) fa[k][u] = fa[k - 1][fa[k - 1][u]]; for (int v : g[u]) if (v != f) dfs(v, u); }
intlca(int u, int v){ if (depth[u] < depth[v]) swap(u, v); int d = depth[u] - depth[v]; for (int k = 0; k < LOG; k++) if (d >> k & 1) u = fa[k][u]; if (u == v) return u; for (int k = LOG - 1; k >= 0; k--) if (fa[k][u] != fa[k][v]) { u = fa[k][u]; v = fa[k][v]; } return fa[0][u]; }
// ========== 点差分:路径 u->v 上每个点 +c ========== voidpathAddPoint(int u, int v, ll c){ int l = lca(u, v); diff[u] += c; diff[v] += c; diff[l] -= c; diff[fa[0][l]] -= c; // 点差分多减一次 l 的父节点 }
// ========== 边差分:路径 u->v 上每条边 +c(边权挂在深度大的端点) ========== voidpathAddEdge(int u, int v, ll c){ int l = lca(u, v); diff[u] += c; diff[v] += c; diff[l] -= 2 * c; // 边差分在 l 处减两次 }
// 最后一次 DFS 自底向上还原:diff[u] 累加所有子树的标记 voidrestore(int u, int f){ for (int v : g[u]) if (v != f) { restore(v, u); diff[u] += diff[v]; } // 此时:点差分 => diff[u] 是点 u 的真实值; // 边差分 => diff[u] 是 u 与 fa[u] 之间那条边的真实值 }
#include<bits/stdc++.h> usingnamespace std; using ll = longlong;
constint N = 1e5 + 5; vector<int> g[N]; int n, m, root, mod; int fa[N], depth[N], sz[N], heavy[N]; // 第一次 DFS 结果 int dfn[N], top[N], rnk[N], timer; // rnk[dfn[u]] = u ll w[N]; // 点权(原编号)
// ========== 第一次 DFS:sz / heavy / depth / fa ========== voiddfs1(int u, int f){ fa[u] = f; depth[u] = depth[f] + 1; sz[u] = 1; heavy[u] = 0; int mx = 0; for (int v : g[u]) if (v != f) { dfs1(v, u); sz[u] += sz[v]; if (sz[v] > mx) mx = sz[v], heavy[u] = v; // 记录重儿子 } }
// ========== 第二次 DFS:dfn / top(先走重儿子保证重链连续) ========== voiddfs2(int u, int tp){ dfn[u] = ++timer; rnk[timer] = u; top[u] = tp; if (heavy[u]) dfs2(heavy[u], tp); // 重儿子继承链顶 for (int v : g[u]) if (v != fa[u] && v != heavy[u]) dfs2(v, v); // 轻儿子新开链 }
// ---------- 线段树:区间加 / 区间和(含 lazy 下传) ---------- ll tree[N * 4], lazy[N * 4]; voidpushUp(int p){ tree[p] = (tree[p<<1] + tree[p<<1|1]) % mod; } voidpushDown(int p, int l, int r){ if (lazy[p] == 0) return; int m = (l + r) >> 1; ll c = lazy[p]; (tree[p<<1] += c * (m - l + 1)) %= mod; (lazy[p<<1] += c) %= mod; (tree[p<<1|1] += c * (r - m)) %= mod; (lazy[p<<1|1] += c) %= mod; lazy[p] = 0; } voidbuild(int p, int l, int r){ if (l == r) { tree[p] = w[rnk[l]] % mod; return; } // 注意 rnk 映射 int m = (l + r) >> 1; build(p<<1, l, m); build(p<<1|1, m+1, r); pushUp(p); } voidrangeAdd(int p, int l, int r, int ql, int qr, ll c){ if (ql <= l && r <= qr) { (tree[p] += c * (r - l + 1)) %= mod; (lazy[p] += c) %= mod; return; } pushDown(p, l, r); int m = (l + r) >> 1; if (ql <= m) rangeAdd(p<<1, l, m, ql, qr, c); if (qr > m) rangeAdd(p<<1|1, m+1, r, ql, qr, c); pushUp(p); } ll rangeSum(int p, int l, int r, int ql, int qr){ if (ql <= l && r <= qr) return tree[p]; pushDown(p, l, r); int m = (l + r) >> 1; ll res = 0; if (ql <= m) res += rangeSum(p<<1, l, m, ql, qr); if (qr > m) res += rangeSum(p<<1|1, m+1, r, ql, qr); return res % mod; }
// ---------- 路径操作:拆成 O(log n) 段链区间 ---------- voidpathAdd(int u, int v, ll c){ while (top[u] != top[v]) { if (depth[top[u]] < depth[top[v]]) swap(u, v); rangeAdd(1, 1, n, dfn[top[u]], dfn[u], c); // 处理 u 所在整条链 u = fa[top[u]]; // u 跳到链顶的父亲 } if (depth[u] > depth[v]) swap(u, v); rangeAdd(1, 1, n, dfn[u], dfn[v], c); // 同链后处理剩余区间 } ll pathSum(int u, int v){ ll res = 0; while (top[u] != top[v]) { if (depth[top[u]] < depth[top[v]]) swap(u, v); res = (res + rangeSum(1, 1, n, dfn[top[u]], dfn[u])) % mod; u = fa[top[u]]; } if (depth[u] > depth[v]) swap(u, v); res = (res + rangeSum(1, 1, n, dfn[u], dfn[v])) % mod; return res; }
#include<bits/stdc++.h> usingnamespace std; using ll = longlong;
constint N = 1e5 + 5; vector<int> g[N]; // 原图 vector<int> dag[N]; // 缩点后的 DAG int dfn[N], low[N], timer; int stk[N], top; // 手动栈(模拟系统栈,防爆栈) bool instk[N]; // 是否在栈中 int sccId[N], sccCnt; // 每个点所属 SCC 编号 vector<int> sccList[N]; // 每个 SCC 包含的顶点(可选)
voidtarjan(int u){ dfn[u] = low[u] = ++timer; stk[++top] = u; instk[u] = true; for (int v : g[u]) { if (!dfn[v]) { // 树边:递归后更新 low tarjan(v); low[u] = min(low[u], low[v]); } elseif (instk[v]) { // 回边 / 指向栈中顶点的横叉边 low[u] = min(low[u], dfn[v]); } // 指向已出栈顶点的边属于别的 SCC,无需处理 } if (low[u] == dfn[u]) { // u 是所在 SCC 的根 sccCnt++; while (true) { int x = stk[top--]; instk[x] = false; sccId[x] = sccCnt; sccList[sccCnt].push_back(x); if (x == u) break; } } }
// 主流程 + 缩点建 DAG(用 set 去重) voidsolve(int n){ for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i); set<pair<int,int>> added; for (int u = 1; u <= n; u++) for (int v : g[u]) { int a = sccId[u], b = sccId[v]; if (a != b && !added.count({a, b})) { added.insert({a, b}); dag[a].push_back(b); } } }
算法思想:每个变量 x 拆成两个顶点:「x 为真」(编号 x) 与「x 为假」(编号 x + n)。约束 a ∨ b 等价于两条蕴含边「¬a → b」与「¬b → a」(若 a 假则 b 必真,反之亦然);其它约束(a → b、a 必真、a 必假等)均可化为蕴含边。建图后用 Tarjan(3.12)求强连通分量:若存在变量 x 使得「x 真」与「x 假」在同一个 SCC,则自相矛盾,无解。输出方案:Tarjan 的 SCC 编号递增方向恰好是拓扑序逆序,取「编号较大」的一侧赋值即可(sccId[x] > sccId[x+n] 则 x 为真,否则为假)。
#include<bits/stdc++.h> usingnamespace std; using ll = longlong;
constint N = 2e5 + 5; // 2n 个顶点 vector<int> g[N]; // 蕴含图 int dfn[N], low[N], timer, stk[N], top; bool instk[N]; int sccId[N], sccCnt;
// 编号约定:x 为真 = x,x 为假 = x + n(n 为变量个数) intlit(int x, bool val){ return val ? x : x + n; }
voidaddImp(int a, int b){ g[a].push_back(b); } // a -> b
// 约束:x 取 xv 或 y 取 yv(即 a ∨ b) voidaddOr(int x, bool xv, int y, bool yv){ addImp(lit(x, !xv), lit(y, yv)); // ¬a -> b addImp(lit(y, !yv), lit(x, xv)); // ¬b -> a }
// 其他常用约束: // x 必为真:addImp(lit(x,false), lit(x,true)); // x 必为假:addImp(lit(x,true), lit(x,false)); // x -> y :addImp(lit(x,true), lit(y,true)); addImp(lit(y,false), lit(x,false));
voidtarjan(int u){ dfn[u] = low[u] = ++timer; stk[++top] = u; instk[u] = true; for (int v : g[u]) { if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); } elseif (instk[v]) low[u] = min(low[u], dfn[v]); } if (low[u] == dfn[u]) { sccCnt++; while (true) { int x = stk[top--]; instk[x] = false; sccId[x] = sccCnt; if (x == u) break; } } }
booltwoSAT(int n){ for (int i = 1; i <= 2 * n; i++) if (!dfn[i]) tarjan(i); for (int i = 1; i <= n; i++) if (sccId[i] == sccId[i + n]) returnfalse; // 真与假同 SCC => 无解 returntrue; }
// ---------- 配套:用快速乘实现的快速幂(mod 接近 1e18 时必须用这个) ---------- ll qpow_mul(ll a, ll b, ll mod){ ll res = 1 % mod; a %= mod; while (b > 0) { if (b & 1) res = qmul128(res, a, mod); a = qmul128(a, a, mod); b >>= 1; } return res; }
注意点 / 坑点:
res 初始化必须写 1 % mod:当 mod = 1 时答案是 0,初始化为 1 会返回错误结果。
乘法 res * a 可能溢出 ll:当 mod ≤ 1e9 时直接乘没问题;mod 超过约 4.6e9(√(9.2e18))时,res * a 就可能超过 9.2e18,必须改用快速乘或 __int128。
指数 b 为负数时本模板不适用(除非模数为素数且 a 可逆,先求逆元再对 -b 快速幂)。
快速乘的 res + a 在 mod 接近 1e18 时也可能溢出(两个接近 1e18 的数相加超过 ll),此时只能用 __int128。
#include<bits/stdc++.h> usingnamespace std; using ll = longlong;
// ---------- gcd / lcm ---------- ll gcd(ll a, ll b){ return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b){ // 先除后乘:a*b 可能溢出,而 a/gcd*b 不会(结果本身在 ll 范围内时) return a / gcd(a, b) * b; }
// ---------- 扩展欧几里得:求 ax+by = gcd(a,b) 的一组特解 (x,y),返回 gcd ---------- ll exgcd(ll a, ll b, ll &x, ll &y){ if (b == 0) { // 递归边界:gcd(a,0)=a,此时 x=1, y=0 满足 a*1+0*0=a x = 1; y = 0; return a; } ll g = exgcd(b, a % b, y, x); // 注意参数顺序交换:递归解是 b*y + (a%b)*x = g y -= a / b * x; // 回代:a*x + b*(y - (a/b)*x) = g,把系数修正到原方程 return g; }
// ---------- 解不定方程 ax + by = c ---------- // 返回 0 表示无解;有解时返回 gcd,且 x 被调整为最小非负整数解,y 对应 intsolveDiophantine(ll a, ll b, ll c, ll &x, ll &y){ ll g = exgcd(a, b, x, y); if (c % g != 0) return0; // 无解判定:c 必须是 g 的倍数 x *= c / g; // 特解放大 c/g 倍 y *= c / g; ll t = b / g; // x 的通解步长:x = x0 + (b/g)*t if (t < 0) t = -t; // b 可能为负,步长取绝对值 x = (x % t + t) % t; // 取 x 的最小非负整数解 y = (c - a * x) / b; // 由方程反解出对应的 y return1; }
// ---------- 用 exgcd 求逆元:a 在模 mod 下的逆元(要求 gcd(a,mod)=1) ---------- ll invExgcd(ll a, ll mod){ ll x, y; ll g = exgcd(a, mod, x, y); if (g != 1) return-1; // 不互素则不存在逆元(返回 -1 表示无解) return (x % mod + mod) % mod; // x 可能是负数,取模转正 }
注意点 / 坑点:
exgcd 返回的 x 可能是负数,凡是用它求逆元或通解都要 (x % t + t) % t 转成最小非负。
#include<bits/stdc++.h> usingnamespace std; using ll = longlong;
// __int128 乘法取模:64 位判素必须用,否则 (x*x)%n 溢出 ll mul(ll a, ll b, ll mod){ return (ll)((__int128)a * b % mod); }
ll qpow(ll a, ll b, ll mod){ ll res = 1 % mod; a %= mod; while (b) { if (b & 1) res = mul(res, a, mod); a = mul(a, a, mod); b >>= 1; } return res; }
// ---------- 试除法(n <= 1e7 量级时够用) ---------- boolisPrimeTrial(ll n){ if (n < 2) returnfalse; for (ll i = 2; i * i <= n; i++) if (n % i == 0) returnfalse; returntrue; }
// ---------- Miller-Rabin 单底数测试 ---------- // 检查 a^(n-1) ≡ 1 (mod n),若 n 为素数必通过;合数以 ≥3/4 概率被识破 boolmillerRabin(ll n, ll a){ if (n % a == 0) return n == a; // 先处理 a 整除 n 的平凡情况 ll d = n - 1, s = 0; while ((d & 1) == 0) { d >>= 1; s++; } // 分解 n-1 = d * 2^s,d 为奇数 ll x = qpow(a, d, n); if (x == 1 || x == n - 1) returntrue; // 两种情况直接通过 for (int i = 1; i < s; i++) { // 连续平方 s-1 次 x = mul(x, x, n); if (x == n - 1) returntrue; // 出现 n-1 说明二次探测定理通过 } returnfalse; // 都没有出现 n-1,必为合数 }
// ---------- 确定性 Miller-Rabin:ll 范围内 100% 正确 ---------- // 底数选择说明: // n < 2^32 时用 {2, 7, 61} 即可(32 位确定集); // n < 3.4e14 时用 {2,3,5,7,11,13,17}; // 有符号 64 位(|n| < 2^63)用下面 6 个底数; // 再加 1795265022 可覆盖无符号 64 位(2^64 以内) boolisPrime(ll n){ if (n < 2) returnfalse; for (ll p : {2LL, 3LL, 5LL, 7LL, 11LL, 13LL, 17LL, 19LL, 23LL, 29LL, 31LL, 37LL}) if (n % p == 0) return n == p; // 小素数直接整除判断 ll bases[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; for (ll a : bases) if (!millerRabin(n, a)) returnfalse; returntrue; }
注意点 / 坑点:
x * x % n 在 n ≥ 4.6e9 时会溢出,判素模板里的乘法必须用 __int128 包装。
先处理小素数整除:否则底数 a 恰好整除 n 时 a^(n-1) mod n 可能算出 0 或错误结果(模板中 n % a == 0 的提前判断就是为此)。
#include<bits/stdc++.h> usingnamespace std; using ll = longlong;
ll mul(ll a, ll b, ll mod){ return (ll)((__int128)a * b % mod); }
ll qpow(ll a, ll b, ll mod){ ll res = 1 % mod; a %= mod; while (b) { if (b & 1) res = mul(res, a, mod); a = mul(a, a, mod); b >>= 1; } return res; }
// Miller-Rabin 判素(确定性 64 位),详见 4.3 节 boolisPrime(ll n){ if (n < 2) returnfalse; for (ll p : {2LL, 3LL, 5LL, 7LL, 11LL, 13LL, 17LL, 19LL, 23LL, 29LL, 31LL, 37LL}) if (n % p == 0) return n == p; ll bases[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; for (ll a : bases) { ll d = n - 1, s = 0; while (!(d & 1)) { d >>= 1; s++; } ll x = qpow(a, d, n); if (x == 1 || x == n - 1) continue; bool ok = false; for (int i = 1; i < s; i++) { x = mul(x, x, n); if (x == n - 1) { ok = true; break; } } if (!ok) returnfalse; } returntrue; }
// ---------- Pollard-Rho:返回 n 的一个非平凡因子(1 < d < n) ---------- mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll pollardRho(ll n){ if (n % 2 == 0) return2; // 偶数直接返回 if (n % 3 == 0) return3; while (true) { ll c = uniform_int_distribution<ll>(1, n - 1)(rng); // 随机常数 ll x = uniform_int_distribution<ll>(0, n - 1)(rng); ll y = x, d = 1; // f(v) = (v*v + c) mod n,乘法必须用 __int128 auto f = [&](ll v) { return (mul(v, v, n) + c) % n; }; for (int i = 1, k = 2; d == 1; i++) { x = f(x); // 快指针每次走一步 d = gcd(x > y ? x - y : y - x, n); // 慢指针由 k 控制每隔一段追上 if (i == k) { y = x; k <<= 1; } // Floyd 判环:周期加倍 } if (d != n) return d; // d==n 说明本次随机失败,重试 } }
// ---------- 递归分解全部质因子(结果无序,含重数) ---------- voidfactor(ll n, vector<ll> &res){ if (n == 1) return; if (isPrime(n)) { res.push_back(n); return; } // 已经是素数,直接记录 ll d = pollardRho(n); factor(d, res); // 递归分解两个部分 factor(n / d, res); }
一句话用途:在模意义下做除法:a/b mod p 需要先求 b 的逆元 inv(b),使 b·inv(b)≡1 (mod p)。四种方法覆盖所有场景:费马小定理(p 为素数)、exgcd(模数可为合数但要求互素)、线性递推(批量求 1..n 的逆元)、阶乘逆元(组合数预处理)。
算法思想:费马小定理:p 为素数且 p∤a 时 a^(p−1)≡1 (mod p),所以 a 的逆元是 a^(p−2) mod p。exgcd 把 ax≡1 (mod m) 化为 ax+my=1 用 4.2 求解。线性递推公式:inv[i] = (m − ⌊m/i⌋·inv[m mod i]) mod m,利用 m mod i < i 保证可从前面的值推出。阶乘逆元先算 fac[n] 的逆元,再倒推 ifac[i−1] = ifac[i]·i,从而 O(1) 求组合数。
#include<bits/stdc++.h> usingnamespace std; using ll = longlong;
ll qpow(ll a, ll b, ll mod){ ll res = 1 % mod; a %= mod; while (b) { if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; }
// ---------- 单个欧拉函数:phi(n) = n * prod(1 - 1/p) ---------- ll eulerPhi(ll n){ ll res = n; for (ll i = 2; i * i <= n; i++) { // 只需枚举到 sqrt(n) if (n % i == 0) { res = res / i * (i - 1); // 先除后乘,防溢出 while (n % i == 0) n /= i; // 把质因子 i 全部除掉,保证下次 i 是新的质因子 } } if (n > 1) res = res / n * (n - 1); // 剩余的大于 sqrt 的质因子 return res; }
// ---------- 线性筛求欧拉函数表(与 4.5 相同,独立给出) ---------- constint N = 1000000; int phi[N + 1], primes[N + 1], cnt; bool isComp[N + 1]; voidphiTable(int n){ phi[1] = 1; for (int i = 2; i <= n; i++) { if (!isComp[i]) { primes[++cnt] = i; phi[i] = i - 1; } for (int j = 1; j <= cnt && (ll)i * primes[j] <= n; j++) { int p = primes[j]; isComp[i * p] = true; if (i % p == 0) { phi[i * p] = phi[i] * p; break; } // p 是 i 的因子 phi[i * p] = phi[i] * (p - 1); // i 与 p 互素 } } }
// ---------- 扩展欧拉定理降幂:求 a^b mod m,其中 b 以十进制字符串给出 ---------- // 核心:读 b 的过程中边读边对 phi(m) 取模,同时标记 b 是否 >= phi(m) ll superPow(string a, string b, ll m){ if (m == 1) return0; // 模 1 恒为 0 ll ph = eulerPhi(m); ll e = 0; bool big = false; // b 是否 >= phi(m) for (char c : b) { e = e * 10 + (c - '0'); if (e >= ph) { e %= ph; big = true; } // 边读边取模,防止 ll 溢出 } if (big) e += ph; // 关键:b >= phi(m) 时指数要加上 phi(m) // 把 a 也转成 ll 取模(若 a 也是大数,同样边读边取模) ll aa = 0; for (char c : a) aa = (aa * 10 + (c - '0')) % m; returnqpow(aa, e, m); }
注意点 / 坑点:
扩展欧拉定理两个分支别搞混:b < φ(m) 时指数就是 b;b ≥ φ(m) 时指数是 b mod φ(m) + φ(m)。只取余不加 φ(m) 在 gcd(a,m)≠1 时会错。
#include<bits/stdc++.h> usingnamespace std; using ll = longlong;
ll exgcd(ll a, ll b, ll &x, ll &y){ if (!b) { x = 1; y = 0; return a; } ll g = exgcd(b, a % b, y, x); y -= a / b * x; return g; }
// ---------- 标准 CRT:模数 m[] 两两互素 ---------- // 返回最小非负整数解;通解为 ans + k*M ll crt(const vector<ll> &a, const vector<ll> &m){ ll M = 1, ans = 0; for (ll x : m) M *= x; for (int i = 0; i < (int)a.size(); i++) { ll Mi = M / m[i]; // 除第 i 个模数外的乘积 ll x, y; exgcd(Mi % m[i], m[i], x, y); // 求 Mi 模 m[i] 的逆元 x = (x % m[i] + m[i]) % m[i]; // 防溢出:a[i] * Mi 可能超 ll,若 m 很大请改用 __int128 ans = (ans + (a[i] % M) * Mi % M * x) % M; } return ans; }
// ---------- 扩展 CRT:合并两个同余式 x≡a1 (mod m1)、x≡a2 (mod m2) ---------- // 成功返回 true,并把合并结果写到 (a, m);无解返回 false boolmerge(ll a1, ll m1, ll a2, ll m2, ll &a, ll &m){ ll x, y; ll g = exgcd(m1, m2, x, y); // 先用 exgcd 求 gcd 及一组系数 ll c = a2 - a1; if (c % g != 0) returnfalse; // 无解:c 必须被 gcd 整除 ll m2g = m2 / g; // 约分后的模数 // 解 m1*t ≡ c (mod m2):两边同除 g 后 t ≡ (c/g) * x (mod m2/g) // 其中 x 满足 (m1/g)*x ≡ 1 (mod m2/g) ll t = (c / g) % m2g * x % m2g; // 注意先对 m2g 取模防溢出 t = (t % m2g + m2g) % m2g; // t 取最小非负 a = a1 + m1 * t; // 新同余式的余数(可能很大,必要时 __int128) m = m1 / g * m2; // 新模数 = lcm(m1, m2) a = (a % m + m) % m; // 归一化到 [0, m) returntrue; }
一句话用途:计算 C(n,k) mod p,其中 p 是较小的素数而 n、k 可以非常大(≥ 1e18)。当 n ≥ p 时阶乘预处理会因 fac 含 p 因子而失效(模 p 下为 0 无法求逆),Lucas 定理把 n、k 按 p 进制拆位递归求解。p 为合数时用扩展 Lucas(思路一句话见下)。
算法思想:Lucas 定理:C(n,k) ≡ C(⌊n/p⌋, ⌊k/p⌋) · C(n mod p, k mod p) (mod p)。递归直到 k 为 0;每层的 C 因为两个参数都 < p,可以直接用阶乘 + 逆元计算。证明方向:利用 (1+x)^p ≡ 1+x^p (mod p) 的二项式展开系数对比。扩展 Lucas:把 p 分解为 ∏pᵢ^eᵢ,对每个素因子幂单独计算 C(n,k) mod pᵢ^eᵢ(把 n! 中 pᵢ 因子全部提出并单独计数,剩余部分模 pᵢ^eᵢ 可逆,配合递推算”不含 pᵢ 因子的阶乘”,最后用 CRT 合并)。
复杂度:Lucas O(p + log_p n)(预处理阶乘 O(p),递归 log_p n 层每层 O(1))。扩展 Lucas O(∑pᵢ^eᵢ + 总因子数·log) 级别。
#include<bits/stdc++.h> usingnamespace std; using ll = longlong;
ll qpow(ll a, ll b, ll mod){ ll res = 1 % mod; a %= mod; while (b) { if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; }
// ---------- 预处理阶乘(模 p,p 为素数,1 <= n < p) ---------- vector<ll> fac; voidinitFac(ll p){ fac.assign(p, 1); // 只开到 p:n mod p < p for (ll i = 1; i < p; i++) fac[i] = fac[i - 1] * i % p; }
// 小组合数:0 <= n,k < p ll smallC(ll n, ll k, ll p){ if (k < 0 || k > n) return0; return fac[n] * qpow(fac[k], p - 2, p) % p * qpow(fac[n - k], p - 2, p) % p; }
// ---------- Lucas 定理 ---------- // 使用前必须先调用 initFac(p)(按当前模数 p 预处理阶乘),p 变了要重新初始化 ll lucas(ll n, ll k, ll p){ if (k == 0) return1; // 递归边界 returnsmallC(n % p, k % p, p) * lucas(n / p, k / p, p) % p; }
扩展 Lucas 思路(一句话 + 关键代码):分解 p = ∏ pᵢ^eᵢ,对每个 pᵢ^eᵢ 用”提出 pᵢ 因子 + 处理 pᵢ 无关部分”的专用函数算出 C(n,k) mod pᵢ^eᵢ,最后 CRT 合并。核心专用函数如下(以单个素因子幂 pk 为例):
1 2 3 4 5 6 7 8 9 10 11 12 13 14
// 计算 n! 去掉所有 p 因子后模 pk 的值(n! 中 p 的个数单独统计) ll facMod(ll n, ll p, ll pk){ if (n == 0) return1; // 每 pk 个一组循环(1..pk 中与 p 互素的部分模 pk 有周期 pk),组数内快速幂 ll res = 1; for (ll i = 1; i <= pk; i++) if (i % p) res = res * (i % pk) % pk; // 一个完整周期的乘积 res = qpow(res, n / pk, pk); // 完整周期部分 for (ll i = 1; i <= n % pk; i++) // 余数部分 if (i % p) res = res * (i % pk) % pk; return res * facMod(n / p, p, pk) % pk; // 递归:n/p! 中还含有 p 的倍数 } // 计算 C(n,k) mod pk:f = facMod(n)*inv(facMod(k))*inv(facMod(n-k)) * p^(c) // 其中 c = (n!中p的个数) - (k!中p的个数) - ((n-k)!中p的个数),用勒让德公式计算
注意点 / 坑点:
Lucas 前提是 p 为素数:p 为合数时阶乘逆元不存在(fac 里含 p 的因子),必须走扩展 Lucas。
三维分块 r = min(n/(n/l), m/(m/l), k/(k/l)) 处理多变量下取整乘积。
典型例题类型:
求 ∑⌊n/i⌋(洛谷 P3935 的组成部分、POJ 的整除分块入门题)。
反演 + 分块求 gcd 计数(洛谷 P2522 Problem b)。
求和式涉及 ⌊n/i⌋·⌊m/i⌋ 的题目(如 HDU 1695 GCD)。
4.13 线性基
一句话用途:维护一个数的集合,支持 O(log V) 插入、求子集异或最大值/最小值、求子集异或第 k 小、判断某数能否由子集异或得到、统计子集异或的个数。本质是对向量空间在 GF(2) 上的高斯消元,是”子集异或”类题目的标准工具。
算法思想:线性基是一个数组 p[i](最高位为 i 的基向量),插入 x 时从高位到低位扫描:若 x 的第 i 位为 1 且 p[i] 为空则放入并结束;否则 x ^= p[i] 继续向低位。这样保证每个 p[i] 的最高位是 i,且集合中任意数的异或都能由基线性表出。最大值:从高位向低位贪心,若 x^p[i] > x 则异或。第 k 小:先”重建”把基化成每行只有最高位和更低位的”行阶梯形”(对每个 p[i],用低位 p[j] 消去其低位的 1),收集非零基向量 v,则第 k 小 = 按 k 的二进制位异或对应的 v。
// 插入 x;返回是否插入成功(false 说明 x 可由现有基表出,即出现线性相关) boolinsert(ll x){ for (int i = MAXB; i >= 0; i--) { if (!(x >> i & 1)) continue; // 第 i 位为 0 直接跳过 if (!p[i]) { p[i] = x; returntrue; } x ^= p[i]; // 消去第 i 位,继续向低位 } returnfalse; // x 被消成 0:线性相关 }
// 判断 x 能否由集合子集异或得到 boolexist(ll x){ for (int i = MAXB; i >= 0; i--) { if (!(x >> i & 1)) continue; if (!p[i]) returnfalse; x ^= p[i]; } return x == 0; }
// 求集合子集异或能得到的最大值(可指定初始值 x,如初始 0) ll maxXor(ll x = 0){ for (int i = MAXB; i >= 0; i--) x = max(x, x ^ p[i]); // 贪心:异或后更大就异或 return x; }
// 求第 k 小(k 从 0 开始计数,kth(0) 是最小值): // 先把基重建为行阶梯形——对每个 p[i],用所有更低位的 p[j] 消掉它低位的 1, // 使每个 p[i] 只保留最高位与若干更低位,且任意两行最高位不同 voidrebuild(){ for (int i = MAXB; i >= 0; i--) for (int j = i - 1; j >= 0; j--) if (p[i] >> j & 1) p[i] ^= p[j]; }
// 重建后调用:返回第 k 小(0 <= k < 2^sz),k 超出可表示个数返回 -1 ll kth(ll k){ rebuild(); vector<ll> v; // 收集非零基向量(下标小的对应低位) for (int i = 0; i <= MAXB; i++) if (p[i]) v.push_back(p[i]); // sz 个基向量表出 2^sz 个值;sz=63 时 2^63 超出 ll 表示范围,等价于 k 恒合法 if (v.size() < 63 && k >= (1LL << v.size())) return-1; ll res = 0; for (int i = 0; i < (int)v.size(); i++) if (k >> i & 1) res ^= v[i]; // 按 k 的二进制位选择基向量 return res; } };
// 应用示例:子集异或能得到的不同值个数 // 若插入时出现过线性相关(有 insert 返回 false),则 0 可由非空子集得到, // 不同值个数 = 2^sz;否则 = 2^sz - 1(不含 0) // 注意:sz=63 时 2^63 超出 ll,需改用 unsigned long long 或 __int128 ll distinctCount(const LinearBasis &b){ int sz = 0; for (int i = 0; i <= MAXB; i++) if (b.p[i]) sz++; return (sz == 63) ? LLONG_MAX : (1LL << sz); }
注意点 / 坑点:
求第 k 小前必须先 rebuild:不重建直接按 k 的二进制选 p[i] 是错的(p[i] 可能含更高位的基的影子)。
插入时位循环要从高到低(MAXB 到 0),方向反了会破坏 p[i] 最高位为 i 的不变量。
k 从 0 开始且 kth(0)=0;若集合本身不含 0(无线性相关)且题目要求”非空子集的第 k 小”,需要把 k 加 1 再查。
算法思想:取 m = ⌈√p⌉,任意 x ∈ [0, p) 可唯一写成 x = i·m + j(0 ≤ i ≤ m,0 ≤ j < m)。等式 a^(i·m+j) ≡ b 等价于 a^j ≡ b·a^(−i·m)。于是先把所有 a^j (0 ≤ j < m) 存入哈希表(小步),再枚举 i 查表(大步):对每个 i 计算 t = b·a^(−i·m) mod p,若 t 在表中,则 x = i·m + j 即答案。a 与 p 互素保证 a^(−m) 存在(用快速幂求逆元)。
#include<bits/stdc++.h> usingnamespace std; using ll = longlong;
ll qpow(ll a, ll b, ll mod){ ll res = 1 % mod; a %= mod; while (b) { if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; }
// 求最小非负整数 x 满足 a^x ≡ b (mod p),p 为素数(或 gcd(a,p)=1),无解返回 -1 ll bsgs(ll a, ll b, ll p){ a %= p; b %= p; if (b == 1) return0; // x = 0 恒成立(含 a=0 的情形) if (a == 0) return b == 0 ? 1 : -1; // 0^x ≡ 0 仅当 x>=1,最小为 1 ll m = (ll)ceil(sqrt((double)p)); // 大步步长:m = ceil(sqrt(p)) unordered_map<ll, ll> baby; // 小步表:a^j -> j ll cur = 1; for (ll j = 0; j < m; j++) { if (!baby.count(cur)) baby[cur] = j; // 只记录第一次出现(保证最小 x) cur = cur * a % p; // cur = a^j } // 大步:t_i = b * a^(-i*m),查表得 j,则 x = i*m + j ll invAm = qpow(qpow(a, m, p), p - 2, p); // a^(-m) = (a^m)^(-1),费马求逆 ll t = b; for (ll i = 0; i <= m; i++) { if (baby.count(t)) return i * m + baby[t]; t = t * invAm % p; // t 递推:乘一次 a^(-m) } return-1; // 枚举完没找到:无解 }
exBSGS 思路(一句话):当 gcd(a,p) ≠ 1 时,把方程两边和模数同时除以 g = gcd(a,p):若 b % g ≠ 0 且 b ≠ 1 则无解,否则 a/g·a^(x−1) ≡ b/g (mod p/g),记下系数并递归处理 a^(x−1) ≡ b’ (mod p’),直到互素后用普通 BSGS,最后答案加上递归层数 k(同时特判小 x 的情况)。
注意点 / 坑点:
b == 1 时直接返回 0:x=0 是最小解,走通用流程会因 i*m+j 可能更大而错。
m 取 ⌈√p⌉:取 ⌊√p⌋ 时可能漏解(x 的最大值接近 p,需要 i 枚举到 m)。
小步表只存”第一次出现”的 j:若后面覆盖,会丢掉更小的解。
大步的 t 要从 b 开始(i=0 时 t=b),循环 i 从 0 到 m,别从 1 开始。
p 为合数且 gcd(a,p)≠1 时费马求逆失效:必须用 exBSGS 或先保证 a 与 p 互素。
用 unordered_map 时小心被卡哈希(可换 gp_hash_table 或自写哈希表)。
可拓展的地方:
exBSGS 处理模数不互素,模板见上思路,配合扩展欧几里得推导。
BSGS 可以处理”指数型同余方程”及”求 a^x ≡ b 的所有解(x 有周期 φ(p))”。
配合原根(4.16)可把”模 p 意义下的乘法”转化为”指数加法”,用于 NTT 的阶分析。
典型例题类型:
求离散对数(洛谷 P3846 【模板】BSGS、SPOJ MOD 等)。
exBSGS:模数不互素(洛谷 P4195 【模板】扩展 BSGS)。
密码学背景 / 指数方程变形(如 poj 2417 Discrete Logging)。
4.16 原根与离散对数
一句话用途:求模素数 p 的最小原根 g(g 的 1..p−1 次幂恰好遍历 1..p−1 全部非零剩余类,即 g 是模 p 乘法群的生成元),并利用原根把乘法问题转化为指数加法(离散对数),是 NTT(数论变换)找单位根、密码学 Diffie-Hellman 密钥交换的理论基础。
算法思想:g 是模 p 的原根当且仅当 g 的阶为 φ(p)=p−1。检验方法:对 p−1 的每个质因子 q,若 g^((p−1)/q) ≠ 1 (mod p) 对所有 q 成立,则 g 是原根(因为 g 的阶若是 p−1 的真因子 d,则存在 q | (p−1)/d,使 g^((p−1)/q) ≡ 1)。最小原根数值通常很小(p 为素数时平均约 3),从 g=2 开始逐个试。离散对数:给定 g 和 a,求 x 使 g^x ≡ a (mod p),用 4.15 的 BSGS 求解;原根保证对任意 a≠0 解都存在且唯一(模 p−1 意义下)。
有向图游戏、Anti-Nim(取走最后一颗石子者负)、阶梯 Nim(偶数堆石子挪到奇数层)都是 Nim 结论的推广。
SG 与”删边游戏””树上的博弈”结合(如 Green Hackenbush),可用 SG 定理拆解。
典型例题类型:
Nim 裸题与变形(POJ 2234 Matches Game、洛谷 P2197)。
SG 函数打表找规律(HDU 1847、洛谷 P4018 等取石子系列)。
巴什/威佐夫裸题(HDU 1846 Brave Game、POJ 1067 取石子游戏)。
4.18 组合数取模
一句话用途:计算 C(n,k) mod p。常规做法是阶乘 + 逆元预处理,O(1) 单次查询;前提是 p 为素数且 n < p。当 n 很大(≥ p 甚至 1e18)时,预处理因 fac 含 p 的因子而失效,改用 Lucas 定理(4.9);p 为合数用扩展 Lucas。本节给出可直接用的完整模板。
算法思想:C(n,k) = n! / (k!·(n−k)!)。预处理 fac[i]=i! mod p 与 ifac[i]=(i!)⁻¹ mod p(ifac 由 fac[n] 的逆元倒推,见 4.6),则 C(n,k) = fac[n]·ifac[k]·ifac[n−k] mod p。n、k 上限由预处理数组大小决定(n 多大数组开多大,一般 ≤ 1e7)。若 n ≥ p,fac[n] 含有因子 p,模 p 下为 0 无法求逆,此时必须用 Lucas(4.9)逐层拆 p 进制。
复杂度:预处理 O(n);单次查询 O(1)。空间 O(n)。(配合 Lucas 后查询 O(log_p n)。)
// Z 函数:z[i] = s 与后缀 s[i..] 的最长公共前缀长度(约定 z[0] = 0) vector<int> z_function(const string& s){ int n = (int)s.size(); vector<int> z(n, 0); int l = 0, r = 0; // 当前最靠右的匹配段 [l, r](闭区间) for (int i = 1; i < n; i++) { if (i <= r) z[i] = min(r - i + 1, z[i - l]); // 借用镜像位置 i-l 的已知值 while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++; // 朴素扩展 if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; } // 更新最右匹配段 } return z; }
// 扩展 KMP:返回 ext,ext[i] = a 的后缀 a[i..] 与 b 的最长公共前缀长度 vector<int> ex_kmp(const string& a, const string& b){ string t = b + "#" + a; // '#' 必须是不出现在 a、b 中的字符 vector<int> z = z_function(t); int m = (int)b.size(); vector<int> ext(a.size()); for (int i = 0; i < (int)a.size(); i++) ext[i] = z[m + 1 + i]; // b + '#' 共占 m+1 个位置 return ext; }
// 应用:统计 b 在 a 中的出现次数(LCP == m 即匹配一次) intcount_occ(const string& a, const string& b){ vector<int> ext = ex_kmp(a, b); int cnt = 0; for (int x : ext) if (x == (int)b.size()) cnt++; return cnt; }
intmain(){ string a, b; cin >> a >> b; vector<int> ext = ex_kmp(a, b); for (int i = 0; i < (int)ext.size(); i++) printf("%d ", ext[i]); return0; }
voidinsert(const string& s, int val = 1){ // 插入一个模式串 int u = 0; for (char c : s) { int v = c - 'a'; if (!trie[u][v]) { trie[u][v] = ++tot; memset(trie[tot], 0, sizeof(trie[tot])); // 新节点转移清零 } u = trie[u][v]; } cnt[u] += val; // 重复模式串:累加而不是覆盖 }
voidbuild(){ // BFS 构建 fail 指针,并补全转移成 trie 图 int head = 0, tail = 0; for (int i = 0; i < 26; i++) // 根的第一层孩子入队,其 fail 指向根 if (trie[0][i]) q[tail++] = trie[0][i]; while (head < tail) { int u = q[head++]; for (int i = 0; i < 26; i++) { int v = trie[u][i]; if (v) { fail[v] = trie[fail[u]][i]; // 父节点 fail 的同字符孩子 q[tail++] = v; } else { trie[u][i] = trie[fail[u]][i]; // 补全缺失转移(trie 图) } } } }
// 匹配文本串,返回所有模式串出现次数之和(每个模式串至多被统计一次) longlongquery(const string& s){ longlong ans = 0; int u = 0; for (char c : s) { u = trie[u][c - 'a']; // 自动机走一步(trie 图保证必有转移) for (int v = u; v && cnt[v] != -1; v = fail[v]) { // 沿 fail 链统计 ans += cnt[v]; cnt[v] = -1; // 置 -1:本次运行不再重复统计 } } return ans; } };
intmain(){ int n; string s; cin >> n; ACAuto ac; for (int i = 0; i < n; i++) { cin >> s; ac.insert(s); } ac.build(); cin >> s; printf("%lld\n", ac.query(s)); return0; }
char s[MAXN]; int n; int sa[MAXN], rk[MAXN], tmp[MAXN], cnt[MAXN], height[MAXN];
// 倍增 + 基数排序求后缀数组 voidbuild_sa(){ int m = 256; // 计数数组大小:字符值域(ASCII 0..255,可先离散化缩小) // 第一轮:按单个字符基数排序 for (int i = 0; i < n; i++) rk[i] = (unsignedchar)s[i]; // 防 char 为负数 for (int i = 0; i < n; i++) cnt[rk[i]]++; for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1]; for (int i = n - 1; i >= 0; i--) sa[--cnt[rk[i]]] = i; // 倒序放置保证稳定 for (int k = 1; k < n; k <<= 1) { int p = 0; // 先按第二关键字排序:第二关键字越界(视为 -1)的后缀排最前 for (int i = n - k; i < n; i++) tmp[p++] = i; for (int i = 0; i < n; i++) if (sa[i] >= k) tmp[p++] = sa[i] - k; // 再按第一关键字(旧 rk)做一次稳定基数排序,得到新 sa memset(cnt, 0, sizeof(int) * m); for (int i = 0; i < n; i++) cnt[rk[tmp[i]]]++; for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1]; for (int i = n - 1; i >= 0; i--) sa[--cnt[rk[tmp[i]]]] = tmp[i]; // 由新 sa 重算 rk(tmp 暂存旧的 rk,swap 后再用) swap(rk, tmp); rk[sa[0]] = 0; p = 1; for (int i = 1; i < n; i++) { int a = sa[i], b = sa[i - 1]; bool same = (tmp[a] == tmp[b]) && ((a + k < n ? tmp[a + k] : -1) == (b + k < n ? tmp[b + k] : -1)); rk[a] = same ? p - 1 : p++; } if (p == n) break; // 所有排名互不相同,提前结束 m = p; // 缩小计数数组范围(值域 = 当前排名数) } }
// height[i] = LCP(sa[i], sa[i-1]),height[0] 无意义(恒为 0) voidbuild_height(){ int k = 0; for (int i = 0; i < n; i++) { if (rk[i] == 0) { k = 0; continue; } // 排名第一的后缀没有前驱 int j = sa[rk[i] - 1]; while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++; height[rk[i]] = k; if (k) k--; // 关键性质:height[rk[i+1]] >= height[rk[i]] - 1 } }
// ST 表:任意两后缀的 LCP = 它们在 sa 中区间内 height 的最小值 int st[MAXN][18], lg2[MAXN]; voidbuild_st(){ for (int i = 2; i <= n; i++) lg2[i] = lg2[i >> 1] + 1; for (int i = 1; i < n; i++) st[i][0] = height[i]; for (int j = 1; (1 << j) < n; j++) for (int i = 1; i + (1 << j) - 1 < n; i++) st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]); }
// 后缀 i 与后缀 j(0 下标)的 LCP,O(1) intget_lcp(int i, int j){ if (i == j) return n - i; int l = rk[i], r = rk[j]; if (l > r) swap(l, r); l++; // 区间为 (l, r],即 [l+1, r] int len = r - l + 1, k = lg2[len]; returnmin(st[l][k], st[r - (1 << k) + 1][k]); }
intmain(){ scanf("%s", s); n = (int)strlen(s); build_sa(); build_height(); build_st(); for (int i = 0; i < n; i++) printf("%d ", sa[i] + 1); // 常用 1 下标输出 return0; }
注意点 / 坑点:
计数数组 cnt 的大小必须覆盖字符值域:第一轮要 ≥ 字符集大小(ASCII 用 256),之后每轮 m 更新为当前排名数 p,memset 范围也要随 m 变化,写死或漏更新会越界或排序错误。
structSuffixAutomaton { structState { int len, link, next[26]; } st[MAXS]; int sz, last; // 状态总数、当前整个串对应的状态 int cnt[MAXS]; // cnt[u]:状态 u 直接代表的 endpos 个数(克隆节点为 0) int num[MAXS]; // num[u]:状态 u 中任意子串的出现次数(endpos 大小) int order[MAXS]; // 按 len 基数排序后的状态顺序
voidextend(int c){ int cur = sz++; st[cur].len = st[last].len + 1; cnt[cur] = 1; // 只有非克隆节点初始 cnt 为 1 memset(st[cur].next, 0, sizeof(st[cur].next)); int p = last; while (p != -1 && st[p].next[c] == 0) { // 沿 link 链补转移 st[p].next[c] = cur; p = st[p].link; } if (p == -1) { st[cur].link = 0; // 新串是全新前缀,link 直接连根 } else { int q = st[p].next[c]; if (st[p].len + 1 == st[q].len) { st[cur].link = q; // q 恰好代表以 c 结尾的最长后缀 } else { int clone = sz++; // 分裂:克隆 q st[clone] = st[q]; // 整体复制 q(len、link、全部 next) st[clone].len = st[p].len + 1; cnt[clone] = 0; // 克隆节点不新增 endpos while (p != -1 && st[p].next[c] == q) { // 把指向 q 的转移改指 clone st[p].next[c] = clone; p = st[p].link; } st[q].link = st[cur].link = clone; // q 与 cur 的 link 都指向 clone } } last = cur; }
// 按 len 基数排序后自底向上累加,得到每个状态的出现次数 voidcalc_cnt(){ staticint bucket[MAXS]; for (int i = 0; i < sz; i++) bucket[st[i].len]++; for (int i = 1; i < sz; i++) bucket[i] += bucket[i - 1]; for (int i = sz - 1; i >= 0; i--) order[--bucket[st[i].len]] = i; for (int i = 0; i < sz; i++) num[i] = cnt[i]; for (int i = sz - 1; i >= 0; i--) { // len 从大到小处理 int v = order[i]; if (st[v].link != -1) num[st[v].link] += num[v]; // 并入 link 父状态 } }
// 本质不同子串数 = Σ (len[u] - len[link[u]]) longlongdiff_substr(){ longlong res = 0; for (int i = 1; i < sz; i++) res += st[i].len - st[st[i].link].len; return res; } };
// 返回 s 的最小表示(字典序最小的循环同构)的起始下标(0 下标) intmin_representation(const string& s){ int n = (int)s.size(); int i = 0, j = 1, k = 0; // i、j:两个候选起点;k:已比较长度 while (i < n && j < n && k < n) { char a = s[(i + k) % n]; // 用取模模拟循环 char b = s[(j + k) % n]; if (a == b) { k++; continue; } if (a > b) { // 起点 i 更差:跳过 [i, i+k] 内所有起点 i += k + 1; if (i == j) i++; // 避免两个指针相同 } else { // 起点 j 更差 j += k + 1; if (i == j) j++; } k = 0; } returnmin(i, j); }
// 构造 s 的最小表示串 string min_rotation(const string& s){ int pos = min_representation(s); int n = (int)s.size(); string res; for (int i = 0; i < n; i++) res += s[(pos + i) % n]; return res; }
#include<bits/stdc++.h> usingnamespace std; constint N = 6005; int n, r[N], dp[N][2]; // dp[u][0]: u 不去; dp[u][1]: u 去 vector<int> g[N]; bool isRoot[N];
voiddfs(int u){ dp[u][1] = r[u]; // 选 u,先累加 u 的快乐值 for (int v : g[u]) { dfs(v); // 先递归子树(自底向上) dp[u][0] += max(dp[v][0], dp[v][1]); // u 不去:子节点可去可不去 dp[u][1] += dp[v][0]; // u 去:子节点必须不去 } }
intmain(){ cin >> n; for (int i = 1; i <= n; i++) cin >> r[i]; fill(isRoot + 1, isRoot + n + 1, true); for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; // 输入:v 是 u 的上司(父亲) g[v].push_back(u); isRoot[u] = false; } int root = 1; while (!isRoot[root]) root++; // 找到根 dfs(root); cout << max(dp[root][0], dp[root][1]) << '\n'; return0; }
#include<bits/stdc++.h> usingnamespace std; using ll = longlong; constint N = 1000005; int n; vector<int> g[N]; ll sz[N], f[N]; // sz[u]: 子树大小; f[u]: 以 u 为根子树内所有点到 u 的距离和
voiddfs1(int u, int fa){ // 第一次 DFS:自底向上 sz[u] = 1; for (int v : g[u]) if (v != fa) { dfs1(v, u); sz[u] += sz[v]; f[u] += f[v] + sz[v]; // v 子树内每个点都多走一步到达 u } }
voiddfs2(int u, int fa){ // 第二次 DFS:自顶向下换根 for (int v : g[u]) if (v != fa) { // 根从 u 换到 v:v 子树内所有点距离 -1,其余点距离 +1 f[v] = f[u] - sz[v] + (n - sz[v]); dfs2(v, u); } }
intmain(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } dfs1(1, 0); // 以 1 为根先算一次 dfs2(1, 0); // 再换根到所有点 int ans = 1; for (int i = 2; i <= n; i++) if (f[i] > f[ans]) ans = i; // 找距离和最小的点 cout << ans << '\n'; return0; }
注意点 / 坑点:
树形 DP 必须先递归完子树再更新父节点,顺序反了会用到未初始化的子状态。
树形背包的容量枚举必须倒序,且 k 从 1 到 j-1(不能取 k = j,否则与 dp[u][j-k] 冲突);若整棵子树只能整体选/不选,则是另一种树形 01 背包。
#include<bits/stdc++.h> usingnamespace std; constint N = 20, INF = 0x3f3f3f3f; int n, d[N][N]; int dp[1 << N][N]; // dp[mask][i]: 已访问集合为 mask、当前停在 i 的最短距离
intmain(){ cin >> n; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> d[i][j]; memset(dp, 0x3f, sizeof dp); // 全部初始化为 INF(不可达) dp[1][0] = 0; // 起点是城市 0,只访问了 0 for (int S = 1; S < (1 << n); S++) { // 枚举集合状态 for (int i = 0; i < n; i++) if ((S >> i) & 1) { // i 必须在集合内 if (dp[S][i] == INF) continue; // 跳过不可达状态 for (int j = 0; j < n; j++) if (!((S >> j) & 1)) // j 未访问 dp[S | (1 << j)][j] = min(dp[S | (1 << j)][j], dp[S][i] + d[i][j]); } } int ans = INF; for (int i = 1; i < n; i++) // 最后回到起点 0 ans = min(ans, dp[(1 << n) - 1][i] + d[i][0]); cout << ans << '\n'; return0; }
枚举子集技巧(O(3ⁿ) 遍历所有集合的所有非空子集):
1 2 3
for (int sub = S; sub; sub = (sub - 1) & S) { // 每次去掉最低位的 1 并保持与 S 相交 // 处理子集 sub(含 S 本身) }
#include<bits/stdc++.h> usingnamespace std; constint N = 100005; vector<pair<int, int>> rg[N]; // 反向图:v -> (u, w) int out[N], indeg[N]; // 原图出度、反向图入度 double dp[N]; // dp[u]: u 到终点 n 的期望路径长度
intmain(){ int n, m; cin >> n >> m; for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; rg[v].push_back({u, w}); // 建反向边,方便从终点倒推 out[u]++; indeg[u]++; // 反向图入度 = 原图出度 } queue<int> q; for (int i = 1; i <= n; i++) if (indeg[i] == 0) q.push(i); while (!q.empty()) { // 沿反向图做拓扑排序 int u = q.front(); q.pop(); for (auto &e : rg[u]) { int v = e.first, w = e.second; dp[v] += (dp[u] + w) / out[v]; // 从 v 出发每条出边等概率 if (--indeg[v] == 0) q.push(v); } } printf("%.2f\n", dp[1]); return0; }
算法思想:维护一个下标递增、值(dp[j])单调(取 max 递减、取 min 递增)的双端队列:每来一个新决策点,先从队尾弹出所有不如它的旧点(新点更靠右且值更优,旧点永远不会再被选),再入队;每次取最优时弹出队头所有已滑出窗口的点。队列头部始终是当前窗口内的最优决策点。这样每个点至多入队、出队一次,总复杂度 O(n)。滑动窗口取最值(洛谷 P1886)就是这个思想的裸题,直接接入 DP 即可。
#include<bits/stdc++.h> usingnamespace std; constint N = 200005, NEG = -0x3f3f3f3f; int n, l, r, a[N], dp[N]; int q[N], head, tail; // 手写单调队列存下标,dp 值单调递减
intmain(){ cin >> n >> l >> r; for (int i = 0; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) dp[i] = NEG; // 不可达标记 dp[0] = a[0]; head = tail = 0; for (int i = 1; i <= n; i++) { int add = i - l; // 新进入窗口的决策点 if (add >= 0 && dp[add] > NEG) { while (head < tail && dp[q[tail - 1]] <= dp[add]) tail--; // 弹出不如它的 q[tail++] = add; } int out = i - r - 1; // 滑出窗口的决策点 if (out >= 0 && head < tail && q[head] == out) head++; if (head < tail) dp[i] = dp[q[head]] + a[i]; // 队头是窗口内最优 } int ans = NEG; for (int i = max(0, n + 1 - l); i <= n; i++) // 能一步跳出 n 的格子才可结束 ans = max(ans, dp[i]); cout << ans << '\n'; return0; }
滑动窗口取最值的完整模板(洛谷 P1886 滑动窗口):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
#include<bits/stdc++.h> usingnamespace std; constint N = 1000005; int n, k, a[N]; deque<int> dq; // 存下标,a 值单调递减
intmain(){ cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) { while (!dq.empty() && dq.front() < i - k + 1) dq.pop_front(); // 滑出窗口 while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back(); // 维护单调递减 dq.push_back(i); if (i >= k) cout << a[dq.front()] << ' '; // 窗口 [i-k+1, i] 的最大值 } return0; }
注意点 / 坑点:
窗口边界要仔细:新决策点是 add = i - l,滑出窗口的是 out = i - r - 1,差 1 就会错。
#include<bits/stdc++.h> usingnamespace std; constint N = 305, INF = 0x3f3f3f3f; int n, a[N], sum[N]; int dp[N][N], s[N][N]; // s[i][j]: dp[i][j] 取得最优时的断点 k
intmain(){ cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; sum[i] = sum[i - 1] + a[i]; } for (int i = 1; i <= n; i++) { dp[i][i] = 0; s[i][i] = i; } // 单堆区间 for (int len = 2; len <= n; len++) { for (int i = 1; i + len - 1 <= n; i++) { int j = i + len - 1; dp[i][j] = INF; // 决策单调性:最优断点只在 [s[i][j-1], s[i+1][j]] 中 for (int k = s[i][j - 1]; k <= s[i + 1][j]; k++) { if (dp[i][k] + dp[k + 1][j] < dp[i][j]) { dp[i][j] = dp[i][k] + dp[k + 1][j]; s[i][j] = k; // 记录最优断点 } } dp[i][j] += sum[j] - sum[i - 1]; // 加上本次合并代价 } } cout << dp[1][n] << '\n'; return0; }
补充:如何判断 w 是否满足四边形不等式(小数据打表验证,用于决定能否套用本优化):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
#include<bits/stdc++.h> usingnamespace std; using ll = longlong;
ll W(int a, int b){ /* 实际代价函数,如区间和 sum[b] - sum[a-1] */return0; }
// 验证 W 是否满足四边形不等式:W(a,c)+W(b,d) <= W(a,d)+W(b,c),对 a<=b<=c<=d boolcheckQuadrangle(int n){ for (int a = 1; a <= n; a++) for (int b = a; b <= n; b++) for (int c = b; c <= n; c++) for (int d = c; d <= n; d++) if (W(a, c) + W(b, d) > W(a, d) + W(b, c)) returnfalse; returntrue; // 全成立则 w 满足四边形不等式,可放心使用 O(n^2) 优化 }
#include<bits/stdc++.h> usingnamespace std; constint N = 105; int n, m, h[N][N], dp[N][N]; int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
intdfs(int x, int y){ if (dp[x][y] != -1) return dp[x][y]; // 已算过直接返回(记忆化) int best = 1; // 至少包含自己这个格子 for (int k = 0; k < 4; k++) { // 四个方向 int nx = x + dx[k], ny = y + dy[k]; if (nx < 1 || nx > n || ny < 1 || ny > m) continue; if (h[nx][ny] < h[x][y]) // 只能滑向更低处 best = max(best, dfs(nx, ny) + 1); } return dp[x][y] = best; // 记录并返回 }
intmain(){ cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> h[i][j]; memset(dp, -1, sizeof dp); int ans = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) ans = max(ans, dfs(i, j)); // 从任意格子出发取最大 cout << ans << '\n'; return0; }
博弈类 DP 的记忆化模板(局面 S 的先手是否必胜):
1 2 3 4 5 6
intdfs(int S){ // 返回 1 先手必胜,0 先手必败 if (memo[S] != -1) return memo[S]; for (每个合法走法 S -> T) if (!dfs(T)) return memo[S] = 1; // 存在一步走到必败态则必胜 return memo[S] = 0; // 所有走法都到必胜态则必败 }
#include<bits/stdc++.h> usingnamespace std; using ll = longlong; constint N = 15; int n, m, ex = -1, ey = -1; // 最后一个可走格子的坐标 char g[N][N]; int pw[N]; // pw[i] = 3^i
inlineintget(int s, int p){ return (s / pw[p]) % 3; } // 取第 p 位的值 inlineintsetv(int s, int p, int v){ return s + (v - get(s, p)) * pw[p]; }
// 括号匹配:p 处为 '(' 则向右找配对的 ')';为 ')' 则向左找 '(' intmatch(int s, int p){ if (get(s, p) == 1) { // 左括号:向右扫描 for (int q = p + 1, dep = 1; ; q++) { int v = get(s, q); if (v == 1) dep++; elseif (v == 2 && --dep == 0) return q; } } else { // 右括号:向左扫描 for (int q = p - 1, dep = 1; ; q--) { int v = get(s, q); if (v == 2) dep++; elseif (v == 1 && --dep == 0) return q; } } return-1; // 合法状态不会走到这里 }
intmain(){ cin >> n >> m; for (int i = 0; i < n; i++) { cin >> g[i]; // '.' 可走,'*' 障碍 for (int j = 0; j < m; j++) if (g[i][j] == '.') { ex = i; ey = j; } // 记录最后一个可走格 } if (ex == -1) { cout << 0 << '\n'; return0; } // 没有可走格 pw[0] = 1; for (int i = 1; i <= m; i++) pw[i] = pw[i - 1] * 3;
unordered_map<int, ll> mp[2]; // 滚动哈希表:状态 -> 方案数 int cur = 0; mp[cur][0] = 1; for (int i = 0; i < n; i++) { unordered_map<int, ll> nxt; // 换行:整体左移一位(三进制下乘 3) for (auto &pr : mp[cur]) nxt[pr.first * 3] = pr.second; mp[cur].swap(nxt); for (int j = 0; j < m; j++) { int nxtid = cur ^ 1; mp[nxtid].clear(); for (auto &pr : mp[cur]) { int s = pr.first; ll val = pr.second; int L = get(s, j), U = get(s, j + 1); // 左插头、上插头 if (g[i][j] == '*') { // 障碍:必须无插头 if (L == 0 && U == 0) mp[nxtid][s] += val; continue; } if (L == 0 && U == 0) { // 新建右、下插头 if (i + 1 < n && j + 1 < m && g[i + 1][j] == '.' && g[i][j + 1] == '.') mp[nxtid][setv(setv(s, j, 1), j + 1, 2)] += val; } elseif (L == 0 || U == 0) { // 单插头:转弯或直走 int v = L | U; int s1 = setv(setv(s, j, 0), j + 1, 0); if (i + 1 < n && g[i + 1][j] == '.') mp[nxtid][setv(s1, j, v)] += val; if (j + 1 < m && g[i][j + 1] == '.') mp[nxtid][setv(s1, j + 1, v)] += val; } else { // 双插头:合并 int s2 = setv(setv(s, j, 0), j + 1, 0); if (L == 1 && U == 1) { // ( ( :把 U 的配对 ) 改成 ( int q = match(s, j + 1); mp[nxtid][setv(s2, q, 1)] += val; } elseif (L == 2 && U == 2) { // ) ) :把 L 的配对 ( 改成 ) int q = match(s, j); mp[nxtid][setv(s2, q, 2)] += val; } elseif (L == 2 && U == 1) { // ) ( :连接两个连通块 mp[nxtid][s2] += val; } else { // ( ) :闭合回路,只能在最后格 if (i == ex && j == ey) mp[nxtid][s2] += val; } } } cur = nxtid; } } cout << mp[cur][0] << '\n'; // 无插头状态 = 恰好一条回路 return0; }
算法思想:Andrew 单调链法:先把点按 x 为第一关键字、y 为第二关键字排序并去重,然后分两次扫描构造凸包——从左到右构造下凸壳(只保留”左转”的顶点,遇到右转或共线就弹出栈顶),从右到左构造上凸壳,最后去掉重复的起点,得到按逆时针排列的凸包顶点。正确性依赖排序后的单调性:扫描过程中任何”凹陷”都会表现为右转而被弹出,最终保留下来的点全部左转,恰好围成凸多边形。
算法思想:分治:按 x 坐标排序后从中间切开,分别递归求两半内部的最近距离 d,再检查”中间带”——横坐标距分割线小于 sqrt(d) 的点,因为任何跨越分割线的更优点对必然落在这个窄带内。带内点按 y 排序后,只需检查 y 差小于 sqrt(d) 的紧邻点对(几何上每点最多与常数个候选比较),即可在 O(n) 内完成合并。本模板在递归过程中用归并把区间按 y 排好序,保证每一层合并 O(n),总体严格 O(n log n)。
/* 比较的正确姿势:一律经 sgn 包装 */ booleq(double a, double b){ returnsgn(a - b) == 0; } // a == b boolne(double a, double b){ returnsgn(a - b) != 0; } // a != b boollt(double a, double b){ returnsgn(a - b) < 0; } // a < b boolgt(double a, double b){ returnsgn(a - b) > 0; } // a > b boolle(double a, double b){ returnsgn(a - b) <= 0; } // a <= b boolge(double a, double b){ returnsgn(a - b) >= 0; } // a >= b
#include<bits/stdc++.h> usingnamespace std; using ll = longlong;
const ll MOD = 998244353; // 需要是质数,且 N < MOD 才可用阶乘逆元 constint MAXN = 200000 + 5; ll fac[MAXN], ifac[MAXN];
ll qpow(ll a, ll b){ // 快速幂(费马小定理求逆元用) ll r = 1; for (; b; b >>= 1, a = a * a % MOD) if (b & 1) r = r * a % MOD; return r; }
voidinitComb(int n = MAXN - 1){ // 预处理阶乘与阶乘逆元 fac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % MOD; ifac[n] = qpow(fac[n], MOD - 2); // 先求最大的逆元,再倒推 for (int i = n; i >= 1; i--) ifac[i - 1] = ifac[i] * i % MOD; }
ll C(int n, int k){ // 组合数 C(n,k),越界返回 0 if (k < 0 || k > n) return0; return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD; }
ll P(int n, int k){ // 排列数 P(n,k) = n!/(n-k)! if (k < 0 || k > n) return0; return fac[n] * ifac[n - k] % MOD; }
// 容斥原理模板:求 [1, n] 中与 m 互质的数的个数 // 思路:与 m 互质 = 不含有 m 的任何质因子,用容斥对质因子集合取并的补 ll coprimeCount(ll n, ll m){ vector<ll> p; for (ll x = 2; x * x <= m; x++) // 分解 m 的不同质因子 if (m % x == 0) { p.push_back(x); while (m % x == 0) m /= x; } if (m > 1) p.push_back(m); // 剩下一个大于 sqrt 的质因子 int t = p.size(); ll ans = 0; for (int mask = 0; mask < (1 << t); mask++) { // 枚举质因子子集 ll prod = 1; int bits = 0; for (int i = 0; i < t; i++) if (mask >> i & 1) { prod *= p[i]; bits++; } // mask=0 时加 n(全集);奇数个因子减,偶数个因子加 if (bits & 1) ans -= n / prod; else ans += n / prod; } return ans; }
#include<bits/stdc++.h> usingnamespace std; using ll = longlong; using cd = complex<double>; constdouble PI = acos(-1.0);
// 迭代版 FFT:invert=false 正变换,invert=true 逆变换 voidfft(vector<cd>& a, bool invert){ int n = (int)a.size(); // 蝴蝶变换:把下标按二进制位逆序重排,使迭代合并时数据成对就位 for (int i = 1, j = 0; i < n; i++) { int bit = n >> 1; for (; j & bit; bit >>= 1) j ^= bit; // 模拟二进制加一求逆序 j ^= bit; if (i < j) swap(a[i], a[j]); // 只交换一次,避免重复 } for (int len = 2; len <= n; len <<= 1) { // len:当前合并的区间长度 double ang = 2 * PI / len * (invert ? -1 : 1); // 逆变换用负角度 cd wlen(cos(ang), sin(ang)); // len 次单位根 for (int i = 0; i < n; i += len) { cd w(1); for (int j = 0; j < len / 2; j++) { cd u = a[i + j]; // 上半部分 cd v = a[i + j + len / 2] * w; // 下半部分乘旋转因子 a[i + j] = u + v; a[i + j + len / 2] = u - v; w *= wlen; } } } if (invert) // 逆变换最后除以 n 完成缩放 for (cd& x : a) x /= n; }
// 多项式乘法:返回 a*b 的系数(长度 a.size()+b.size()-1) vector<ll> multiply(const vector<ll>& a, const vector<ll>& b){ vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end()); int n = 1; while (n < (int)(a.size() + b.size() - 1)) n <<= 1; // 补成 2 的幂 fa.resize(n); fb.resize(n); fft(fa, false); fft(fb, false); // 求值:两个点值序列 for (int i = 0; i < n; i++) fa[i] *= fb[i];// 点值逐点相乘 fft(fa, true); // 插值:逆变换回系数 vector<ll> res(a.size() + b.size() - 1); for (int i = 0; i < (int)res.size(); i++) res[i] = (ll)round(fa[i].real()); // 四舍五入消除浮点误差 return res; }
// 大数乘法:两个十进制字符串相乘(先翻转成低位在前,卷积后统一进位) string bigMul(string s1, string s2){ if (s1 == "0" || s2 == "0") return"0"; vector<ll> a, b; for (int i = (int)s1.size() - 1; i >= 0; i--) a.push_back(s1[i] - '0'); for (int i = (int)s2.size() - 1; i >= 0; i--) b.push_back(s2[i] - '0'); vector<ll> c = multiply(a, b); for (int i = 0; i + 1 < (int)c.size(); i++) { // 从低位向高位进位 c[i + 1] += c[i] / 10; c[i] %= 10; } while (c.size() > 1 && c.back() == 0) c.pop_back(); // 去掉前导 0 string res; for (int i = (int)c.size() - 1; i >= 0; i--) res += char('0' + c[i]); return res; }
ll qpow(ll a, ll b){ ll r = 1; for (; b; b >>= 1, a = a * a % MOD) if (b & 1) r = r * a % MOD; return r; }
voidntt(vector<ll>& a, bool invert){ int n = (int)a.size(); // 蝴蝶变换:位逆序重排(与 FFT 相同) for (int i = 1, j = 0; i < n; i++) { int bit = n >> 1; for (; j & bit; bit >>= 1) j ^= bit; j ^= bit; if (i < j) swap(a[i], a[j]); } for (int len = 2; len <= n; len <<= 1) { ll wlen = qpow(G, (MOD - 1) / len); // len 次单位原根 if (invert) wlen = qpow(wlen, MOD - 2); // 逆变换用原根的逆 for (int i = 0; i < n; i += len) { ll w = 1; for (int j = 0; j < len / 2; j++) { ll u = a[i + j]; ll v = a[i + j + len / 2] * w % MOD; a[i + j] = (u + v) % MOD; a[i + j + len / 2] = (u - v + MOD) % MOD; // 加 MOD 保证非负 w = w * wlen % MOD; } } } if (invert) { ll invN = qpow(n, MOD - 2); for (ll& x : a) x = x * invN % MOD; // 除以 n 的逆元 } }
// 模意义下的多项式乘法 vector<ll> multiply(vector<ll> a, vector<ll> b){ int need = (int)a.size() + (int)b.size() - 1; int n = 1; while (n < need) n <<= 1; a.resize(n); b.resize(n); ntt(a, false); ntt(b, false); for (int i = 0; i < n; i++) a[i] = a[i] * b[i] % MOD; ntt(a, true); a.resize(need); return a; }
注意点 / 坑点:
模数必须满足 MOD = c·2^k + 1 且 2^k ≥ 变换长度 n,否则 (MOD-1)/len 不是整数、原根不存在;998244353 只支持 n ≤ 2²³。
逆变换结束必须乘 n 的模逆元,漏掉会使结果整体放大 n 倍。
(u - v + MOD) % MOD 保证非负;乘法中间量 (a[i+j+len/2] * w) 要用 long long 存,否则 int 溢出。
三模数合并时三个模数的乘积(约 4.7e26)远超 long long,CRT 合并需用 __int128 或「先合并两个、再与第三个合并」的写法。
算法思想:核心是牛顿迭代倍增:已知 B 是 A 的逆模 x^m,则 B’ = B·(2 − A·B) 模 x^{2m} 精度翻倍,每次迭代做常数次 NTT,总复杂度 O(n log n)。其余运算都归约到求逆:ln A = ∫ A’/A;exp A 用 B ← B·(1 − ln B + A) 迭代;开方 B ← (A + B²)/(2B);幂 A^k = exp(k·ln A)。
// ---------- 多项式求逆(倍增 + NTT) ---------- // 已知 A(A[0] != 0),求 B 使 A*B ≡ 1 (mod x^n) vector<ll> polyInv(const vector<ll>& A, int n){ vector<ll> B(1, qpow(A[0], MOD - 2)); // 常数项的逆,作为起点 for (int m = 1; m < n; m <<= 1) { // 当前精度 m,翻倍到 2m int len = m << 1; vector<ll> f(len, 0); // f = A 截断到 len 项 int take = min((int)A.size(), len); copy(A.begin(), A.begin() + take, f.begin()); vector<ll> g(B.begin(), B.end()); // g = 当前的 B,补 0 到 len g.resize(len, 0); ntt(f, false); ntt(g, false); for (int i = 0; i < len; i++) // 牛顿迭代:B <- B*(2 - A*B),在频域点乘 g[i] = g[i] * ((2 - f[i] * g[i] % MOD + MOD) % MOD) % MOD; ntt(g, true); B.assign(g.begin(), g.begin() + len); // 取回前 len 个系数 } B.resize(n); return B; }
// 多项式求导与积分(积分依赖预处理的逆元数组 inv[1..n]) vector<ll> polyDeriv(const vector<ll>& A){ // a_i -> (i+1)*a_{i+1} int n = (int)A.size(); vector<ll> r(max(0, n - 1)); for (int i = 1; i < n; i++) r[i - 1] = A[i] * i % MOD; return r; } vector<ll> polyInteg(const vector<ll>& A, const vector<ll>& inv){ int n = (int)A.size(); vector<ll> r(n + 1); for (int i = 0; i < n; i++) r[i + 1] = A[i] * inv[i + 1] % MOD; return r; }
// ---------- 多项式 ln ---------- 需 A[0] == 1 // ln A = ∫ (A'/A) dx:先求导、求逆,再卷积,最后积分(结果严格截断到 n 项) vector<ll> polyLn(const vector<ll>& A, int n, const vector<ll>& inv){ vector<ll> t = multiply(polyDeriv(A), polyInv(A, n)); t.resize(n); vector<ll> r = polyInteg(t, inv); r.resize(n); // ln A 的常数项为 0,去掉多余的第 n+1 项 return r; }
// ---------- 多项式 exp(简要实现)---------- 需 A[0] == 0 // 牛顿迭代:B <- B*(1 - ln B + A) 模 x^{2m};朴素版每轮重算 ln vector<ll> polyExp(const vector<ll>& A, int n, const vector<ll>& inv){ vector<ll> B(1, 1); // exp(0) = 1 for (int m = 1; m < n; m <<= 1) { int len = m << 1; vector<ll> f = A; f.resize(len); // 截断到 len vector<ll> lnB = polyLn(B, len, inv); for (int i = 0; i < len; i++) f[i] = (f[i] - lnB[i] + MOD) % MOD; // f = A - ln B f[0] = (f[0] + 1) % MOD; // f = 1 - ln B + A B = multiply(B, f); // B <- B * f B.resize(len); } B.resize(n); return B; }
#include<bits/stdc++.h> usingnamespace std; using ll = longlong; const ll MOD = 1e9 + 7;
structMat { // 矩阵结构体 int n, m; // 行数、列数 vector<vector<ll>> a; Mat(int n_ = 0, int m_ = 0) : n(n_), m(m_), a(n_, vector<ll>(m_, 0)) {} static Mat identity(int sz){ // 单位阵 Mat I(sz, sz); for (int i = 0; i < sz; i++) I.a[i][i] = 1; return I; } };
Mat mul(const Mat& A, const Mat& B){ // 矩阵乘法,要求 A.m == B.n Mat C(A.n, B.m); for (int i = 0; i < A.n; i++) for (int k = 0; k < A.m; k++) if (A.a[i][k]) // 跳过 0 项(稀疏加速) for (int j = 0; j < B.m; j++) C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j]) % MOD; return C; }
Mat qpow(Mat base, ll e){ // 矩阵快速幂(e >= 0) Mat res = Mat::identity(base.n); // 结果初始为单位阵 while (e) { if (e & 1) res = mul(res, base); base = mul(base, base); e >>= 1; } return res; }
// 斐波那契第 n 项:F_0=0, F_1=1,转移矩阵 M = [[1,1],[1,0]] // [F_{t+1}, F_t]^T = M * [F_t, F_{t-1}]^T,故 M^n 的 (1,0) 元素即 F_n ll fib(ll n){ if (n == 0) return0; Mat M(2, 2); M.a[0][0] = M.a[0][1] = M.a[1][0] = 1; M.a[1][1] = 0; Mat P = qpow(M, n); // P = M^n,[F_{n+1}, F_n]^T = P * [F_1, F_0]^T = P * [1, 0]^T return P.a[1][0]; // F_n = (M^n)[1][0] }
注意点 / 坑点:
单位阵维度必须等于转移矩阵的阶;快速幂指数 n 与初始向量 v₀ 的对应关系(F₀/F₁ 从哪一项开始)极易写错,建议先手推 n=1、2 验证。
矩阵乘法三层循环用 i–k–j 顺序并跳过 0 元素,可显著加速稀疏转移矩阵;中间量 A.a[i][k]*B.a[k][j] 可能超 int,必须用 long long。
算法思想:Burnside 引理:等价类数 = (1/|G|)·Σ_{g∈G} fix(g),其中 fix(g) 是 g 作用下的不动点个数。Pólya 定理:用 m 种颜色给 n 个位置着色时,fix(g) = m^{c(g)},c(g) 是置换 g 的循环个数(同一循环内颜色必须相同才不动)。项链只考虑旋转群 C_n(|G|=n,旋转 k 步有 gcd(n,k) 个循环);手镯加翻转构成二面体群 D_n(|G|=2n,翻转向量的循环数分奇偶讨论)。
#include<bits/stdc++.h> usingnamespace std; using ll = longlong; const ll MOD = 998244353;
ll qpow(ll a, ll b){ ll r = 1; for (; b; b >>= 1, a = a * a % MOD) if (b & 1) r = r * a % MOD; return r; }
// 欧拉函数:1~n 中与 n 互质的数的个数(试除法分解) ll phi(ll n){ ll res = n; for (ll p = 2; p * p <= n; p++) if (n % p == 0) { res = res / p * (p - 1); while (n % p == 0) n /= p; } if (n > 1) res = res / n * (n - 1); return res; }
// 项链(只考虑旋转):n 颗珠子,m 种颜色 // Burnside:答案 = (1/n) * Σ_{k=0}^{n-1} m^{gcd(n,k)},O(n log MOD) ll necklace(int n, ll m){ ll ans = 0; for (int k = 0; k < n; k++) ans = (ans + qpow(m, gcd(n, k))) % MOD; // 旋转 k 步有 gcd(n,k) 个循环 return ans * qpow(n, MOD - 2) % MOD; // 除以群大小 |G| = n }
// 欧拉函数优化版:按循环数 d = gcd(n,k) 分组,个数为 φ(n/d),O(√n log MOD) ll necklaceFast(int n, ll m){ ll ans = 0; for (int d = 1; d * d <= n; d++) { if (n % d == 0) { // 循环数为 d 的旋转有 φ(n/d) 个;循环数为 n/d 的有 φ(d) 个 ans = (ans + phi(n / d) % MOD * qpow(m, d)) % MOD; if (d != n / d) ans = (ans + phi(d) % MOD * qpow(m, n / d)) % MOD; } } return ans * qpow(n, MOD - 2) % MOD; // |G| = n(仍是旋转群) }
// 手镯(旋转 + 翻转):二面体群 D_n,|G| = 2n ll bracelet(int n, ll m){ ll ans = 0; for (int k = 0; k < n; k++) // n 个旋转 ans = (ans + qpow(m, gcd(n, k))) % MOD; if (n & 1) { // n 为奇数:n 个翻转,各 (n+1)/2 个循环 ans = (ans + n * qpow(m, (n + 1) / 2)) % MOD; } else { // n 为偶数:两类翻转各 n/2 个 ans = (ans + (n / 2) * qpow(m, n / 2 + 1)) % MOD; // 过对珠:2 + (n-2)/2 个循环 ans = (ans + (n / 2) * qpow(m, n / 2)) % MOD; // 过对边:n/2 个循环 } return ans * qpow(2 * n, MOD - 2) % MOD; // 除以 |G| = 2n }
注意点 / 坑点:
旋转 k 步的循环数 = gcd(n,k),从 k=0(恒等置换,n 个循环)开始枚举,别漏掉恒等置换。
算法思想:DFS(深度优先)沿一条分支走到底再回溯,用「标记 → 递归 → 撤销」三步完成状态枚举,vis 数组兼作去重;BFS(广度优先)借助队列按层扩展,第一次到达某状态的步数一定是最短步数(无权图),因此 dist 数组可兼作访问标记。网格题常用 id = x * m + y 把二维坐标压成一维,既省内存又便于开 dist 数组;连通块统计即对每个未访问点做一次遍历并计数。
// ============ 模板三:网格 BFS(二维坐标转一维 + 连通块) ============ constint MAXN = 1005; char mp[MAXN][MAXN]; // 地图,'#' 障碍,'.' 可走 int n, m; inlineintid(int x, int y){ return x * m + y; } // 二维坐标压成一维 constint dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
// 求 (sx,sy) 到 (tx,ty) 最少步数;不可达返回 -1 intbfsGrid(int sx, int sy, int tx, int ty){ vector<int> dist(n * m, -1); queue<int> q; // 一维 dist 省内存 dist[id(sx, sy)] = 0; q.push(id(sx, sy)); while (!q.empty()) { int cur = q.front(); q.pop(); int x = cur / m, y = cur % m; // 一维还原成二维 if (x == tx && y == ty) return dist[cur]; for (int k = 0; k < 4; k++) { int nx = x + dx[k], ny = y + dy[k]; if (nx < 0 || nx >= n || ny < 0 || ny >= m || mp[nx][ny] == '#') continue; // 越界或障碍 int nid = id(nx, ny); if (dist[nid] != -1) continue; // 去重 dist[nid] = dist[cur] + 1; q.push(nid); } } return-1; } // 连通块个数:对每个未访问的 '.' 做一次 BFS 染色,次数即连通块数 intcntComp(){ bool vis[MAXN][MAXN] = {}; int comp = 0; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (mp[i][j] == '.' && !vis[i][j]) { comp++; queue<int> q; q.push(id(i, j)); vis[i][j] = true; while (!q.empty()) { // 四方向扩散染色 int cur = q.front(); q.pop(); int x = cur / m, y = cur % m; for (int k = 0; k < 4; k++) { int nx = x + dx[k], ny = y + dy[k]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (mp[nx][ny] != '.' || vis[nx][ny]) continue; vis[nx][ny] = true; q.push(id(nx, ny)); } } } return comp; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
// ============ 模板四:无权图最短路条数计数 ============ longlong cnt[N]; // cnt[v]:起点到 v 的最短路条数 voidbfsCnt(int s){ memset(dist, -1, sizeof dist); fill(cnt, cnt + N, 0); queue<int> q; dist[s] = 0; cnt[s] = 1; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); for (int v : g[u]) { if (dist[v] == -1) { // 第一次到达:确定最短路 dist[v] = dist[u] + 1; cnt[v] = cnt[u]; q.push(v); } elseif (dist[v] == dist[u] + 1) { cnt[v] += cnt[u]; // 等长最短路,累加条数 } } } }
// ============ 模板二:Meet in the Middle(折半枚举 + 排序二分) ============ // 例题:n 个数中选任意个,使总和 ≤ W,求方案数(n ≤ 40 时 2^40 不可行) #include<bits/stdc++.h> usingnamespace std; using ll = longlong;
int n; ll W, a[45];
// 枚举 a[l..r) 的所有子集和(每数选或不选),结果存入 out voidgen(int l, int r, vector<ll>& out){ int m = r - l; for (int mask = 0; mask < (1 << m); mask++) { // mask 的每个二进制位表示选/不选 ll sum = 0; for (int i = 0; i < m; i++) if (mask >> i & 1) sum += a[l + i]; out.push_back(sum); } }
intmain(){ cin >> n >> W; for (int i = 0; i < n; i++) cin >> a[i];
int mid = n / 2; // 折半点:左右各约 n/2 个数 vector<ll> L, R; gen(0, mid, L); // 左半:2^(n/2) 种和 gen(mid, n, R); // 右半:2^(n-n/2) 种和 sort(R.begin(), R.end()); // 右半排序,供二分查找
ll ans = 0; for (ll x : L) { // 对每个左半和,二分右半能配几个 ll lim = W - x; if (lim < 0) continue; // 左半和已超预算,跳过 ans += upper_bound(R.begin(), R.end(), lim) - R.begin(); // 统计 ≤ lim 的个数 } cout << ans << '\n'; return0; }
int n, len, cnt; // 小木棒数、目标大棒长度、大棒根数 int a[70]; bool used[70];
// 拼第 k 根大棒、已拼 cur、从下标 start 开始试(保证组合不重复) booldfs(int k, int cur, int start){ if (k == cnt) returntrue; // 全部拼完 if (cur == len) returndfs(k + 1, 0, 0); // 当前根拼满,拼下一根 int last = -1; // 记录本层刚失败的长度 for (int i = start; i < n; i++) { if (used[i]) continue; if (cur + a[i] > len) continue; // 可行性剪枝:放不下 if (a[i] == last) continue; // 对称性剪枝:同长度刚失败,跳过 used[i] = true; if (dfs(k, cur + a[i], i + 1)) returntrue; used[i] = false; last = a[i]; // 两个强剪枝:拼「第一段」就失败,或「恰好填满」仍失败, // 说明该长度在任何方案中都不可行,直接返回 if (cur == 0) returnfalse; if (cur + a[i] == len) returnfalse; } returnfalse; }
intmain(){ while (cin >> n && n) { int sum = 0; for (int i = 0; i < n; i++) { cin >> a[i]; sum += a[i]; } sort(a, a + n, greater<int>()); // 排序剪枝:从长到短,尽早失败 for (len = a[0]; len <= sum; len++) { // 大棒长度 ≥ 最长段 if (sum % len) continue; // 总长必须能被 len 整除 cnt = sum / len; memset(used, 0, sizeof used); if (dfs(0, 0, 0)) { cout << len << '\n'; break; } } } return0; }
1 2 3 4 5 6 7 8 9 10 11 12
// ============ 剪枝片段 2:最优性剪枝(当前代价 + 乐观估计 ≥ best 则剪) ============ // 适用:求最小代价类搜索(最小步数、最小花费),先搜出较优解再不断收紧剪枝 int best = INT_MAX; // 全局已知最优解 voiddfs(int step, int cost){ if (cost + optimistic(step) >= best) return; // 乐观估计都追不上 best,必不可能更优 if (step == n) { best = min(best, cost); return; } // 到达叶节点更新答案 for (int x : choices[step]) { if (cost + w[step][x] >= best) continue; // 单步就超,直接跳过 dfs(step + 1, cost + w[step][x]); } } // 注意:optimistic(step) 是"剩余部分代价的下界",必须 ≤ 真实剩余代价
算法思想:用整数的二进制位表示集合(第 k 位表示元素 k 是否在集合中),则并 / 交 / 差 / 对称差分别对应 |、&、~、^;lowbit = x & (-x) 取出最低位的 1;枚举子集用 (sub - 1) & mask 依次剥掉最低位;1 的个数用 __builtin_popcount 直接得到。异或满足自反性 x ^ x = 0,配合前缀异或可 O(1) 求区间异或;a + b = (a ^ b) + 2 * (a & b) 揭示了异或与加法的关系。这些技巧与状压 DP 天然配合:dp[mask] 以集合为状态,转移时枚举元素或子集。
// 按右端点升序排序;能接上(左端点 > 上一个右端点)就选 intmaxDisjoint(vector<Seg>& a){ sort(a.begin(), a.end(), [](const Seg& x, const Seg& y) { return x.r < y.r; // 关键:按右端点排序 }); int cnt = 0, last = -1e9; for (auto& s : a) if (s.l > last) { cnt++; last = s.r; } // 选它,更新覆盖到的右端点 return cnt; }
1 2 3 4 5 6 7 8 9
// ============ 模型 2:区间选点(用最少的点覆盖所有区间) ============ // 与区间调度同构:按右端点排序,未被覆盖的区间在右端点处放一个点 intminPoints(vector<Seg>& a){ sort(a.begin(), a.end(), [](const Seg& x, const Seg& y) { return x.r < y.r; }); int cnt = 0, last = -1e9; for (auto& s : a) if (s.l > last) { cnt++; last = s.r; } // 点放在右端点最优(贪心性) return cnt; }
1 2 3 4 5 6 7 8 9 10 11 12 13
// ============ 模型 3:区间覆盖(用最少的区间覆盖 [L, R]) ============ // 按左端点排序,每次选"能接上且右端点最远"的区间 intminCover(vector<Seg>& a, int L, int R){ sort(a.begin(), a.end(), [](const Seg& x, const Seg& y) { return x.l < y.l; }); int cnt = 0, cur = L, i = 0, n = (int)a.size(); while (cur < R) { int far = cur; // 当前覆盖范围内能到的最远右端点 while (i < n && a[i].l <= cur) far = max(far, a[i++].r); if (far == cur) return-1; // 出现断层:无法继续覆盖 cur = far; cnt++; } return cnt; }
structNode { int a, b, c; // 三维坐标 int cnt; // 完全相同的点合并后的个数 int ans; // 满足偏序关系的点数(不含自身) } p[N]; int n, m, k, bit[N]; // n 原始点数、m 去重后点数、k 为 c 值域;bit 树状数组
voidadd(int i, int v){ for (; i <= k; i += i & -i) bit[i] += v; } intsum(int i){ int s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; }
// CDQ 分治处理区间 [l, r]:统计"左半对右半"的贡献 voidcdq(int l, int r){ if (l == r) return; int mid = (l + r) >> 1; cdq(l, mid); cdq(mid + 1, r); // 先递归,保证两半内部已按 b 有序 // 双指针统计:左半按 b 递增、右半按 b 递增 int i = l; for (int j = mid + 1; j <= r; j++) { while (i <= mid && p[i].b <= p[j].b) { // b 值不超过右半当前点 add(p[i].c, p[i].cnt); // 按 c 维度加入树状数组 i++; } p[j].ans += sum(p[j].c); // 统计 c 值 ≤ 当前点的左点贡献 } for (int t = l; t < i; t++) add(p[t].c, -p[t].cnt); // 回滚本层修改 // 归并排序合并 [l, r](按 b 升序),供上层递归继续使用 inplace_merge(p + l, p + mid + 1, p + r + 1, [](const Node& x, const Node& y) { return x.b < y.b; }); } intmain(){ scanf("%d%d", &n, &k); for (int i = 1; i <= n; i++) scanf("%d%d%d", &p[i].a, &p[i].b, &p[i].c); // 先按 (a, b, c) 字典序排序:左半元素的 a 一定 ≤ 右半元素的 a sort(p + 1, p + n + 1, [](const Node& x, const Node& y) { return x.a != y.a ? x.a < y.a : (x.b != y.b ? x.b < y.b : x.c < y.c); }); // 去重:完全相同的点合并,cnt 记录个数(它们两两互相偏序) m = 0; for (int i = 1; i <= n; i++) { if (m > 0 && p[i].a == p[m].a && p[i].b == p[m].b && p[i].c == p[m].c) p[m].cnt++; else { p[++m] = p[i]; p[m].cnt = 1; } } cdq(1, m); // 与自己相同的 (cnt-1) 个点也满足偏序,补上 for (int i = 1; i <= m; i++) p[i].ans += p[i].cnt - 1; // 统计每个等级的出现次数并输出(等级 0..n-1) staticint res[N]; for (int i = 1; i <= m; i++) res[p[i].ans] += p[i].cnt; for (int i = 0; i < n; i++) printf("%d\n", res[i]); return0; }
// ============ 模板二:整体二分(静态区间第 k 小,P3834 思路) ============ // 适用:多组询问、答案可二分、判定可离线批量处理。 #include<bits/stdc++.h> usingnamespace std; constint N = 200005;
structOp { // 统一事件:修改(数组元素)或查询 int type; // 1 = 修改(位置 x 上的值 y 参与计数);2 = 查询 int x, y; // 修改: x=位置, y=值;查询: x=l, y=r int k, id; // 查询专用:第 k 小、询问编号 } op[N]; int n, m, ans[N], bit[N];
voidadd(int i, int v){ for (; i <= n; i += i & -i) bit[i] += v; } intsum(int i){ int s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; }
// 答案值域 [l, r],事件区间 [ql, qr) voidsolve(int l, int r, int ql, int qr){ if (ql >= qr) return; if (l == r) { // 值域缩成一点:答案确定 for (int i = ql; i < qr; i++) if (op[i].type == 2) ans[op[i].id] = l; return; } int mid = (l + r) >> 1, L = ql, R = qr, i = ql; // 划分:左半 [ql, L)、右半 [R, qr) while (i < R) { if (op[i].type == 1) { if (op[i].y <= mid) { // 值在左半:加入树状数组并放左边 add(op[i].x, 1); swap(op[i], op[L++]); i++; } else { // 值在右半:放右边,继续处理换来的元素 swap(op[i], op[--R]); } } else { int cnt = sum(op[i].y) - sum(op[i].x - 1); // 区间内值 ≤ mid 的个数 if (cnt >= op[i].k) { // 第 k 小落在左半 swap(op[i], op[L++]); i++; } else { // 落在右半:k 减去左半贡献 op[i].k -= cnt; swap(op[i], op[--R]); } } } for (int t = ql; t < L; t++) if (op[t].type == 1) add(op[t].x, -1); // 回滚 solve(l, mid, ql, L); solve(mid + 1, r, R, qr); } intmain(){ scanf("%d%d", &n, &m); int tot = 0, mn = INT_MAX, mx = 0; for (int i = 1; i <= n; i++) { int v; scanf("%d", &v); op[tot++] = {1, i, v, 0, 0}; // 元素视为"修改"事件 mn = min(mn, v); mx = max(mx, v); } for (int i = 0; i < m; i++) { int l, r, k; scanf("%d%d%d", &l, &r, &k); op[tot++] = {2, l, r, k, i}; // 询问事件 } solve(mn, mx, 0, tot); // 值域从最小值到最大值 for (int i = 0; i < m; i++) printf("%d\n", ans[i]); return0; }
// 快读:比 cin 快数倍,数据量达 1e6 级别时必备 template <typename T> voidread(T& x){ x = 0; int f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = getchar(); } x *= f; } // 用法:read(n); read(a[i]); // 简单场景也可直接关同步: // ios::sync_with_stdio(false); // cin.tie(nullptr); // 注意:cin 与 scanf/printf 混用会乱序,全程只用一种
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
@echo off REM ============ 对拍脚本(Windows 批处理) ============ REM 目录下准备三个程序:gen.exe(数据生成器)、std.exe(标准/暴力)、my.exe(待测) for /l %%iin (1,1,1000) do ( gen.exe > in.txt std.exe < in.txt > ans.txt my.exe < in.txt > out.txt fc /b ans.txt out.txt >nul iferrorlevel1 ( echo WA at test %%i copyin.txt wa_in_%%i.txt >nul goto :end ) else ( echo OK test %%i ) ) :end REM 提示:输出行末多余空格/换行会造成误报,必要时先 strip 再比较
斯特林数:第二类 S(n,k) = S(n-1,k-1) + k·S(n-1,k),表示把 n 个不同元素分成 k 个非空子集的方案数(边界 S(n,0)=[n=0],S(n,1)=S(n,n)=1);第一类 s(n,k) = s(n-1,k-1) + (n-1)·s(n-1,k),表示 n 个元素排列成 k 个循环置换的方案数。
模运算性质(m 为模数):
分配律:(a+b) mod m = ((a mod m)+(b mod m)) mod m,乘法同理;减法注意 C++ 负数取模:(a%m - b%m + m) % m。
除法需要逆元:a/b mod m = a·b⁻¹ mod m;b⁻¹ 存在当且仅当 gcd(b, m) = 1。m 为素数时由费马小定理 b⁻¹ = b^(m-2)(快速幂);一般情形用扩展欧几里得解 b·x ≡ 1 (mod m)。
幂运算:a^b mod m 用快速幂 O(logb);指数 b 极大时(a、m 互质)可先对指数取模 φ(m)。
#include<bits/stdc++.h> usingnamespace std; using ll = longlong; const ll MOD = 1e9 + 7;
ll qpow(ll a, ll b, ll mod = MOD){ // 快速幂:a^b % mod,O(logb) ll r = 1 % mod; a %= mod; for (; b; b >>= 1) { if (b & 1) r = r * a % mod; a = a * a % mod; } return r; }
ll inv(ll x){ returnqpow(x, MOD - 2); } // 费马小定理求逆元(要求 MOD 为素数)
intmain(){ int n = 5; // 例:算 C(10,3) 与卡特兰数 C5 int MAX = 2 * n; vector<ll> fac(MAX + 1), ifac(MAX + 1); fac[0] = 1; for (int i = 1; i <= MAX; ++i) fac[i] = fac[i - 1] * i % MOD; ifac[MAX] = inv(fac[MAX]); for (int i = MAX; i >= 1; --i) ifac[i - 1] = ifac[i] * i % MOD;
// 组合数函数:C(n,k) = n! / (k! (n-k)!),阶乘预处理后 O(1) 查询 auto C = [&](int nn, int kk) -> ll { if (kk < 0 || kk > nn) return0; return fac[nn] * ifac[kk] % MOD * ifac[nn - kk] % MOD; };
intmain(){ auto st = chrono::steady_clock::now(); longlong s = 0; for (int i = 0; i < 1e8; ++i) s += i; // 1e8 次加法实测约 0.1~0.3s(O2) auto ed = chrono::steady_clock::now(); double ms = chrono::duration<double, milli>(ed - st).count(); printf("time: %.2f ms, s=%lld\n", ms, s); return0; }