抽象代数的竞赛用法
先把题目中的对象和操作说清楚:对象是余数、排列、向量还是多项式?操作能否结合、交换、撤销?随后才能判断应该用群、环、域中的哪条性质。下列竞赛模型由这些定义推导,例子均为独立构造;完整定义与证明见本章后续八节。
| 题面信号 | 先问什么 | 可落地的方法 |
|---|---|---|
| 环上重复跳跃、模意义下加减 | 所有操作生成了哪些余数? | GCD、线性同余、循环群的阶 |
| 同一洗牌执行巨大次数 | 每个位置属于哪个循环? | 循环分解,每环对长度取模 |
| 换位、三轮换、能否复原 | 操作改变奇偶性吗? | 符号同态、置换不变量 |
| 许多输入得到同一个输出 | 映射是否保持运算? | 核、陪集、像,计算纤维大小 |
| 把大量状态归为同一类 | 换代表元后,所有后继仍等价吗? | 良定性、商结构,证明状态压缩 |
| 模除法、模高斯消元 | 被除数所在结构中是否有逆元? | 单位群;素数域与合数环分开 |
| 旋转或翻转视为相同 | 各对象的等价类大小相同吗? | 群作用、Burnside,数不动点 |
| NTT、异或系数、多项式取模 | 系数在哪个域?根的阶和模多项式是什么? | 单位根、有限域、商环 |
1. 模环上的移动:可达性先算生成子群
识别。 状态为 ,可反复加减固定步长 ,问能否从 到达 、有多少可达状态,或多久回到起点。
转化。 令 。所有可达增量组成 的子群,恰为 的倍数;因此
单一步长 的最小正周期是 。证明分两边:每个操作保留模 的余数;Bezout 恒等式给出 的整数线性组合,从而所有 的倍数都能生成。若只有“加”、无次数上限,在有限模环上同样能通过重复加法模拟逆操作。
应用。 先约去 GCD 判断可解,再用扩展欧几里得求某个操作次数;若问最短步数,还需考虑允许的操作及边权,不能仅凭可达性得到距离。
例。 在 12 个位置的环上每次加 8,从 0 出发依次为 :只到达 3 个位置。再允许加 6,则 ,可到达全部偶数位置。若每种操作次数有上限,以上充分性不再自动成立。
这是循环群及其子群在加法模环上的应用。基础见 MIT 18.703:循环群;对应笔记 02-循环群与生成元。
2. 巨大次数置换:逐环取模,通常不用算全局 LCM
识别。 洗牌、重排、轮换的规则固定,每个位置恰有一个前驱和后继,执行 次, 可能是十进制大整数。
应用。 把 分解成不相交循环 ,满足 。则
遍历所有位置 ;每个不同环长需要 ,大整数可逐位维护余数。只有题目真的问“整体最早复原次数”时,才计算各环长 LCM;LCM 本身可能超过 64 位。
例。 ,阶为 6。执行 2026 次后,三环移 1 格,二环不动,所以 、。
方向检查。 若规则是“原位置 的物品移到 ”,则写 new[p[i]]=old[i];若定义是 new[i]=old[p[i]],移动方向相反。先用一个三环验方向。一般函数图可能带入树,必须先处理进环前的路径,不能把任意映射都当置换。
不相交循环分解与阶公式见 MIT 18.703:置换群;证明见 06-置换群-内自同构-Cayley。
3. 置换奇偶性:先证明不可能,再讨论怎么构造
识别。 操作是交换、三轮换,题目要求复原、限制操作次数奇偶,或问状态之间能否互达。
转化。 置换符号是到 的同态。一次任意对换改变符号;三轮换是两个对换的乘积,保留符号。若分解后有 个循环(含不动点),则符号为 。任意两位置可交换时,最少交换次数为 :一次交换至多增加一个循环,而一个长 的循环可用 次交换拆开。
例。 有 ,是奇置换,不能仅靠三轮换复原。若操作允许任意三个不同位置的三轮换,则偶置换可以复原;若只允许某些局部三轮换,还要证明这些操作能生成全部目标状态。
使用边界。 有重复值时,交换两个相等值可以改变“带标签置换”的奇偶性却不改变可见序列,因此不能直接把互异排列的必要条件搬到重复值排序。滑块拼图也必须把空格位置的变化一起纳入不变量。
证明见 06-置换群-内自同构-Cayley。这一节给出的是从符号同态推导的竞赛判据。
4. 同态、核与像:一份解加上所有零解
识别。 问某种线性/同余变换能产生哪些输出,某个输出有几个原像,或者多个方程解集为什么大小相同。
转化。 若 是有限群同态,,则所有映到 的元素恰为陪集 。所以每个可达输出有 个原像,而且 。要先检查映射保持运算;任意非线性函数没有这一保证。核与像的基础见 MIT 18.703:同态与核。
例一。 ,。核是 ,像是 。因此 有 4 个解,分别为 ,而右端为 2 时无解。
例二。 上 ,有 个变量、秩为 。若无矛盾行,零空间有 个自由变量,解数为 ;否则为 0。例如 ,,解为 和 ,恰为一份解加零空间。
应用。 同余用扩欧先查 GCD;二进制线性方程用 XOR 高斯消元或带方程信息的线性基。不要把“能表示的不同异或值个数 ”与“每个异或值对应多少下标子集 ”混为一谈。进一步理论见 05-三大同构定理。
5. 商结构与 DP 压缩:同类状态的下一步也必须同类
识别。 想只存余数、排序后的集合、某个哈希值或当前答案,忽略原状态的其他信息。
应用步骤。 明确等价关系 ;对每个合法操作 检查:操作是否合法、代价和可观察收益是否一致,而且 是否推出 。若选择依赖状态,必须能逐项对应可选操作。这样才可以在等价类上定义转移;计数问题还要保留每类的权重或转移重数。
例。 存 能支持任意整数加法、乘法,因为换代表元不会改变结果的余数;却不能支持 :,但结果为 0、1,已经不同余。
如何判断状态不足。 主动找两个被合并的历史,并让它们面对同一个后续操作;若合法性或最优剩余值不同,就必须加信息。哈希碰撞控制的是表示错误概率,不能代替这个充分性证明。商集上的良定性见 00-集合论与映射;群商还要求正规性,见 04-商群与同态。
6. 群、环、域:为什么有的模数可以除,有的不行
识别。 公式里出现除法、约分、高斯消元的主元,或要把巨大指数按周期缩小。
判断。 在加法下是群;在乘法下只有与 互质的元素有逆元,它们组成单位群。 为素数时,全部非零元素可逆,才可把通常的域上线性代数直接用于模运算。MIT 循环群讲义证明了单位群与 Euler 定理;MIT 环讲义给出了模环中的零因子。
例。 模 12 下 ,但 6 无逆元;,不能约去 6 得到 。因此复合模高斯消元不能把任意非零主元拿来求逆。
应用。 使用 cp::inv_mod(a,m) 并处理无逆元;素数模快速幂逆元要求 。对互质底数,指数可模元素的阶或 ;不互质时不能直接套 Euler 缩指数。比如 ,把指数模 后变成 。
7. 群作用与去重:不能看到旋转就除以 n
识别。 染色、项链、棋盘等对象在旋转/翻转下视为相同。先列清允许的变换:只旋转通常是循环群,旋转和翻转是二面体群。
转化与证明。 对有限群 的作用,每个对象的轨道大小为 ;具有对称性的对象会有较小轨道,所以等价类并不统一有 个元素。轨道与稳定子的基础见 MIT 18.703:群作用。
对固定对 (满足 )双计数:一个轨道里所有点的稳定子大小之和恰为 ,故
应用。 先把每个变换看成位置置换。不受其他条件限制的 色染色要被该变换固定,同一个位置循环必须同色,因而有 种。圆环旋转 格时有 个位置循环。
例。 长为 4 的二色圆环,仅视旋转相同:四种旋转的不动点数为 ,答案 ,直接 会漏算。
边界。 限制某种颜色数量、相邻颜色或图结构时,固定染色数需在循环压缩后的约束上重新计算,不能一律用 。取模时只有 与模数互质才可乘逆元;否则在能保留整除信息的模数或整数范围下先求和再除。
8. NTT:单位根的阶决定能处理的长度
识别。 两组数按“下标和”组合,需要求 ;把它看成多项式乘法。
转化。 在素数域 中选阶恰为 的元素 。本册的二进制 NTT 要求 是 2 的幂且 ;若 为原根,可取 。逆变换还要除以 。ACL 的卷积接口明确给出了素数模与可用二次幂长度条件。ACL convolution 官方文档
应用。 先取 的最小 2 次幂,检查根是否存在,再补零。模数 支持最长 ;调用本册 cp::convolution。任意改模数,原根和最大长度都要一起重推。
例。 ,需补到长度 4。模 7 的乘法群阶为 6,没有阶为 4 的元素,不能照搬长度 4 的常规 NTT。若不补零,算的是模 的循环卷积,会让高次项绕回低位。
9. 有限域不等于“整数模一个同样大的数”
识别。 题目使用二进制多项式、CRC、扩域,或声称有 个域元素。
转化。 在 不可约时是域;若 ,每个元素可用次数小于 的余式表示,共 个。原因是任意非零余式 与 互质,扩展 Euclid 给出 ,从而 是其逆元。二、三次多项式可通过检查基域上有无根判断不可约,高次不能只检查根。MIT 18.703:多项式环
例。 在 上, 在 0、1 都不为 0,故不可约。记 ,则 ,。四个元素为 ;加法按位 XOR,乘法先做无进位多项式乘法,再模 。
边界。 中 ,因此不是这个四元域。若模 ,非零 的平方为 0,商环也不是域。CRC 的模多项式按检测需求选取,不保证不可约;不要因此假设所有非零余数都有逆元。
阅读顺序
竞赛应用先读本节和数学套路中的对应条目;需要证明时按“集合与映射 → 群与子群 → 循环群 / 陪集 → 商群与同态 → 同构定理 → 置换群”阅读。章节末的抽象代数易错点整理的是概念与证明;个人竞赛复盘单独放在全书最后。
10. 可直接复制的代数代码
完整 GNU C++17 头文件,不依赖 cp_ready.hpp 或第三方库;命名空间为 cp_algebra。提交单文件时将头文件放在 main 前,并删除示例中的本地 include。
| 接口 | 输入与返回 | 前提与代价 |
|---|---|---|
| solve_binary(n, rows) | 每行是 (系数位掩码,右端0/1);返回是否有解、秩、特解、零空间基 |
0≤n≤63,位j对应变量j;O(mn+n²)时间,O(m+n)空间 |
| determinant_prime(a,p) | 方阵的行列式模p;空方阵返回1 | p为素数;O(n³+n log p)时间、O(n²)空间 |
| spanning_trees_prime(n,edges,p) | 无向图生成树边权乘积之和,模p | n≥1,顶点0-based,p素数;平行边累加,自环忽略,单点返回1;O(n³+n log p+m)时间 |
| lagrange_consecutive(y,t,p) | y[i]=F(i),返回F(t)模p | 已证明次数≤d,d=y.size()-1<p,p素数;O(d+log p)时间、O(d)空间 |
| permutation_power(p,K) | 返回每个原位置执行K次后的目的地 | p为0-based双射,K为64位非负整数;O(n)时间/空间 |
| power_sum(A,n,M) | 返回 (A^n, Σ A^i),求和i=0..n-1 |
M≥2可为合数,n为64位非负整数;O(log n)时间、O(1)空间 |
解读二进制方程返回值。 若无解,不读取特解与零空间基;若有解,全部解为 particular 异或任意一个零空间基子集,解数为 2^(n-rank)。题目若要求非空选择且目标为0,需要扣掉空选择。枚举所有解的成本本身是指数级,不要把基向量个数当解数。
检查运算结构。 prime 接口将“p是素数”作为调用前提,不进行素性检测。合数模矩阵不能直接套用。生成树权值在这里是每棵树内相乘,不是树边权相加;无解图返回0,权值在模意义下抵消也可能得到0,不能据此反推原图不连通。
#pragma once#include <bits/stdc++.h>
namespace cp_algebra {using i64 = long long;using i128 = __int128_t;using u64 = std::uint64_t;
inline i64 norm(i64 x, i64 mod) { assert(mod >= 2); x %= mod; return x < 0 ? x + mod : x;}inline i64 power(i64 a, u64 e, i64 mod) { a = norm(a, mod); i64 r = 1; for (; e; e >>= 1, a = (i128)a * a % mod) if (e & 1) r = (i128)r * a % mod; return r;}
// Each row is (coefficient mask, RHS). Variable j is bit j, 0 <= n <= 63.// With a solution: x = particular XOR any subset of nullspace vectors.struct BinarySolution { bool consistent; int rank; u64 particular; std::vector<u64> nullspace;};inline BinarySolution solve_binary(int n, std::vector<std::pair<u64, bool>> rows) { assert(0 <= n && n <= 63); for (auto [a, b] : rows) { (void)b; assert((a >> n) == 0); } int m = (int)rows.size(), r = 0; std::vector<int> pivot; for (int col = 0; col < n && r < m; ++col) { int at = r; while (at < m && !(rows[at].first >> col & 1)) ++at; if (at == m) continue; std::swap(rows[r], rows[at]); for (int i = 0; i < m; ++i) if (i != r && (rows[i].first >> col & 1)) { rows[i].first ^= rows[r].first; rows[i].second = rows[i].second != rows[r].second; } pivot.push_back(col); ++r; } for (auto [a, b] : rows) if (a == 0 && b) return {false, r, 0, {}}; BinarySolution ans{true, r, 0, {}}; std::vector<bool> is_pivot(n, false); for (int i = 0; i < r; ++i) { is_pivot[pivot[i]] = true; if (rows[i].second) ans.particular |= u64(1) << pivot[i]; } for (int f = 0; f < n; ++f) if (!is_pivot[f]) { u64 v = u64(1) << f; for (int i = 0; i < r; ++i) if (rows[i].first >> f & 1) v |= u64(1) << pivot[i]; ans.nullspace.push_back(v); } return ans;}
// Prime mod is a caller precondition. Empty determinant is 1.// O(n^3 + n log mod) time and O(n^2) copied storage; no primality test.inline i64 determinant_prime(std::vector<std::vector<i64>> a, i64 mod) { assert(mod >= 2); int n = (int)a.size(); for (auto &row : a) { assert((int)row.size() == n); for (auto &x : row) x = norm(x, mod); } i64 answer = 1; for (int col = 0; col < n; ++col) { int at = col; while (at < n && a[at][col] == 0) ++at; if (at == n) return 0; if (at != col) { std::swap(a[at], a[col]); answer = norm(-answer, mod); } i64 p = a[col][col], inv = power(p, (u64)(mod - 2), mod); answer = (i128)answer * p % mod; for (int i = col + 1; i < n; ++i) { i64 factor = (i128)a[i][col] * inv % mod; for (int j = col; j < n; ++j) { i64 sub = (i128)factor * a[col][j] % mod; a[i][j] = a[i][j] >= sub ? a[i][j] - sub : mod - (sub - a[i][j]); } } } return answer;}
struct Edge { int u, v; i64 weight = 1; };// Undirected weighted Matrix-Tree: sum of products of edge weights, modulo prime.// Vertices 0..n-1, n >= 1. Parallel edges add; self-loops have no effect.inline i64 spanning_trees_prime(int n, const std::vector<Edge> &edges, i64 mod) { assert(n >= 1 && mod >= 2); std::vector<std::vector<i64>> a(n - 1, std::vector<i64>(n - 1)); auto add = [&](int u, int v, i64 w) { if (u < n - 1 && v < n - 1) a[u][v] = ((i128)a[u][v] + w) % mod; }; for (auto [u, v, weight] : edges) { assert(0 <= u && u < n && 0 <= v && v < n); if (u == v) continue; i64 w = norm(weight, mod), neg = w ? mod - w : 0; add(u, u, w); add(v, v, w); add(u, v, neg); add(v, u, neg); } return determinant_prime(std::move(a), mod);}
// Values y[i] = F(i), i=0..d, of a polynomial of degree <= d over F_mod.// Caller guarantees prime mod and d < mod. O(d + log mod) time, O(d) storage.inline i64 lagrange_consecutive(const std::vector<i64> &y, i64 t, i64 mod) { assert(mod >= 2 && !y.empty()); int d = (int)y.size() - 1; assert(d < mod); t = norm(t, mod); if (t <= d) return norm(y[(int)t], mod); std::vector<i64> pre(d + 2, 1), suf(d + 2, 1), invfact(d + 1, 1); i64 fact = 1; for (int i = 1; i <= d; ++i) fact = (i128)fact * i % mod; invfact[d] = power(fact, (u64)(mod - 2), mod); for (int i = d; i > 0; --i) invfact[i - 1] = (i128)invfact[i] * i % mod; for (int i = 0; i <= d; ++i) pre[i + 1] = (i128)pre[i] * norm(t - i, mod) % mod; for (int i = d; i >= 0; --i) suf[i] = (i128)suf[i + 1] * norm(t - i, mod) % mod; i64 answer = 0; for (int i = 0; i <= d; ++i) { i64 term = (i128)norm(y[i], mod) * pre[i] % mod * suf[i + 1] % mod; term = (i128)term * invfact[i] % mod * invfact[d - i] % mod; if ((d - i) & 1) term = term ? mod - term : 0; answer = ((i128)answer + term) % mod; } return answer;}
// Valid permutation p[i] = destination of original position i; exponent K >= 0.// Returns p^K(i) for every i; O(n). Apply values as new[result[i]] = old[i].inline std::vector<int> permutation_power(const std::vector<int> &p, u64 k) { int n = (int)p.size(); std::vector<int> indeg(n), answer(n); for (int v : p) { assert(0 <= v && v < n); ++indeg[v]; } for (int count : indeg) { (void)count; assert(count == 1); } std::vector<bool> seen(n, false); for (int i = 0; i < n; ++i) if (!seen[i]) { std::vector<int> cycle; for (int v = i; !seen[v]; v = p[v]) { seen[v] = true; cycle.push_back(v); } std::size_t shift = k % cycle.size(); for (std::size_t j = 0; j < cycle.size(); ++j) answer[cycle[j]] = cycle[(j + shift) % cycle.size()]; } return answer;}
// Returns (A^n, 1+A+...+A^(n-1)) mod M, for any M >= 2 (including composite).// Binary composition of consecutive blocks; O(log n), no modular division.inline std::pair<i64, i64> power_sum(i64 a, u64 n, i64 mod) { i64 result_p = 1, result_s = 0, block_p = norm(a, mod), block_s = 1; while (n) { if (n & 1) { result_s = ((i128)result_s + (i128)result_p * block_s) % mod; result_p = (i128)result_p * block_p % mod; } block_s = ((i128)block_s + (i128)block_p * block_s) % mod; block_p = (i128)block_p * block_p % mod; n >>= 1; } return {result_p, result_s};}} // namespace cp_algebra11. 完整调用示例
下面的输出依次是:方程有解/秩/自由变量数,三角形生成树数,平方和插值值,置换2026次后的目的地,等比和。
#include "cp_algebra.hpp"using namespace std;using namespace cp_algebra;int main() { auto s = solve_binary(3, {{0b011, true}, {0b110, false}}); cout << s.consistent << ' ' << s.rank << ' ' << s.nullspace.size() << '\n'; cout << spanning_trees_prime(3, {{0,1,1}, {1,2,1}, {2,0,1}}, 1000000007) << '\n'; cout << lagrange_consecutive({0,1,5,14}, 4, 1000000007) << '\n'; auto p = permutation_power({1,2,0,4,3}, 2026); for (int v : p) cout << v + 1 << ' '; cout << '\n' << power_sum(3, 4, 7).second << '\n';}预期输出:
1 2 13302 3 1 4 55分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ,距今已过 22 天
部分内容可能已过时