数论基础与位运算技巧与随机化算法 - 面试题

#

★★★

1. 随机化算法分类中 Monte Carlo（可能错）与 Las Vegas（可能慢）的差异，以及随机化快速排序/快速选择的期望分析？

问题

请解释随机化算法两大分类——Monte Carlo（可能错）与 Las Vegas（可能慢）——的差异，并说明随机化快速排序与快速选择的期望复杂度分析？

考察点

随机化算法两大类别的结果正确性保证与运行时间保证
随机化快速排序/快速选择的期望时间推导
随机化在对抗恶意输入下的鲁棒性意义

答案

Monte Carlo 算法保证在限定的时间内运行并返回结果，但结果有概率错误（错误概率可通过重复运行以指数级降低）；Las Vegas 算法保证结果一定正确，但运行时间可能在少量随机度下变慢（随机性只影响时间不影响正确性）。随机化快速排序每次随机选 pivot，期望比较次数为 O(n log n)，期望快速选择为 O(n)；随机化保证了"期望"是相对任意输入序列取平均，而非对固定输入取平均，从而能对抗最坏情形输入。在确定性选择固定 pivot 时，如果输入恰好糟糕，会退化到 O(n²)；随机化把这种坏情况概率化并摊薄到所有输入上。

解析

核心在于随机化把"运气"从输入转移到算法内部，使任何输入下期望时间都受控。期望分析用线性期望与递归方程：快排期望代价 T(n)=n+Σ_{k=0}^{n-1}(1/n)(T(k)+T(n-1-k))，解得 T(n)=O(n log n)。快速选择同理，期望 O(n)。Monte Carlo 与 Las Vegas 可互相转化：对 Las Vegas 可加超时转 Monte Carlo，对 Monte Carlo 可重复验证转 Las Vegas。

#

★★★

2. 矩阵快速幂在动态规划优化中的工程应用

问题

说明矩阵快速幂如何将线性递推的动态规划转化为矩阵幂运算以加速求解？

考察点

线性递推到矩阵乘法的转化建模
矩阵快速幂 O(log n) 的复杂度
与生成函数/特征根法的联系

答案

当 DP 的转移是线性的（如 Fibonacci f(n)=f(n-1)+f(n-2)），可以构造转移矩阵 M，把状态向量 v 与 M 的幂相乘的展开写成递推式。于是 f(n) 对应 M^n 乘初始向量的某一分量，用二进制快速幂将矩阵连乘降到 O(k³ log n)（k 为状态维数，k 小时远优于 O(n)）。工程上常用于斐波那契第 n 项、常系数线性递推（如线性递推求第 n 项）、以及状态转移矩阵较小的矩阵次数 DP。注意矩阵乘法需实现为可对任意模数取模、并处理好维度较高的常数优化。

解析

关键是把"逐项递推"改写成"矩阵乘法"，从而利用矩阵结合律用快速幂，把 O(n) 的迭代降到 O(log n)。这一思想本质是线性递推的线性代数表示，与特征多项式、线性递推的矩阵特征值分析相通。

示例代码

// 斐波那契：矩阵快速幂求第 n 项，O(log n)
long[][] mul(long[][] a, long[][] b, long mod) {
    int n = a.length, m = b[0].length, p = b.length;
    long[][] c = new long[n][m];
    for (int i = 0; i < n; i++)
        for (int k = 0; k < p; k++) if (a[i][k] != 0)
            for (int j = 0; j < m; j++)
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
    return c;
}
long fib(long n, long mod) {
    long[][] base = {{1,1},{1,0}};
    long[][] res = {{1,0},{0,1}}; // 单位阵
    while (n > 0) {
        if ((n & 1) == 1) res = mul(res, base, mod);
        base = mul(base, base, mod);
        n >>= 1;
    }
    return res[0][1]; // f(n)
}

#

★★★

3. 按位异或的区间问题中前缀异或数组如何快速求解任意区间异或，与"只出现一次的数字"系列的联系？

问题

说明如何用前缀异或数组快速求解任意区间 [l,r] 的异或和，以及它与"只出现一次的数字"系列题目的联系？

考察点

