4809 字
24 分钟
抽象代数的竞赛用法

抽象代数的竞赛用法#

先把题目中的对象和操作说清楚:对象是余数、排列、向量还是多项式?操作能否结合、交换、撤销?随后才能判断应该用群、环、域中的哪条性质。下列竞赛模型由这些定义推导,例子均为独立构造;完整定义与证明见本章后续八节。

题面信号 先问什么 可落地的方法
环上重复跳跃、模意义下加减 所有操作生成了哪些余数? GCD、线性同余、循环群的阶
同一洗牌执行巨大次数 每个位置属于哪个循环? 循环分解,每环对长度取模
换位、三轮换、能否复原 操作改变奇偶性吗? 符号同态、置换不变量
许多输入得到同一个输出 映射是否保持运算? 核、陪集、像,计算纤维大小
把大量状态归为同一类 换代表元后,所有后继仍等价吗? 良定性、商结构,证明状态压缩
模除法、模高斯消元 被除数所在结构中是否有逆元? 单位群;素数域与合数环分开
旋转或翻转视为相同 各对象的等价类大小相同吗? 群作用、Burnside,数不动点
NTT、异或系数、多项式取模 系数在哪个域?根的阶和模多项式是什么? 单位根、有限域、商环

1. 模环上的移动:可达性先算生成子群#

识别。 状态为 x mod mx\bmod m,可反复加减固定步长 a1,…,aka_1,\ldots,a_k,问能否从 ss 到达 tt、有多少可达状态,或多久回到起点。

转化。 令 g=gcd⁡(m,a1,…,ak)g=\gcd(m,a_1,\ldots,a_k)。所有可达增量组成 Zm\mathbb Z_m 的子群,恰为 gg 的倍数;因此

t 可达  ⟺  g∣(t−s),#可达状态=m/g.t\text{ 可达}\iff g\mid(t-s),\qquad \#\text{可达状态}=m/g.

单一步长 aa 的最小正周期是 m/gcd⁡(m,a)m/\gcd(m,a)。证明分两边:每个操作保留模 gg 的余数;Bezout 恒等式给出 gg 的整数线性组合,从而所有 gg 的倍数都能生成。若只有“加”、无次数上限,在有限模环上同样能通过重复加法模拟逆操作。

应用。 先约去 GCD 判断可解,再用扩展欧几里得求某个操作次数;若问最短步数,还需考虑允许的操作及边权,不能仅凭可达性得到距离。

例。 在 12 个位置的环上每次加 8,从 0 出发依次为 0,8,4,00,8,4,0:只到达 3 个位置。再允许加 6,则 g=2g=2,可到达全部偶数位置。若每种操作次数有上限,以上充分性不再自动成立。

这是循环群及其子群在加法模环上的应用。基础见 MIT 18.703:循环群;对应笔记 02-循环群与生成元。

2. 巨大次数置换:逐环取模,通常不用算全局 LCM#

识别。 洗牌、重排、轮换的规则固定,每个位置恰有一个前驱和后继,执行 KK 次,KK 可能是十进制大整数。

应用。 把 pp 分解成不相交循环 c0,c1,…,cℓ−1c_0,c_1,\ldots,c_{\ell-1},满足 p(ci)=c(i+1) mod ℓp(c_i)=c_{(i+1)\bmod\ell}。则

pK(ci)=c(i+K) mod ℓ.p^K(c_i)=c_{(i+K)\bmod\ell}.

遍历所有位置 O(n)O(n);每个不同环长需要 K mod ℓK\bmod\ell,大整数可逐位维护余数。只有题目真的问“整体最早复原次数”时,才计算各环长 LCM;LCM 本身可能超过 64 位。

例。 p=(1 2 3)(4 5)p=(1\ 2\ 3)(4\ 5),阶为 6。执行 2026 次后,三环移 1 格,二环不动,所以 1↦21\mapsto2、4↦44\mapsto4。

方向检查。 若规则是“原位置 ii 的物品移到 p(i)p(i)”,则写 new[p[i]]=old[i];若定义是 new[i]=old[p[i]],移动方向相反。先用一个三环验方向。一般函数图可能带入树,必须先处理进环前的路径,不能把任意映射都当置换。

不相交循环分解与阶公式见 MIT 18.703:置换群;证明见 06-置换群-内自同构-Cayley。

3. 置换奇偶性:先证明不可能,再讨论怎么构造#

识别。 操作是交换、三轮换,题目要求复原、限制操作次数奇偶,或问状态之间能否互达。

转化。 置换符号是到 {+1,−1}\{+1,-1\} 的同态。一次任意对换改变符号;三轮换是两个对换的乘积,保留符号。若分解后有 cc 个循环(含不动点),则符号为 (−1)n−c(-1)^{n-c}。任意两位置可交换时,最少交换次数为 n−cn-c:一次交换至多增加一个循环,而一个长 ℓ\ell 的循环可用 ℓ−1\ell-1 次交换拆开。

