# 1. 集合幂级数 exp/ln 在连通图计数问题中的应用中用子集卷积的 exp 求'所有子集的连通图数量'，复杂度 O(n²·2^n) A 任意图计数 F 与连通图计数 C 满足 F = exp(C) ✓ 正确答案 B 子集卷积可以直接用逐位乘法的 FWT 完成而不需分层 C 集合幂级数 exp 的单次乘法复杂度为 O(2^n) D ln 用于把任意图"合并"为连通图
# 2. 长链剖分的核心思想中为什么"最长链"用于优化树上深度相关 DP 的合并复杂度到 O(n)？ A 长链剖分中所有链长之和等于 n，故总合并代价 O(n) ✓ 正确答案 B 长链剖分按子树大小选择重儿子 C 长儿子数组必须每次重新复制 D 长链剖分的总复杂度为 O(n log n)
# 3. 多项式多点求值的分治思路中为什么用 (x-x_i) 的乘积多项式做多项式取模，复杂度 O(n log^2 n)？ A 多点求值的总复杂度为 O(n²) B 多点求值必须逐点代入做除法 C 区间乘积多项式的构造复杂度为 O(n log n) D P 在 x_i 处的值等于 P 对 (x - x_i) 取模后余式的常数项 ✓ 正确答案
# 4. FMT（快速莫比乌斯变换）子集和变换与 SOS DP 的关系中高维前缀和的位运算实现，超集和与子集和的方向差异 A 子集和与超集和采用完全相同的递推方向 B 超集和递推式为 dp[mask] += dp[mask ^ (1<<i)] C SOS DP 的子集和变换等价于对 n 维超立方体做高维前缀和，复杂度 O(n·2^n) ✓ 正确答案 D FMT 只能处理子集和，不能处理超集和
# 5. 子集卷积（Subset Convolution）的占位多项式 O(n²·2^n) 实现中为何需要引入'占位维度'（按 popcount 分层）来避免超集/子集混淆 A 子集卷积可以直接用 FWT 逐点相乘得到 B 占位多项式实现的总复杂度为 O(n·2^n) C 子集卷积允许两个子集相交 D 占位多项式按 popcount 分层，利用"不相交子集 popcount 相加等于结果 popcount"约束 ✓ 正确答案
# 6. 集合幂级数在'子集 DP'中的工程取舍中 n≤20 时 O(3^n) 枚举 vs O(n²·2^n) 子集卷积 A 子集卷积的内存需求为 O(3^n) B 子集卷积的常数通常比子集枚举小 C n = 20 时 3^20 远小于 4e8，任意实现都能通过 D n = 18 时 O(3^n) 枚举的总子集枚举量为 Σ 2^popcount = 3^n ✓ 正确答案
# 7. FWT（快速沃尔什变换）的 XOR 卷积 O(n log n) 正变换与逆变换推导中为何正变换矩阵为 [[1,1],[1,-1]]，逆变换需乘 1/2 A XOR 变换矩阵的逆矩阵需要 O(n²) 计算 B XOR 正变换蝶形为 a' = a + b, b' = a - b，逆变换为同样蝶形后乘 1/2 ✓ 正确答案 C FWT 逆变换不需要任何缩放因子 D XOR 卷积的变换矩阵为 [[1,1],[0,1]]
# 8. 中国剩余定理（CRT）的两种实现中直接 CRT 与 Garner 算法，为什么 Garner 适合增量合并同余式？ A Garner 算法逐个确定混合基数系数，新增同余式时只需对新模数求逆 ✓ 正确答案 B 直接 CRT 可以处理模数不互素的情况而无需调整 C Garner 算法要求所有模数都是素数 D 直接 CRT 与 Garner 在增量合并场景下开销相同
# 9. 长链剖分求 k 级祖先中 O(1) 查询比倍增更优，预处理复杂度如何？ A 长链剖分求 k 级祖先的正确性不依赖链长性质 B 长链剖分法的预处理空间为 O(n) C 倍增法的查询复杂度为 O(1) D 长链剖分求 k 级祖先的查询分"跳链顶 + 链内 O(1) 定位"两步 ✓ 正确答案
# 10. 长链剖分 DP 合并的指针复用技巧中为什么把重儿子数组移位复用能避免复制，总空间 O(n)？ A 轻儿子合并的总代价为 O(n log n) B 指针复用技巧的总空间复杂度为 O(n log n) C 长儿子的深度数组必须复制到新内存 D 同一条长链上 dfn 连续，长儿子数组可通过指针加 1 直接继承 ✓ 正确答案
# 11. FWT 在竞赛中的典型场景中子集异或卷积求'选若干个数异或值为 k 的方案数' A FWT 只能处理长度小于 16 的数组 B XOR 卷积的 FWT 后需要逐点做除法 C 每个数只能用一次与可重复使用在 FWT 框架下处理完全相同 D 选 t 个数异或值为 y 的方案数 = FWT(f) 逐点 t 次幂后再逆变换的第 y 项 ✓ 正确答案
# 12. NTT 在 k=23, n=2^23 的最坏情况常数因子与缓存优化。 A n = 2^23 时蝶形运算总数约 (n/2)·log₂n ✓ 正确答案 B 取模运算比乘法更快，无需优化 C 2^23 规模的旋转因子表约 4KB，能完全放入 L1 缓存 D Montgomery 约减会增加取模次数
# 13. 为何子集卷积不能直接用 FWT，XOR/AND/OR 卷积都不等于子集卷积，必须引入占位多项式 A OR 卷积允许 T∩U ≠ ∅，而子集卷积要求不相交 ✓ 正确答案 B 子集卷积可以直接用 XOR-FWT 逐点相乘得到 C 重叠子集对的 popcount 之和等于并集的 popcount D 占位多项式的作用是降低卷积维度
# 14. NTT 实现多项式乘法的位逆序重排中迭代版需要 bit-reversal 置换，原地蝴蝶运算如何避免额外数组？ A 逆 NTT 只需将旋转因子取共轭，无需任何缩放 B 蝶形运算必须复制到新数组才能完成 C bit-reversal 置换的时间复杂度为 O(n log n) D 迭代版 NTT 需要 bit-reversal 置换来恢复正确的蝶形配对顺序 ✓ 正确答案
# 15. 集合幂级数的指数/对数在组合计数中的角色中连通图计数用 exp（SET 构造），任意图与连通图的生成函数如何关联？ A ln 用于把连通图合并成任意图 B 连通图计数等于任意图计数的 exp C SET 构造（无序分量集合）对应的是普通乘法 D 任意图计数等于连通图计数的集合幂级数 exp：F = exp(C) ✓ 正确答案
# 16. FWT 的 AND/OR 卷积与 XOR 卷积在变换矩阵上的区别中 OR 正变换 [[1,1],[0,1]]，AND 正变换 [[1,0],[1,1]] A XOR 逆变换不需要任何缩放 B AND 正变换的矩阵为 [[1,1],[1,-1]] C OR 正变换对应子集和（前缀和）蝶形 a += b，逆变换无 1/2 因子 ✓ 正确答案 D 三种 FWT 使用完全相同的变换矩阵
# 17. SOS DP（Sum Over Subsets）的 DP 递推式 dp[mask][i] = dp[mask][i-1] + dp[mask^(1<<i)][i-1] 与 FMT 的等价性 A SOS DP 的滚动数组实现与 FMT 的子集和正变换逐维等价 ✓ 正确答案 B SOS DP 递推要求 mask 的第 i 位为 0 时也要累加 C SOS DP 的时间复杂度为 O(3^n) D SOS DP 只能处理子集和，不能做超集和
# 18. 多项式多点求值 (n 个点代入 m 次多项式) 在分治 + 模逆的 O((n+m) log²(n+m)) 实现。 A 到达叶子时余式为 P 本身 B 多项式取模无需求逆，直接逐位相除即可 C 多点求值的每层复杂度为 O(n²) D 因为区间乘积多项式 M 在所有求值点上为 0，P 与 P mod M 在这些点取值相同 ✓ 正确答案
# 19. 多项式对数函数 ln 在复数与负数的分支切割工程实现。 A 复数域实现时无需固定幅角分支 B 多项式 ln 可以直接对任意常数项逐项展开 C 多项式 ln 定义为 ∫ P'/P，要求常数项为单位元（通常为 1） ✓ 正确答案 D 多项式 ln 的实现不需要多项式求逆
# 20. 多项式开方 (F² ≡ G) 在牛顿迭代 + 二次剩余的 O(n log n) 工程实现。 A 多项式开方用牛顿迭代 F' = (F + G·F^{-1})/2，每步长度翻倍，总 O(n log n) ✓ 正确答案 B 多项式开方要求 G 的常数项为 0 C 开方迭代每步只需要一次乘法 D 开方结果的常数项是唯一确定的，无需选择
# 21. 多项式快速插值 (n 个点构造 m 次多项式) 在 Lagrange/Newton 的 O((n+m) log²(n+m))。 A 快速插值的总复杂度为 O(n²) B 拉格朗日插值的权 w_i 与 y_i 无关 C 分治合并插值多项式只需一次 NTT D 快速插值先求 M(x)，再用多点求值计算 M'(x_i) 得到权 w_i = y_i/M'(x_i) ✓ 正确答案
# 22. 多项式求逆在牛顿迭代 (F(x)·G(x) ≡ 1 mod x^n) 的 O(n log n) 工程实现。 A 多项式求逆不要求常数项可逆 B 多项式求逆的牛顿迭代式为 G' = G(2 - FG)，误差每步平方增长阶数 ✓ 正确答案 C 多项式求逆的复杂度为 O(n²) D 牛顿迭代每步只需一次乘法
# 23. 多项式复合与复合逆的应用中如何用拉格朗日反演求树的计数（如度为 i 的节点数），与普通生成函数的区别？ A 若 T = x·φ(T)，拉格朗日反演给出 [x^n]T = (1/n)[t^{n-1}]φ(t)^n ✓ 正确答案 B 拉格朗日反演要求树类必须是有标号的 C 复合逆与 exp 在处理树结构时完全等价 D 度为 i 的节点数只能用枚举统计，无法用生成函数计算
# 24. 长链剖分优化树上深度 DP 的合并过程中为什么长链上直接继承、短链暴力合并能保证总 O(n)，请用'每条链只合并一次'论证？ A 链长总和为 O(n log n) B 长链剖分合并的总代价为 O(n log n) C 链内合并也需要逐深度复制 D 每条长链的数组只在链顶被合并一次，合并代价等于链长，故总代价 O(n) ✓ 正确答案
# 25. 多项式除法与取模的实现中需要先反转系数再用多项式求逆，O(n log n) 的步骤如何分解？ A 多项式除法不需要求逆运算 B 多项式除法可以直接逐位相除达到 O(n log n) C 余式 R 在反转后落在高次端，需要保留 D 反转后 rev(Q) ≡ rev(A)·rev(B)⁻¹ (mod x^{n-m+1})，故除法可化为求逆与乘法 ✓ 正确答案
# 26. 子集卷积在集合划分计数中的应用中如何用占位多项式计算'将集合划分成若干部分'的方案数，与枚举子集 O(3^n) 的对比？ A 集合划分计数对应集合幂级数的 exp，需除以 k! 消除部分顺序 ✓ 正确答案 B 划分计数对应子集卷积的 ln C O(3^n) 枚举法的递推依赖"最大元素所在部分"的枚举 D 子集卷积实现划分计数的复杂度为 O(3^n)
# 27. 分治 FFT 与牛顿迭代的取舍中计算多项式 exp/ln 时为什么用倍增牛顿而非直接分治卷积，两者的常数与实现复杂度差异？ A 两者复杂度均为 O(n²) B 分治 FFT 每层只做一次点乘，常数更小 C ln 的计算不需要多项式求逆 D 牛顿迭代计算 exp/ln 时长度翻倍，总复杂度 O(n log n)，常数小于分治 FFT ✓ 正确答案
# 28. 长链剖分与重链剖分的分工中深度相关 DP 用长链、路径查询用重链的判断标准？ A 长链剖分适合任意路径的区间加操作 B 重链剖分按最大深度选重儿子 C 长链剖分按最大深度选儿子，适合深度相关 DP 的 O(n) 合并 ✓ 正确答案 D 两种剖分在任何问题上等价
# 29. 长链剖分求树上各深度信息中为什么长链顶端的答案只合并一次保证 O(n)，与启发式合并（DSU on tree）的区别？ A DSU on tree 按深度选择重儿子 B DSU on tree 的每个节点恰好被统计一次 C 长链剖分中每条链的数组只在链顶合并一次，合并代价等于链长，总 O(n) ✓ 正确答案 D 长链剖分能处理与深度无关的任意子树统计