前缀异或的定义与区间异或公式 prefix[r]⊕prefix[l-1]
异或的逆运算仍是自身（x⊕x=0）
与"只出现一次的数字"的消去思想联系

答案

定义前缀异或 prefix[i]=a[0]⊕a[1]⊕…⊕a[i]，则区间 [l,r] 的异或为 prefix[r]⊕prefix[l-1]。由于 a[l..r] 的部分在 prefix[r] 与 prefix[l-1] 中恰好出现两次被抵消，剩下正是区间内元素。这依赖异或自反性质 x⊕x=0。同理，"只出现一次的数字"利用 a⊕a=0 把所有成对元素抵消，只剩出现奇数次的数。二者本质都是"异或即不带进位的模 2 加法，可逆可消"的体现。

解析

前缀异或是前缀和的位运算版本，把区间查询降到 O(1)，配合乘法/哈希可处理"异或等于某值"的子数组计数问题。而"只出现一次"系列则用异或的唯一性做集合消去，是同一性质的两种应用。

示例代码

int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] ^ a[i];
// 区间 [l, r] 异或（0-based）
int rangeXor = prefix[r + 1] ^ prefix[l];

#

★★★

4. 随机化快速选择（Quickselect）的期望复杂度分析与最坏退化？

问题

分析随机化快速选择（Quickselect）的期望时间复杂度，并说明其最坏情况如何退化及如何避免？

考察点

期望 O(n) 的推导（线性期望）
最坏 O(n²) 的退化机制
随机 pivot 与中位数中位数（median of medians）的对比

答案

随机化快速选择每次随机选 pivot，把数组划分为小于和大于 pivot 的两部分，递归到包含目标值的一侧。期望时间 O(n)：因为每次选到任意 pivot 概率相等，某次递归只处理一侧，期望规模按几何级数收缩，期望总比较数约为 2n（线性）。最坏情况发生在每次选到极端 pivot（如最大或最小），导致只缩小一个元素，递归 n 次，O(n²)。随机化把这种坏情况概率化，但仍有不可忽略的坏输入概率；若需确定性最坏 O(n)，可用中位数中位数算法（median of medians）保证每次分离出至少固定比例的元素。

解析

期望分析的关键是线性期望：期望总工作量 = Σ 每次划分的期望代价，且每次只剩一侧递归，规模期望减半，故期望 O(n)。实用上随机 pivot 足够，median of medians 常数大，工程中少用。

#

★★

5. Pollard Rho 的期望复杂度中为什么随机函数 f(x)=x²+c 的序列期望 O(√n) 步出现碰撞（生日悖论），从而期望 O(n^{1/4}) 找到因子？

问题

解释 Pollard Rho 分解算法的期望复杂度，说明为何随机序列约 O(√n) 步发生碰撞（生日悖论），从而整体期望 O(n^{1/4}) 找到因子？

考察点

生日悖论与随机序列碰撞的期望步数
f(x)=x²+c 的伪随机序列与 p 模下的碰撞
Floyd 判圈与 gcd 检测

答案

Pollard Rho 用伪随机函数 f(x)=x²+c (mod n) 生成序列，若 n 有因子 p，则序列模 p 上是一个周期序列。由生日悖论，随机序列在长度约 O(√p) 时出现重复（碰撞）的概率接近 1/2。当两个不同的 x 模 n 值不同但模 p 相同（即 x≡y mod p 且 x≠y mod n），则 gcd(|x-y|, n) 是 n 的非平凡因子 p。因此期望 O(√p) 步得到碰撞，而 p≤√n（最小因子），故期望 O(n^{1/4}) 步找到因子。用 Floyd 判圈或 Brent 加速检测，并且用累积 gcd 来降低常数。

解析

关键洞察是生日悖论把"找因子"的随机碰撞期望从 O(p) 降到 O(√p)，故整体 O(n^{1/4})。这在 n 达到 64 位时仍可行，是 RSA 大整数分解中小因子分解的实用工具。

#

★★

6. 期望线性时间的指示器变量分析法中快速选择中每个元素成为 pivot 的概率均等，指示器变量求和得期望 O(n)

问题

用指示器变量分析法证明快速选择的期望时间 O(n)？

