# 1. 随机化算法分类中 Monte Carlo（可能错）与 Las Vegas（可能慢）的差异，以及随机化快速排序/快速选择的期望分析？ A Monte Carlo 可能出错但时间可控，Las Vegas 结果正确但可能变慢 ✓ 正确答案 B Monte Carlo 保证结果正确，Las Vegas 可能出错 C 两者都保证结果正确 D 两者都会出错
# 2. 矩阵快速幂在动态规划优化中的工程应用 A 它能把任意 DP 都优化到 O(log n) B 仅适用于线性递推，用转移矩阵的幂取代逐项递推 ✓ 正确答案 C 复杂度必为 O(n) D 它不能用于 Fibonacci 这类递推
# 3. 按位异或的区间问题中前缀异或数组如何快速求解任意区间异或，与"只出现一次的数字"系列的联系？ A 区间异或 = prefix[r] + prefix[l-1] B 区间异或 = prefix[r] ⊕ prefix[l-1] ✓ 正确答案 C 前缀异或只能用于单点查询 D 异或没有可逆性
# 4. 随机化快速选择（Quickselect）的期望复杂度分析与最坏退化？ A 最坏与期望都是 O(n) B 期望 O(n log n) C 期望 O(n)，最坏 O(n²) ✓ 正确答案 D 随机 pivot 能保证最坏 O(n)
# 5. Pollard Rho 的期望复杂度中为什么随机函数 f(x)=x²+c 的序列期望 O(√n) 步出现碰撞（生日悖论），从而期望 O(n^{1/4}) 找到因子？ A 期望 O(n) 找到最小因子 B 期望 O(n^{1/4}) 找到因子（基于生日悖论） ✓ 正确答案 C 期望 O(√n) 找到因子 D 与生日悖论无关
# 6. 期望线性时间的指示器变量分析法中快速选择中每个元素成为 pivot 的概率均等，指示器变量求和得期望 O(n) A 与随机性无关 B 所有元素都成为 pivot C 最坏情况出现概率为 1 D 每个元素被选为 pivot 的概率均等 ✓ 正确答案
# 7. 位运算的经典性质与应用中异或的性质（x^x=0、交换律）、n&(n-1) 消除最低位 1、lowbit 与树状数组的关系？ A n&(n-1) 会消除 n 的最高位 1 B 树状数组与 lowbit 无关 C 异或无交换律 D lowbit(x)=x&(-x) 取出最低位 1 对应的值 ✓ 正确答案
# 8. 状态压缩 DP 的位运算基础中如何用位掩码表示子集、枚举子集的技巧（sub=(sub-1)&mask）与复杂度分析？ A O(2^n) B O(n²) C O(n·2^n) D O(3^n) ✓ 正确答案
# 10. 异或线性基（XOR linear basis）的构造中逐数插入时从高位到低位消元为何能得到一组线性无关基，基的大小为何不超过 log(maxA)，如何用它求最大子集异或与判定某值能否被表示，复杂度 O(n log A)？ A ≤ n B ≤ log(maxA) ✓ 正确答案 C ≤ 64 D 无界
# 11. Fisher-Yates 洗牌为什么无偏，从后往前每次在 [0,i] 内均匀取随机下标并交换，为何每种排列出现概率恰好为 1/n!，与'随机交换 n 次'的常见错误实现偏差在哪，O(n) 时间 O(1) 额外空间的证明？ A 每种排列出现概率为 1/n! ✓ 正确答案 B 每次在 [0,n-1] 随机交换也能保证均匀 C 需要 O(n) 额外空间 D 随机交换 n 次与 Fisher-Yates 等价
# 13. 快速幂与快速乘的实现与边界中指数取模 (a^b mod p) 需要按位处理，快速乘如何避免乘法溢出？ A 与快速幂无关 B 提高乘法的精度 C 把 O(n) 乘法降到 O(log n) D 把乘法转成加法并逐位取模以规避 64 位乘法溢出 ✓ 正确答案
# 14. BSGS 的适用边界中要求群阶已知且能枚举 baby steps，阶巨大（≥2^64）时为什么必须改用 Pollard Rho 等亚指数/指数算法？ A 需要 O(√p) 空间存 baby steps，且群阶需已知可枚举 ✓ 正确答案 B 不能处理乘方 C 只能用于小素数 D 时间 O(p)
# 15. 概率方法（非构造存在性证明）在算法中的应用中 Lovász 局部 lemma 证明特定着色存在，随机舍入求解整数规划 A 若随机过程产生目标概率 >0 则存在 ✓ 正确答案 B 构造出具体解 C 必须确定性强 D 只能证明不存在
# 16. gcd/lcm 与扩展欧几里得中如何用 exgcd 求模逆元与一次不定方程，与费马小定理求逆的适用条件差异？ A 模为任意整数 B 存在任意 a C 模为素数且 a 不被模整除 ✓ 正确答案 D 与素数无关
# 17. Pollard-Rho 与 Miller-Rabin 在 stress test 数据生成的应用 A 与测试无关 B 两者都只做加法 C 两者都只做排序 D Miller-Rabin 判素、Pollard-Rho 分解 ✓ 正确答案