例。 p=(1 2 3)(4 5)p=(1\ 2\ 3)(4\ 5) 有 n−c=5−2=3n-c=5-2=3,是奇置换,不能仅靠三轮换复原。若操作允许任意三个不同位置的三轮换,则偶置换可以复原;若只允许某些局部三轮换,还要证明这些操作能生成全部目标状态。

使用边界。 有重复值时,交换两个相等值可以改变“带标签置换”的奇偶性却不改变可见序列,因此不能直接把互异排列的必要条件搬到重复值排序。滑块拼图也必须把空格位置的变化一起纳入不变量。

证明见 06-置换群-内自同构-Cayley。这一节给出的是从符号同态推导的竞赛判据。

4. 同态、核与像:一份解加上所有零解#

识别。 问某种线性/同余变换能产生哪些输出,某个输出有几个原像,或者多个方程解集为什么大小相同。

转化。 若 f:G→Hf:G\to H 是有限群同态,f(x0)=yf(x_0)=y,则所有映到 yy 的元素恰为陪集 x0ker⁡fx_0\ker f。所以每个可达输出有 ∣ker⁡f∣|\ker f| 个原像,而且 ∣G∣=∣ker⁡f∣ ∣Im⁡f∣|G|=|\ker f|\,|\operatorname{Im}f|。要先检查映射保持运算;任意非线性函数没有这一保证。核与像的基础见 MIT 18.703:同态与核。

例一。 f:Z12→Z12f:\mathbb Z_{12}\to\mathbb Z_{12},f(x)=8xf(x)=8x。核是 {0,3,6,9}\{0,3,6,9\},像是 {0,4,8}\{0,4,8\}。因此 8x≡4(mod12)8x\equiv4\pmod{12} 有 4 个解,分别为 2,5,8,112,5,8,11,而右端为 2 时无解。

例二。 F2\mathbb F_2 上 Ax=bAx=b,有 nn 个变量、秩为 rr。若无矛盾行,零空间有 n−rn-r 个自由变量,解数为 2n−r2^{n-r};否则为 0。例如 x1⊕x2=1x_1\oplus x_2=1,x2⊕x3=0x_2\oplus x_3=0,解为 (1,0,0)(1,0,0) 和 (0,1,1)(0,1,1),恰为一份解加零空间。

应用。 同余用扩欧先查 GCD;二进制线性方程用 XOR 高斯消元或带方程信息的线性基。不要把“能表示的不同异或值个数 2r2^r”与“每个异或值对应多少下标子集 2n−r2^{n-r}”混为一谈。进一步理论见 05-三大同构定理。

5. 商结构与 DP 压缩:同类状态的下一步也必须同类#

识别。 想只存余数、排序后的集合、某个哈希值或当前答案,忽略原状态的其他信息。

应用步骤。 明确等价关系 x∼yx\sim y;对每个合法操作 TT 检查:操作是否合法、代价和可观察收益是否一致,而且 x∼yx\sim y 是否推出 T(x)∼T(y)T(x)\sim T(y)。若选择依赖状态,必须能逐项对应可选操作。这样才可以在等价类上定义转移;计数问题还要保留每类的权重或转移重数。

例。 存 x mod 3x\bmod3 能支持任意整数加法、乘法,因为换代表元不会改变结果的余数;却不能支持 T(x)=⌊x/2⌋T(x)=\lfloor x/2\rfloor:0≡3(mod3)0\equiv3\pmod3,但结果为 0、1,已经不同余。

如何判断状态不足。 主动找两个被合并的历史,并让它们面对同一个后续操作;若合法性或最优剩余值不同,就必须加信息。哈希碰撞控制的是表示错误概率,不能代替这个充分性证明。商集上的良定性见 00-集合论与映射;群商还要求正规性,见 04-商群与同态。

6. 群、环、域:为什么有的模数可以除,有的不行#

识别。 公式里出现除法、约分、高斯消元的主元,或要把巨大指数按周期缩小。

判断。 Zm\mathbb Z_m 在加法下是群;在乘法下只有与 mm 互质的元素有逆元,它们组成单位群。m=pm=p 为素数时,全部非零元素可逆,才可把通常的域上线性代数直接用于模运算。MIT 循环群讲义证明了单位群与 Euler 定理;MIT 环讲义给出了模环中的零因子。

例。 模 12 下 5−1=55^{-1}=5,但 6 无逆元;6⋅2≡6⋅4≡06\cdot2\equiv6\cdot4\equiv0,不能约去 6 得到 2≡42\equiv4。因此复合模高斯消元不能把任意非零主元拿来求逆。

应用。 使用 cp::inv_mod(a,m) 并处理无逆元;素数模快速幂逆元要求 a≢0a\not\equiv0。对互质底数,指数可模元素的阶或 φ(m)\varphi(m);不互质时不能直接套 Euler 缩指数。比如 24 mod 8=02^4\bmod8=0,把指数模 φ(8)=4\varphi(8)=4 后变成 20 mod 8=12^0\bmod8=1。