考察点

指示器随机变量与线性期望
每个元素成为 pivot 概率均等的论证
期望总比较数的求和

答案

在快速选择中，定义指示器变量 X_i 表示元素 i 是否在某次划分中被选取为 pivot 参与比较。由于每次在区间内均匀随机选 pivot，每个元素被选为 pivot 的概率均等。关键观察：两元素 i<j 发生比较当且仅当 i 或 j 是区间 [i,j] 内第一个被选为 pivot 的元素，概率为 2/(j-i+1)。期望总比较数 = Σ_{i<j} P(比较发生) = Σ_{i<j} 2/(j-i+1) = Σ_{d=1}^{n} 2(n-d)/d = O(n log n) 对快排；而快速选择只递归一侧，实际期望为 O(n)。用指示器变量与线性期望，把期望时间分解为各单元事件的概率之和，免去求联合分布。

解析

指示器变量法的价值在于把复杂随机过程的总工作量分解为线性期望的单元事件概率求和，每条贡献可独立计算。快排的 O(n log n) 与快速选择 O(n) 的差异正是"只递归一侧"与"递归两侧"的分野。

#

★★

7. 位运算的经典性质与应用中异或的性质（x^x=0、交换律）、n&(n-1) 消除最低位 1、lowbit 与树状数组的关系？

问题

总结位运算的经典性质（异或、n&(n-1)、lowbit）及其在算法中的应用？

考察点

异或的三条基本性质
n&(n-1) 消除最低位 1 及统计 1 的个数
lowbit 与树状数组区间维护

答案

异或满足：x⊕x=0、x⊕0=x、交换律与结合律，因此可用于成对抵消与可逆运算。n&(n-1) 能消除 n 二进制最低位的 1，反复执行即可统计二进制中 1 的个数（O(#1)），也可用于判断 n 是否为 2 的幂（n&(n-1)==0）。lowbit(x)=x&(-x) 取出最低位 1 对应的值，是树状数组（Fenwick Tree）的核心：单点更新沿 i+=lowbit(i) 向上传播，前缀查询沿 i-=lowbit(i) 累加，从而 O(log n) 完成区间和/单点修改。

解析

这些位运算性质是"用位表示集合与计数"的基础。n&(n-1) 与 lowbit 都基于补码表示，-x 是 x 取反加一，使 x&(-x) 恰好保留最低位 1。树状数组正是利用 lowbit 划分前缀区间。

示例代码

int countOnes(int n) { int c = 0; while (n != 0) { n &= n - 1; c++; } return c; }
boolean isPow2(int n) { return n > 0 && (n & (n - 1)) == 0; }
int lowbit(int x) { return x & -x; }

#

★★

8. 状态压缩 DP 的位运算基础中如何用位掩码表示子集、枚举子集的技巧（sub=(sub-1)&mask）与复杂度分析？

问题

说明状态压缩 DP 中如何用位掩码表示子集，以及枚举子集的技巧 sub=(sub-1)&mask 与复杂度分析？

考察点

位掩码表示集合/子集
枚举子集的迭代技巧
复杂度 Σ 2^{|S|} = 3^n

答案

状态压缩 DP 用 n 位二进制数表示集合，第 i 位为 1 表示元素 i 在集合中。对给定掩码 mask，枚举其所有子集可用 sub=(sub-1)&mask：从 mask 出发，每次减 1 后与 mask 取与，得到下一个更小的子集，直到 sub=0。枚举一个含 k 个元素的集合的所有子集共 2^k 个，而对全部 2^n 个集合分别枚举其子集的总复杂度为 Σ_{S⊆U} 2^{|S|} = 3^n（因为每个元素有三种状态：不在 S、在 S 不在子集、在 S 且在子集）。常用于旅行商、集合覆盖、图上 DP 等。

解析

(sub-1)&mask 的技巧保证了 sub 始终是 mask 的子集且以递减方式遍历所有子集，避免重复。3^n 的复杂度来自每个元素三种归属，是 bitmask 枚举子集的标准上界。

示例代码

for (int sub = mask; sub != 0; sub = (sub - 1) & mask) {
    // 处理子集 sub
}

#

★★

9. 快速幂的二进制分解原理与矩阵快速幂中如何把线性递推转化为矩阵幂加速？

问题

说明快速幂的二进制分解原理，以及如何把线性递推转化为矩阵幂来加速？

考察点

二进制分解指数与折半相乘
常数模幂 O(log n)
线性递推到矩阵的建模

答案

快速幂把指数 b 二进制展开，a^b = Π a^{2^i}（其中第 i 位为 1），通过反复平方 base=a^{2^i} 并仅在与当前位为 1 时乘入结果，将乘法次数降到 O(log b)。矩阵快速幂把矩阵当"数"做同样的二进制分解，把 T(n) 的线性递推用转移矩阵 M 表示，使第 n 项为 M^n 与初始向量的乘积的某分量，复杂度 O(k³ log n)。这是把"线性递推"从 O(n) 迭代加快到 O(log n) 的标准手法。

解析

二进制分解的本质是乘法的结合律与指数可拆分；反复平方是分治思想的体现。矩阵版本把标量换成矩阵，幂的意义转移到状态转移的重复应用，是 DP 状态转移的代数化。

#

★★

10. 异或线性基（XOR linear basis）的构造中逐数插入时从高位到低位消元为何能得到一组线性无关基，基的大小为何不超过 log(maxA)，如何用它求最大子集异或与判定某值能否被表示，复杂度 O(n log A)？

问题

说明异或线性基（XOR basis）的构造原理、基的大小上界，以及求最大子集异或与判定可达性的应用？

考察点

从高位到低位的消元插入
基大小 ≤ log(maxA)
最大子集异或与可达性判定

答案

线性基维护一组线性无关的二进制向量，插入新数 x 时从最高位到最低位逐位处理：若当前位为 1 且该位已有基，则用 x ^= base[i] 消去该位；若该位无基，则把当前 x 存入第 i 位并结束。这样每个基的最高位互不相同，保证线性无关，且最多有 log(maxA) 个基。求最大子集异或：从高位到低位贪心，若 ans ^ base[i] > ans 则更新，得到最大值。判定某值能否被表示：类似插入过程，若逐位消元后 x 变为 0 则可达。所有操作 O(n log A)。

解析

从高位到低位消元保证"每个基底最高位唯一"，从而独立且可逆向生成 span。贪心求最大异或依赖"高位优先"的字典序最优性。这是求异或最大/最小/第 k 小的经典工具。

示例代码

long[] base = new long[64];
void insert(long x) {
    for (int i = 63; i >= 0; i--) if ((x >> i & 1) == 1) {
        if (base[i] == 0) { base[i] = x; return; }
        x ^= base[i];
    }
}
long maxXor() {
    long ans = 0;
    for (int i = 63; i >= 0; i--) ans = Math.max(ans, ans ^ base[i]);
    return ans;
}

#

★★

11. Fisher-Yates 洗牌为什么无偏，从后往前每次在 [0,i] 内均匀取随机下标并交换，为何每种排列出现概率恰好为 1/n!，与'随机交换 n 次'的常见错误实现偏差在哪，O(n) 时间 O(1) 额外空间的证明？

问题

证明 Fisher-Yates 洗牌的无偏性，并说明它与"随机交换 n 次"的错误实现的偏差？

考察点

无偏性证明（乘法原理）
常见错误实现的偏差
O(n) 时间 O(1) 空间

答案

Fisher-Yates 从后往前，对 i 从 n-1 到 1，从 [0,i] 均匀随机选 j 并交换 a[i] 与 a[j]。每种排列出现的概率为 Π_{i=1}^{n-1} 1/(i+1) = 1/n!，因为每一步都确定一个位置且概率独立均等，故无偏。错误实现"随机交换 n 次（每次在 [0,n-1] 选两个下标）"产生的排列概率不均衡：因为交换图是边可重复的随机游走，某些排列可被多条路径到达，概率不同，且不满足均匀分布。Fisher-Yates 只做 n-1 次交换，O(n) 时间、O(1) 额外空间。

解析

无偏性依赖于"第 i 步从剩余未确定位置中均匀抽取"，每一步把随机性限定在尚未定稿的位置，从而每个排列有唯一确定的生成路径。错误实现允许重复交换导致多路径合并，破坏均匀性。

示例代码

for (int i = n - 1; i > 0; i--) {
    int j = ThreadLocalRandom.current().nextInt(i + 1);
    int t = a[i]; a[i] = a[j]; a[j] = t;
}

#

★★

12. 模运算与同余性质中模加法/乘法/幂的运算规则，以及负数取模在不同语言中的差异与处理？

问题

总结模运算的加法/乘法/幂规则，以及负数取模在不同语言中的差异与统一处理？

考察点

模加法/乘法/幂规则
负数取模的语言差异
统一到非负模的规范处理

答案

模运算满足 (a+b) mod m = ((a mod m)+(b mod m)) mod m，乘法同理；幂用快速幂。除法不直接取模，需通过乘法逆元。负数取模在不同语言不同：Python 中 -7 % 3 = 2（结果非负，商向下取整），而 C/C++/Java 中 -7 % 3 = -1（结果与被除数同号，商向零取整）。统一处理可在使用前对负数规范化：((x % m) + m) % m，保证结果落在 [0, m-1]。减法同理用 (a-b+m)%m 避免负值。

解析

模运算本质是剩余类环上的运算，规则由同余关系导出。负数取模差异源于不同的"商"取整方向约定，工程上统一用"加模再取模"规范化即可规避。

示例代码

long norm(long x, long m) { return ((x % m) + m) % m; }
long add(long a, long b, long m) { return norm(a + b, m); }
long mul(long a, long b, long m) { return norm(a * b, m); }

#

★

13. 快速幂与快速乘的实现与边界中指数取模 (a^b mod p) 需要按位处理，快速乘如何避免乘法溢出？

问题

说明快速幂为何需要按位处理指数，以及快速乘如何避免乘法溢出？

考察点

二进制分解指数
乘法溢出问题
快速乘（倍增累加）规避溢出

答案

快速幂按指数 b 的二进制位逐位处理：b 的每一位决定是否乘入当前 base 的平方，从而把 O(b) 次乘法降到 O(log b)。这在 p 很大时必要，因为直接循环 b 次不可行。快速乘用于 ab mod p 在 a、b 很大（如 1e18）时乘积溢出 64 位的问题：用倍增累加把 b 拆成二进制，ab = Σ a*2^i（对应位为 1），每次加前取模，避免中间乘积溢出。两法结合可实现大模数下的幂运算。

解析

按位处理是"分治/二进制分解"思想；快速乘则是把乘法化解为"加法+取模"的循环，等价于把 b 二进制展开。两者都牺牲一点常数换取不溢出与大指数可行。

示例代码

long mulMod(long a, long b, long p) { // a*b mod p 避免溢出
    long r = 0; a %= p;
    while (b > 0) { if ((b & 1) == 1) r = (r + a) % p; a = (a * 2) % p; b >>= 1; }
    return r;
}
long powMod(long a, long b, long p) {
    long r = 1 % p; a %= p;
    while (b > 0) { if ((b & 1) == 1) r = mulMod(r, a, p); a = mulMod(a, a, p); b >>= 1; }
    return r;
}

#

★

14. BSGS 的适用边界中要求群阶已知且能枚举 baby steps，阶巨大（≥2^64）时为什么必须改用 Pollard Rho 等亚指数/指数算法？

问题

说明 BSGS 算法的适用边界，以及群阶巨大时为何必须改用 Pollard Rho 等算法？

考察点

BSGS 的 baby-step giant-step 原理
需要群阶已知且可枚举 baby steps（O(√n)）
阶太大时改用 Pollard Rho 离散对数

答案

BSGS（Baby-step Giant-step）求解离散对数 a^x ≡ b (mod p)：令 m=⌈√p⌉，把 x 写成 x=im+j，预计算 baby steps（a^j 的哈希表，O(√p) 空间），再依次检查 giant steps（a^{im}），总 O(√p) 时间。它要求群阶已知且 √p 在可枚举范围内（内存需存 baby steps）。当群阶 ≥2^64 时 √p ≥ 2^32，baby steps 表大到不可行，故须改用 Pollard Rho 的离散对数版本（期望 O(√p) 时间、O(1) 空间）等亚指数算法。

解析

BSGS 是"时间-空间权衡"的经典：以 O(√p) 空间换 O(√p) 时间。当空间不可行时，Pollard Rho 用伪随机游走找碰撞，保持 O(√p) 期望时间但只需 O(1) 空间，因而适合超大阶。

#

★

15. 概率方法（非构造存在性证明）在算法中的应用中 Lovász 局部 lemma 证明特定着色存在，随机舍入求解整数规划

问题

说明概率方法（非构造存在性证明）在算法中的应用，如 Lovász 局部引理与随机舍入？

考察点

概率方法的思想（存在性证明）
Lovász 局部引理
随机舍入求解整数规划

答案

概率方法证明某对象存在：构造一个随机过程，若其产生目标对象的概率 >0，则存在性得证。它常是非构造的，仅证明存在。Lovász 局部引理（LLL）用于证明当"坏事件"相互很少依赖时，存在使所有坏事件都不发生的赋值，即使每个坏事件单独概率不小。随机舍入用于整数规划：先解线性规划松弛，再把分数解按概率舍入为整数，可证明期望近似比（如最大割、集合覆盖）。这些方法把"存在性/近似性"从构造转为概率论证。

解析

概率方法的价值在于证明界而非给出具体算法，常与去随机化（method of conditional expectations）结合转成确定性算法。LLL 与随机舍入是研究界与近似算法的两大支柱。

#

★

16. gcd/lcm 与扩展欧几里得中如何用 exgcd 求模逆元与一次不定方程，与费马小定理求逆的适用条件差异？

问题

说明扩展欧几里得（exgcd）如何求模逆元与一次不定方程，以及与费马小定理求逆的适用条件差异？

考察点

exgcd 求解 ax+by=gcd(a,b)
用 exgcd 求模逆元
费马小定理求逆需模素数

答案

扩展欧几里得在求 gcd(a,b) 的同时回溯出整数 x,y 使 ax+by=gcd(a,b)。要求 a 的模 m 逆元，即解 ax≡1 (mod m)，等价于 ax+my=1，当 gcd(a,m)=1 时有解，x 即逆元。费马小定理 a^{m-1}≡1 (mod m)（m 为素数且 a 不被 m 整除）给出逆元 a^{m-1}... 即 a^{m-2} mod m，用快速幂求得。差异：exgcd 对任意 m（只要 gcd(a,m)=1）都适用，费马小定理要求模为素数。

解析

两者都求逆元，但 exgcd 更通用（适用于合数模），费马小定理需要素数模但实现简单（快速幂）。选择取决于模是否为素数。

示例代码

long[] exgcd(long a, long b) { // 返回 {g, x, y} 满足 ax+by=g
    if (b == 0) return new long[]{a, 1, 0};
    long[] r = exgcd(b, a % b);
    return new long[]{r[0], r[2], r[1] - (a / b) * r[2]};
}
long inv(long a, long m) { // gcd(a,m)=1
    long[] r = exgcd(a, m);
    return ((r[1] % m) + m) % m;
}

#

★

17. Pollard-Rho 与 Miller-Rabin 在 stress test 数据生成的应用

问题

说明 Pollard-Rho 与 Miller-Rabin 在压力测试（stress test）数据生成中的作用？

考察点

Miller-Rabin 素性检测
Pollard-Rho 大整数分解
生成对抗性大数/素数测试数据

答案

在压力测试生成针对数论算法的对抗数据时，Miller-Rabin 用于快速判定一个测试输入是否为素数（概率性，可多轮降低错误率），Pollard-Rho 用于对合数做质因数分解，从而构造"伪素数"（强伪素数）、Carmichael 数或特定结构的大合数来触发被测算法的边界。二者配合可在 O(n^{1/4}) 内分解 64 位整数，用以验证素性判定、分解、逆元等算法的能力与 bug。

解析

stress test 的核心是构造极端输入。Miller-Rabin 提供素性判定，Pollard-Rho 提供分解，二者结合能生成并验证"难以区分素数与合数"的对抗用例，检验被测程序的正确性与鲁棒性。