7. 群作用与去重:不能看到旋转就除以 n#

识别。 染色、项链、棋盘等对象在旋转/翻转下视为相同。先列清允许的变换:只旋转通常是循环群,旋转和翻转是二面体群。

转化与证明。 对有限群 GG 的作用,每个对象的轨道大小为 ∣G∣/∣Stab⁡(x)∣|G|/|\operatorname{Stab}(x)|;具有对称性的对象会有较小轨道,所以等价类并不统一有 ∣G∣|G| 个元素。轨道与稳定子的基础见 MIT 18.703:群作用。

对固定对 (g,x)(g,x)(满足 g⋅x=xg\cdot x=x)双计数:一个轨道里所有点的稳定子大小之和恰为 ∣G∣|G|,故

#轨道=1∣G∣∑g∈G∣Fix⁡(g)∣.\#\text{轨道}=\frac1{|G|}\sum_{g\in G}|\operatorname{Fix}(g)|.

应用。 先把每个变换看成位置置换。不受其他条件限制的 qq 色染色要被该变换固定,同一个位置循环必须同色,因而有 qc(g)q^{c(g)} 种。圆环旋转 rr 格时有 gcd⁡(n,r)\gcd(n,r) 个位置循环。

例。 长为 4 的二色圆环,仅视旋转相同:四种旋转的不动点数为 16,2,4,216,2,4,2,答案 (16+2+4+2)/4=6(16+2+4+2)/4=6,直接 16/4=416/4=4 会漏算。

边界。 限制某种颜色数量、相邻颜色或图结构时,固定染色数需在循环压缩后的约束上重新计算,不能一律用 qc(g)q^{c(g)}。取模时只有 ∣G∣|G| 与模数互质才可乘逆元;否则在能保留整除信息的模数或整数范围下先求和再除。

8. NTT:单位根的阶决定能处理的长度#

识别。 两组数按“下标和”组合,需要求 ck=∑i+j=kaibjc_k=\sum_{i+j=k}a_i b_j;把它看成多项式乘法。

转化。 在素数域 Fp\mathbb F_p 中选阶恰为 LL 的元素 ω\omega。本册的二进制 NTT 要求 LL 是 2 的幂且 L∣(p−1)L\mid(p-1);若 gg 为原根,可取 ω=g(p−1)/L\omega=g^{(p-1)/L}。逆变换还要除以 LL。ACL 的卷积接口明确给出了素数模与可用二次幂长度条件。ACL convolution 官方文档

应用。 先取 L≥∣a∣+∣b∣−1L\ge|a|+|b|-1 的最小 2 次幂,检查根是否存在,再补零。模数 998244353=119⋅223+1998244353=119\cdot2^{23}+1 支持最长 2232^{23};调用本册 cp::convolution。任意改模数,原根和最大长度都要一起重推。

例。 (1+2x)(3+4x)=3+10x+8x2(1+2x)(3+4x)=3+10x+8x^2,需补到长度 4。模 7 的乘法群阶为 6,没有阶为 4 的元素,不能照搬长度 4 的常规 NTT。若不补零,算的是模 xL−1x^L-1 的循环卷积,会让高次项绕回低位。

9. 有限域不等于“整数模一个同样大的数”#

识别。 题目使用二进制多项式、CRC、扩域,或声称有 pkp^k 个域元素。

转化。 Fp[x]/(f)\mathbb F_p[x]/(f) 在 ff 不可约时是域;若 deg⁡f=k\deg f=k,每个元素可用次数小于 kk 的余式表示,共 pkp^k 个。原因是任意非零余式 aa 与 ff 互质,扩展 Euclid 给出 ua+vf=1ua+vf=1,从而 uu 是其逆元。二、三次多项式可通过检查基域上有无根判断不可约,高次不能只检查根。MIT 18.703:多项式环

例。 在 F2\mathbb F_2 上,f=x2+x+1f=x^2+x+1 在 0、1 都不为 0,故不可约。记 α=[x]\alpha=[x],则 α2=α+1\alpha^2=\alpha+1,α(α+1)=1\alpha(\alpha+1)=1。四个元素为 0,1,α,α+10,1,\alpha,\alpha+1;加法按位 XOR,乘法先做无进位多项式乘法,再模 ff。

边界。 Z4\mathbb Z_4 中 2⋅2=02\cdot2=0,因此不是这个四元域。若模 x2+1=(x+1)2x^2+1=(x+1)^2,非零 x+1x+1 的平方为 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_algebra

11. 完整调用示例#

下面的输出依次是:方程有解/秩/自由变量数,三角形生成树数,平方和插值值,置换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 1
3
30
2 3 1 4 5
5
抽象代数的竞赛用法
https://sanzenin.top/posts/obsidian/抽象代数的竞赛用法/
作者
Sanzenin 凪
发布于
2026-10-25
许可协议
CC BY-NC-SA 4.0

分享文章

生成精美分享图或复制链接,与更多人分享本文。

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取