CSP-S 第一轮通关指南 CSP-S R1 Passport

面向 CSP-S（提高级）第一轮（初赛）。S 组初赛 = J 组全部内容 + 提高级知识，且数学与复杂度分析占比更大。本文按 NOI 大纲 2025（提高级）梳理常考知识点，结合 CSP-S 2025 真题、洛谷 SCP2025-S 与 SCP2026-S1（难度高于真题）模拟赛，总结经验之谈与易错坑点。

参考：NOI 大纲 2025 ｜ CSP-S 2025 真题 ｜ 洛谷 SCP2025-S、SCP2026-S1 模拟赛

每个考点统一按「知识点 → 讲解 → 例题 → 解析 → 易错辨析 / 常见变形 / 使用条件与技巧」的结构整理。J 组基础（进制、二叉树、排序、DP 入门）见 普及组篇。

0. 考试结构 & 与 J 组的区别

板块	题量	分值	说明
单项选择题	15 题	30 分	每题 2 分
阅读程序	3 题 17 小问	40 分	判断 T/F + 单选 + 多选
完善程序	2 题 10 小问	30 分	每题 3 分

时间与策略

• 120 分钟，建议与 J 组相同：单选 25~30 min，阅读 50~60 min，完善 30 min，留 10 min 检查。
• 判断题不倒扣分（以当年通知为准），不会也要蒙。
• S 组选择题常考"概念辨析"（哪个说法正确/错误），先把每个选项当作判断题逐项排除。

J 组之外，S 组多出来的板块

板块	新增内容
复杂度分析	主定理、递归式、STL 复杂度陷阱
C++	类、运算符重载、STL 高级容器、编译选项
数据结构	线段树、树状数组、并查集、Trie、哈希、平衡树、单调队列、ST 表
图论算法	最短路全家桶、MST、拓扑、欧拉回路、强连通、割点割边、LCA、树上差分
字符串	KMP、Manacher
数学	数论（逆元/CRT/欧拉函数）、组合数学（Catalan/错排/容斥）、线性代数（矩阵）

1. 复杂度分析（S 组最爱）

讲解

• 大 O 基本规则：循环相乘、并列相加、忽略低阶项与常数。
• 递归式与主定理：只适用标准型 \(T(n)=aT(n/b)+f(n)\)（问题切 \(b\) 等份、递归出 \(a\) 个子问题，\(f(n)\) 是非递归开销）。只需把 \(f(n)\) 的多项式次数 \(k\) 与关键数 \(\log_b a\) 比大小：

\(f\) 的次数 \(k\) 与 \(\log_b a\) 相比	情况	结论	例子	最终复杂度
\(k<\log_b a\)	叶子层主导	\(O(n^{\log_b a})\)	\(T(n)=2T(n/2)+O(1)\)	\(O(n)\)
\(k=\log_b a\)	每层打平	\(O(f(n)\log n)\)	\(T(n)=2T(n/2)+O(n)\)	\(O(n\log n)\)
\(k>\log_b a\)	\(f(n)\) 主导	\(O(f(n))\)	\(T(n)=2T(n/2)+O(n^2)\)	\(O(n^2)\)

常见误区：\(\log\) 幂次不算次数差距

\(f(n)=O(n\log n)\) 的次数仍是 \(1\)，与 \(\log_b a\) 打平应按「每层打平」处理：\(T(n)=2T(n/2)+O(n\log n)\) → \(O(n\log^2 n)\)，不是 \(O(n\log n)\)。

• 换元法：\(T(n)=2T(\sqrt n)+\log n\) → 令 \(n=2^k\)，\(S(k)=2S(k/2)+k\) → \(O(k\log k)=O(\log n\cdot\log\log n)\)（SCP2026 考过）。
• 背熟常用复杂度：二分 \(O(\log n)\)、快排/归并 \(O(n\log n)\)、Floyd \(O(n^3)\)、Dijkstra \(O((n+m)\log n)\)、SPFA 最坏 \(O(nm)\)、状压 \(O(n\cdot2^n)\)。
• 双循环计数：外层 i *= 2（\(\log n\) 次）、内层 j /= 2（\(\log n\) 次）→ \(O(\log^2 n)\)（SCP2025 考过）。
• 排序最坏复杂度对照：

算法	最坏复杂度
快速排序	\(O(n^2)\)
归并 / 堆排序	\(O(n\log n)\)
计数排序	\(O(n+k)\)
基数排序	\(O(d\cdot(n+k))\)

例题（CSP-S 2025 原题） 求 \(T(n)=2T(n/2)+O(n^2)\) 的复杂度。

- 解析

比较 \(f(n)=n^2\) 与 \(n^{\log_2 2}=n\)：\(f\) 的次数 \(2>\log_2 2=1\)，合并开销盖过递归 → \(T(n)=O(n^2)\)。

例题（SCP2026 考过） 求 \(T(n)=2T(\sqrt n)+\log n\) 的复杂度。

- 解析

换元：令 \(n=2^k\)，则 \(\sqrt n=2^{k/2}\)，\(T(2^k)=2T(2^{k/2})+k\)。记 \(S(k)=T(2^k)\)，得 \(S(k)=2S(k/2)+k\) → 由主定理 \(O(k\log k)\)。代回 \(k=\log n\)：\(O(\log n\cdot\log\log n)\)。

易错辨析（STL 复杂度陷阱，必考）

• set/map 增删查 \(O(\log n)\)；priority_queue 插入/删除堆顶 \(O(\log n)\)。
• std::lower_bound(s.begin(), s.end(), x) 对 set 是 \(O(n)\)！因为 set 的迭代器是双向迭代器，通用 lower_bound 只能线性扫描；必须用成员函数 s.lower_bound(x) 才是 \(O(\log n)\)（SCP2026 考过）。
• nth_element：\(O(n)\) 求第 k 小，只保证"第 k 个位置正确，左右不有序"（SCP2026 考过）。

使用条件与技巧

• 问 STL 操作复杂度先看迭代器类别：随机访问才支持 \(O(\log n)\) 的算法库函数；set/map 一律用成员函数版本。
• 递归式求复杂度只有三招：画递归树 / 主定理 / 换元。看到 \(\sqrt n\)、\(\log n\) 嵌套先想到换元 \(n=2^k\)。

2. C++ 高级

2.1 编译命令

讲解

• g++ 只编译 .cpp 源文件，头文件 .h 不参与编译（被 #include 引入）。
• 多源文件一起编译链接：g++ grader.cpp scp.cpp -o scp -O2 -std=c++14 -static（SCP2026 考过"交互题编译"）。
• 常用选项：-O2（优化）、-std=c++14（标准）、-static（静态链接）、-Wall（警告）。

易错辨析（GDB 调试，SCP2025 考过）

用 -O2 优化编译后用 gdb 的 print 查看局部变量不一定能看到真实值（变量可能被优化掉或存入寄存器）——既不会崩溃也不会自动重新编译。调试请加 -g（最保险是 -g -O0）。

使用条件与技巧

• 判断题"改了代码不重新编译，gdb 里能直接看到新值"恒为假——gdb 调试的是编译产物，改码必先重编。

2.2 STL 高级

讲解

• set/multiset、map/multimap、deque、priority_queue、bitset、pair/tuple。
• 迭代器分类：随机访问（vector/deque/指针）＞ 双向（list/set/map）＞ 单向（forward_list/unordered_*）。
• bitset：位运算容器，s[i] 取第 i 位，count() 数 1 的个数（大纲 2025 新增）。
• __builtin_popcount(x)：数二进制中 1 的个数。
• 防溢出：1ll * a * b、模 998244353。

常见变形

• 排序/去重三件套 sort + unique + erase 与 lower_bound 配合做离散化——unique 后必须 erase 多余尾巴，lower_bound 才能正确二分。
• 状压 DP 常用 __builtin_popcount 统计已选个数（见 7）。

使用条件与技巧

• deque 两头都能 \(O(1)\) 进出（单调队列用）；vector 只在尾部 \(O(1)\)，头部插入 \(O(n)\)——判断题"vector 头部 push 是 O(1)"为假。

3. 数据结构（S 组核心）

3.1 线性结构（单调队列 / 单调栈 / 后缀表达式 / ST 表）

讲解

• 单调队列：滑动窗口最值，O(n)；单调栈：下一个更大/更小元素。
• 后缀表达式（逆波兰式）求值：遇数字入栈，遇运算符弹出两个操作数、计算后压回。注意含乘方 ^ 时按"右结合"、指数先算（SCP2025 考过 3 4 2 * 1 5 - 2 3 ^ ^ / +）。
• ST 表：\(O(n\log n)\) 预处理、\(O(1)\) 查询区间最值，只支持可重复贡献且不可修改（min/max/gcd 可以，区间和不行）。

例题（SCP2025 考过） 后缀表达式 3 4 2 * 1 5 - 2 3 ^ ^ / + 的求值顺序是怎样的？

- 解析

模拟栈：3 4 2 * → 3 8；1 5 - → -4；遇到 2 3 ^ 先算 \(2^3=8\)（乘方右结合、指数最优先）；下一步 ^ 再算 \((-4)^8\)（注意指数与底数的配对方向），最后才做 ÷ 与 +。逐运算符弹两数、压回一数，别被"同级从左到右"的习惯带偏——乘方是右结合。

易错辨析

• ST 表查询区间和是错的：f[i][j] 两个子区间会重叠，只有"重叠无影响"的运算（min/max/gcd）才行——线段树能求和因为它是精确划分，ST 表是覆盖合并，两者适用域不同。
• 后缀表达式遇数字就压栈、遇双目运算符弹两个——先弹的是右操作数，减法/除法顺序错了符号就反。

常见变形

• 前缀表达式（波兰式）与中缀互转、表达式树求值都是同一模型：中缀转后缀用运算符栈（考虑优先级与括号），后缀求值用数字栈。
• 单调栈经典三问：下一个更大/更小、左右第一个更矮/更高、最大矩形面积——都是"维护单调性 + 出栈时结算"。

使用条件与技巧

• "不可修改 + 只查最值" → ST 表；"要修改" → 线段树/树状数组；"窗口滑动" → 单调队列。先看有没有修改再选结构。

3.2 树结构（线段树 / 树状数组 / Trie / 01-Trie / 并查集 / 平衡树 / 二叉堆）

线段树

讲解

• 区间查询/修改 \(O(\log n)\)，要求运算满足结合律（加法、max、gcd、矩阵乘法都可以；不需要交换律）。
• 区间查询本质是递归分解，访问节点数与区间大小、树高相关。

例题（CSP-S 2025 原题） 16 个元素建线段树，查询区间 3 到 11 最少访问多少个节点？（答案：8）

- 解析

不背答案，理解递归分解过程：根区间 [1,16] 每次对半分裂，只有完全被 [3,11] 覆盖的节点才整块返回，部分覆盖的节点继续下探；两棵子树互不重叠地拼出查询区间，访问节点数 = 递归过程中"触及且必要"的节点个数。能说出"递归分解 + 剪掉无交子树"就够应对变体。

易错辨析

• 线段树对运算的要求只是结合律，不需要可逆也不需要交换律——矩阵乘法可以做区间积。
• 查询的递归写法：完全覆盖直接返回、完全无交直接剪掉、否则下探——三句判断顺序写反会多访问或漏节点。

树状数组

讲解

• 前缀和思想，要求运算可逆（有逆元）：加法（用减法）、异或（自逆）可以；min/max 不行（SCP2026 考过）。

易错辨析

• "树状数组维护区间最值"是经典错误选项——最值不可逆，删不掉旧贡献。判断标准：能不能通过逆运算撤销。
• 单点改 + 区间查用树状数组；区间改 + 区间查要两棵或差分树状数组。

Trie

讲解

• 共享前缀的树；统计节点数要"一个前缀一个节点"地数。

例题（CSP-S 2025 原题） 依次插入 cat, car, cart, case, dog, do，Trie（含根）有多少个节点？

- 解析

按插入顺序数新增节点：cat +3（c,a,t）；car 共享 ca 只 +1（r）；cart 共享 car 只 +1（t 在 r 分支下，与 cat 的 t 不是同一个）；case 共享 ca 只 +2（s,e）；dog +3；do 全共享 +0。累计 \(3+1+1+2+3=10\) 个字符节点，含根共 11。

常见变形

• 问"某字符串是否存在/是否某串前缀"，直接沿 Trie 走到底看标记。
• 01-Trie：处理最大异或对，每层最多 2 个孩子。节点数范围题：第 \(i\) 层节点数 \(\le 2^i\) 且 \(\le\) 上一层两倍（SCP2026：10 个数、深度 5，最多 35、最少 22）。

使用条件与技巧

• 字符集小（26/10）用数组存孩子，字符集大用 map——判断题会问空间开销。

并查集 / 平衡树 / 二叉堆

讲解

• 并查集：路径压缩 + 按秩合并，几乎 O(1)。
• 平衡树（了解）：AVL/Treap/Splay 的旋转思想——本质是"防止 BST 退化"。
• 二叉堆：插入、删除堆顶，均 \(O(\log n)\)。

例题（CSP-S 2025 考过） 对一个小根堆连续做两次"删除最小值"操作，问新堆顶是谁。

- 解析

两次删除后堆顶 = 原堆中第三小的元素。做法：把堆顶弹出、末尾元素补位、向下调整两次，手算时等价于"在原数组里排除两个最小后找最小"。

易错辨析

• 并查集只说"路径压缩"不说"按秩合并"时复杂度才是 \(O(\log n)\) 级别——判断题问最坏复杂度别答 O(1)。

3.3 图（概念辨析）

讲解

• 二分图：无奇环，可用黑白染色判定。
• 欧拉回路：连通 + 所有点度数为偶数；欧拉路径：连通 + 至多 2 个奇度点。
• 补图性质：\(G\) 不连通 ⇒ 补图连通（SCP2026 考过；反之不成立）。
• DAG：存在拓扑序。无向图删除一条边后连通块数可能变化。
• 竞赛图：任意两点之间恰有一条有向边的图。

例题（SCP2025 考过） 竞赛图中出度为 0 的节点最多有几个？

- 解析

最多 1 个。若存在两个节点 \(u,v\) 出度都为 0，则 \(u,v\) 之间的那条有向边无论指向谁，都会给其中一个节点带来出度 1——矛盾。所以出度为 0 的节点至多一个。

易错辨析

• "\(G\) 连通 ⇒ 补图连通"为假（如完全图的补图全是孤立点）；不连通 ⇒ 补图连通才恒真，方向别记反。
• 欧拉路径允许恰好 2 个奇度点（起点/终点），欧拉回路要求全偶——判断题"有欧拉路径必有欧拉回路"为假。

常见变形

• 黑白染色判二分图、度数和判欧拉、拓扑序判 DAG——概念题先把"判定条件"写出来再逐选项套。
• 补图计数：\(n\) 点完全图有 \(C(n,2)\) 条边，补图边数 = \(C(n,2)-m\)，常与度数/连通性合考。

3.4 哈希

讲解

• 哈希函数 + 冲突处理：链地址法、开放地址法（线性探查/二次探查）。
• 线性探查：从哈希位置往后找空位（CSP-S 2025 考过插入位置）。
• 字符串哈希：进制哈希（如 \(h(s)=\sum s_i\cdot base^i \bmod P\)）。

易错辨析

• 开放地址法删除元素不能直接置空（会断掉探查链），要打"已删除"标记——判断题常考。
• 线性探查是向后找空位，到表尾要回绕（mod m），别漏循环。

使用条件与技巧（哈希表大小 m 的选择，SCP2025 考过）

若数据都满足 \(x\equiv c \pmod d\)，而 \(m\) 恰好是 \(d\) 的倍数，哈希值会集中在少数桶。应选与数据周期互质（最好是大质数）的 \(m\)（如 97）让分布更均匀。

3.5 扫描线（大纲 2025 新增，SCP2025 完善程序考过）

讲解

• 适用：矩形并/交面积、矩形包含关系等"二维平面 + 平行坐标轴"问题。
• 套路：把每个矩形拆成"左竖线 + 右竖线"，按 x 排序后从左往右扫；用线段树维护 y 方向区间被覆盖的次数；y 坐标大时先离散化（sort + unique + lower_bound）。
• 识别标志：line 结构体 + sort + 线段树的 update/query + 离散化模板。

使用条件与技巧

这是"模板性极强"的题：背熟"拆竖线 → 排序 → 线段树维护覆盖次数 → 边扫边累加面积"五步即可，不用理解几何证明也能做对完善程序。 左竖线权值 +1、右竖线权值 −1：覆盖次数归零的区间不再贡献面积——填空时盯"是加还是减、累加的是哪段 y 长度"。

4. 图论算法（S 组重点）

最短路全家桶（Dijkstra / SPFA / Bellman-Ford / Floyd）

讲解

算法	条件/用途	复杂度	坑点
Dijkstra	边权非负	\(O((n+m)\log n)\)	有负权会错（SCP2026 考过"无负环也不够"）
SPFA	可负权	最坏 \(O(nm)\)	会被卡，但可判负环
Bellman-Ford	可负权	\(O(nm)\)	第 n 轮仍能松弛 ⇒ 负环
Floyd	任意两点	\(O(n^3)\)	判负环：\(d_{i,i}<0\)；也能求传递闭包

例题（SCP2026 考过） "图中没有负环，所以 Dijkstra 一定能求出最短路"对吗？

- 解析

错。Dijkstra 的贪心前提是"已确定的点不会被更晚的路径改小"，而负边（哪怕无负环）就能让一个已出堆的点被更短路径反超——SCP2026 明确指出"无负环也不够"。负权图必须上 Bellman-Ford/SPFA。

易错辨析

• Dijkstra 适合非负权；Bellman-Ford/SPFA 容忍负权；负环只能被 Bellman-Ford/SPFA/Floyd 检测出来。概念辨析题逐算法对条件。

使用条件与技巧

最短路选择口诀：非负权 → Dijkstra；有负权 → Bellman-Ford/SPFA；求负环 → Bellman-Ford/SPFA；任意两点 → Floyd。SPFA 不是"一定比 Dijkstra 快"，最坏反而更差。

MST（Kruskal / Prim）

讲解

• Kruskal：按边权排序 + 并查集，\(O(m\log m)\)；Prim：加点法，\(O(n^2)\)/堆优化 \(O(m\log n)\)。
• 边权互异 ⇒ MST 唯一。

易错辨析

• "边权互异"是 MST 唯一的充分条件；边权有相同时 MST 可能不唯一，但总权值唯一。

分层图（拆点）最短路

讲解

• 处理"最多免费一条边"类问题：状态 = (节点, 已用免费次数)，在分层图上跑 Dijkstra（CSP-S 2025 完善程序考过）。

常见变形

"最多 k 次免费/优惠/绕行" → 建 \(k+1\) 层图，层间连权值为 0（或代价）的边；答案 = 所有层中目标点的最短路最小值。

拓扑排序 / LCA / 树的直径 / 其他

讲解

• 拓扑排序：入度为 0 的节点入队。DAG 拓扑序数量：最少 1 种，最多 \(n!\) 种（CSP-S 2025 考过"可能是多少"）。
• LCA：倍增/树上差分；性质：若 a 是 b 的祖先，则 \(LCA(a,b)=a\)（CSP-S 2025 考过判断不可能的组合）。
• 树的直径：两次 DFS/BFS；树的重心、树链剖分（了解）。
• 强连通分量（Tarjan）、割点割边（了解）：删边后连通块变化。

鸡蛋硬度问题

讲解

2 个鸡蛋 \(n\) 层楼的最坏最少实验次数（CSP-S 2025 阅读程序）。

- 解析

最优策略是分组跳跃 + 小范围线性：第一颗蛋按 \(w, w-1, w-2, \dots\) 递减的间隔往上跳（保证无论在哪一层碎，第二颗蛋线性扫的步数都不超过 \(w\)）。总覆盖楼层 \(w+(w-1)+\dots+1=w(w+1)/2\)，取 \(\ge n\) 的最小 \(w\)，最坏 \(O(\sqrt n)\) 次。

使用条件与技巧

树的题先定三件套：直径（两次 DFS）、LCA（倍增）、树形 DP（看子树）。删边/删点问连通性变化 → 割边割点/桥。

5. 字符串

KMP

讲解

• next[i] = 前缀 s[1..i] 的最长相等真前后缀长度（真前缀不含自身）。

例题（CSP-S 2025 原题） 手算 abacaba 的 next 数组。

- 解析

逐位找"既在开头、又在末尾的最长段"：a→0，ab→0，aba→1（a），abac→0，abaca→1（a），abacab→2（ab），abacaba→3（aba），得 {0,0,1,0,1,2,3}。

易错辨析

• next 数组的"最长真前后缀"不含自身，next[1]=0。
• 可行性判断题（SCP2026 考过）：若 next[i+1]=k+1，则必须有 next[i] 的链式约束；枚举 \(2^6\) 个小串验证最稳。

常见变形

• 最小循环节：n - next[n]（能整除 n 时）——问"字符串可由多短串重复得到"先写这个式子。
• Manacher（了解）：最长回文子串 \(O(n)\)；实现上通常在每个字符之间和首尾插入特殊分隔符（如 #），把奇偶长度回文统一成奇数长度来处理（SCP2025 考过此描述）。

使用条件与技巧

判断"一个串是否另一个的子串/出现次数"用 KMP；判回文用 Manacher/哈希；多项串公共前缀用哈希二分。

6. 搜索优化

讲解

• 剪枝、记忆化搜索（= 自顶向下 DP）、双向 BFS、迭代加深、启发式搜索（了解）。
• 折半搜索（Meet-in-the-Middle）：把枚举拆成前后两半，各 DFS 枚举 \(m^{n/2}\) 种，排序 + 双指针合并（CSP-S 2025 阅读程序考过"多项式和为零计数"）。

例题（CSP-S 2025 阅读程序） "多项式和为零"的计数为什么用折半而不是全枚举？

- 解析

直接枚举 \(m^n\) 种会爆炸；折半后每半只有 \(m^{n/2}\) 种：枚举左半所有和 → 枚举右半所有和 → 排序后半 → 双指针找互补为零的对。阅读程序里识别标志是"拆两半 + sort + 双指针"，先说出它在做折半搜索再逐问作答。

易错辨析

• 折半搜索的合并阶段要排序 + 双指针/二分统计，不是简单配对——判断题"折半后直接两两比"复杂度仍是 \(O(m^{n/2}\cdot m^{n/2})\)，等于没优化。
• 记忆化搜索与 DP 是同一张表两种填法，判断题"记忆化比 DP 多算状态"为假（都只算每状态一次）。

使用条件与技巧

\(n \le 40\) 左右、每项选择数小 → 折半；状态有大量重复子问题 → 记忆化；知道解在浅层 → 迭代加深；双向都宽 → 双向 BFS。

7. 动态规划（S 组）

讲解

• 多维 DP、树形 DP（树上背包）、区间 DP。
• 状压 DP：\(n\le20\)，\(O(n\cdot2^n)\)；配合 __builtin_popcount、1ll 防溢出。
• 背包进阶：完全背包（正序）、多重背包（二进制拆分）、分组背包。
• DP 优化（了解）：单调队列优化、斜率优化。

例题（SCP2026 考过） \([0,2^n)\) 中所有状态二进制 1 的个数（popcount）之和是多少？

- 解析

每个二进制位在 \(2^n\) 个数中恰有一半为 1：总和 = \(n\times 2^{n-1}\)。不必逐个枚举。

易错辨析

• 状压 DP 循环顺序：先枚举状态、再枚举转移（或先枚举子集）——方向反了会用到"未算完"的状态。
• 完全背包正序枚举容量、0-1 背包倒序，阅读程序改个循环方向就会改变答案（见 J 组篇 4.6）。

使用条件与技巧

\(n\le20\) 且状态是"选了哪些" → 状压；子树合并 → 树形背包（每棵子树当成一组物品）；区间合并取最优 → 区间 DP。DP 优化题的识别标志是转移式里出现 \(\max/\min\) 滑动窗口（单调队列）或斜率式 \(\frac{y_j-y_k}{x_j-x_k}\)（斜率优化）。

8. 数学（S 组比重最大）

8.1 数论

讲解

内容	要点	考点
快速幂	二进制分解指数	模意义下 \(a^b\)，\(O(\log b)\)
模逆元	费马小定理 \(a^{p-2}\bmod p\)（p 为素数）	组合数取模
扩展欧几里得	解 \(ax+by=\gcd(a,b)\)	同余方程
欧拉函数/定理	\(\varphi(n)\)、\(a^{\varphi(m)}\equiv1\)	与 m 互质时
中国剩余定理 CRT	解同余方程组	了解即可
斐波那契周期	mod m 的皮萨诺周期	mod 3 周期 8；\(\begin{bmatrix}1&1\\1&0\end{bmatrix}^n\)

例题（SCP2025 考过） 判断下列模运算恒等式是否成立：\((a+b)\bmod m=(a\bmod m+b)\bmod m\)；\((a/b)\bmod m\stackrel{?}{=}(a\bmod m)/(b\bmod m)\)。

- 解析

• 恒成立：加、减、乘都可以"先取模再运算"（同余性质）；
• 不成立：除法没有直接分配律——模意义下的除法要乘逆元 \(b^{-1}\)；另外 \(a\bmod m=b\bmod m\) 也推不出 \(a=b\)（只差 \(m\) 的整数倍）。

易错辨析

• 模逆元存在的条件是 \(\gcd(b,m)=1\)；\(p\) 为素数时用费马小定理 \(b^{p-2}\)，否则用扩展欧几里得——判断题"任何数都有逆元"为假。
• 斐波那契周期：mod 3 的皮萨诺周期是 8，求 \(F_{2026}\bmod 3\) 之类先 \(2026\bmod 8\) 再查表（SCP2026 考过）。

常见变形

斐波那契矩阵恒等式：\(\begin{bmatrix}1&1\\1&0\end{bmatrix}^n=\begin{bmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{bmatrix}\)——大下标 \(F_n\) 用矩阵快速幂。

8.2 组合数学

容斥原理

讲解

• 三集合"加奇减偶"：奇数次相交加、偶数次相交减。

例题（CSP-S 2025 原题） 1~1000 中不被 2、3、5 整除的数有多少个？

- 解析

\(1000-\left(\lfloor\frac{1000}{2}\rfloor+\lfloor\frac{1000}{3}\rfloor+\lfloor\frac{1000}{5}\rfloor\right)+\left(\lfloor\frac{1000}{6}\rfloor+\lfloor\frac{1000}{10}\rfloor+\lfloor\frac{1000}{15}\rfloor\right)-\lfloor\frac{1000}{30}\rfloor\) \(=1000-(500+333+200)+(166+100+66)-33=266\)。

卡特兰 / 错排 / 圆排列 / 鸽巢 / 二项式

讲解

• 卡特兰数：\(C_n=\frac{1}{n+1}\binom{2n}{n}\)，前几项 1,1,2,5,14,42；应用：合法括号序列、出栈序列、n 个节点二叉树形态数。
• 错排 \(D_n\)：0,1,2,9,44,265（递推 \(D_n=(n-1)(D_{n-1}+D_{n-2})\)）；圆排列：\((n-1)!\)（大纲 2025 新增）。
• 鸽巢原理：\(n+1\) 个东西放 \(n\) 个盒子必有盒子放 ≥2 个。
• 二项式定理、杨辉三角、帕斯卡恒等式 \(C(n,k)=C(n-1,k)+C(n-1,k-1)\)。

常见变形

• 问"二叉树形态数/出栈序列数/括号序列数"认出卡特兰；问"没人坐回原位"认出错排；问"围成一圈"用圆排列——先把题目翻译成标准模型再套数。

插空法 / 捆绑法

讲解

• 不相邻 → 插空；必须相邻 → 捆绑成一组再排。

例题（CSP-S 2025 原题） 5 红 5 蓝排成一排、蓝球不相邻，有多少种排法？

- 解析

先排 5 个红球（只 1 种，同色不区分），红球形成 6 个空位（含两端），在 6 个空里选 5 个放蓝球 → \(C(6,5)=6\)。

使用条件与技巧

多重集排列组合（了解即可）：含重复元素的排列数 \(=\dfrac{n!}{\prod n_i!}\)。

8.3 线性代数

讲解

• 矩阵运算：加法、乘法、转置；矩阵快速幂（配合斐波那契等递推加速）。
• 高斯消元 / 异或方程组（SCP2025 考过）。

例题（SCP2025 考过） \(n\) 个未知数、系数矩阵秩为 \(r\) 的异或方程组，解的个数是多少？

- 解析

自由元 \(=n-r\)，每个自由元可取 0/1 → 解的个数 \(=2^{n-r}\)。异或方程组的高斯消元只需做按位消元（行与行异或），比实数消元更简单。

易错辨析

• "秩 = 未知数个数"才有唯一解；\(r<n\) 时无穷多解，个数要数自由元而不是直接说"无数个"（异或域里是有限个 \(2^{n-r}\)）。
• 消元过程某列全 0 意味着该列对应自由元——数秩时逐列检查。

9. 阅读程序与完善程序应试技巧（S 组加强版）

阅读程序

1. S 组阅读题常是"算法题伪装成代码"：先翻译代码语义（求什么？什么算法？），再答题。
2. 判断题用边界值/特殊值验证；"输出是多少"先手算小样例。
3. 复杂度判断题（\(O(\cdot)\) 量级）：看循环层数、递归展开、每个操作的复杂度。
4. 代码修改题：盯循环边界、比较符号、是否 1ll、初始值。
5. 多选（4 分）：逐项排除，注意"必然/可能"字眼。
6. SCP2025 三篇阅读分别是：类筛法标记 + 乘积取模、快速幂 + 拉格朗日插值（自然数幂和）、Trie + 树上多项式 DP——先识别"它算的是什么"再逐问分析，最后一问（4 分）常问"这段代码等价于求什么"。

易错辨析

• 空栈/空队列 top()/front() 是 UB；数组越界、1<<31 都是常见陷阱。
• 删掉 1ll* 会因 int 溢出改变结果（SCP2026 考过）。
• next 数组的"最长真前后缀"不含自身，next[1]=0。

完善程序

1. 先通读全程序，识别算法模板：Dijkstra / KMP / 线段树 / 二分 / DP / 线性筛。
2. 填空时结合变量名、注释、循环范围；注意边界（l<r vs l<=r、u.k<k vs u.k<=k）。
3. 关注"防溢出/取模/类型"的空（1ll*、%mod、l+(r-l)/2）。

经验

完善程序第 1 题通常考经典算法（二分、BFS、Dijkstra、线性筛），第 2 题考相对新颖的题（分层图、信息论编码、Top Tree）。把经典模板背熟，第 1 题几乎全对。 SCP2025 的两题分别是树的重心（链式前向星 + DFS 维护 siz 与 max_part）和矩形覆盖（扫描线 + 线段树 + 离散化）——都属于"模板性很强"的题，练熟即可拿满分。

10. 考前速查：S 组高频考点清单

考点	怎么考	记忆要点
主定理	递归式求复杂度	比较 \(f\) 的次数与 \(\log_b a\)，\(\log\) 幂次不算差距
STL 复杂度	set 的 lower_bound	成员函数 O(log n)，迭代器版 O(n)
线段树	区间查询节点数	递归分解理解
Trie	节点数	一个前缀一个节点
哈希	线性探查位置	冲突往后找
最短路	算法特性辨析	Dijkstra 非负权；Floyd 判负环
分层图	免费边最短路	状态拆点
拓扑排序	结果数、入度	1 到 \(n!\) 不等
容斥	三集合整除	加奇减偶
卡特兰/错排	计数	前几项背诵
KMP	手算 next	最长相等真前后缀
折半搜索	指数级优化	拆两半排序合并
鸡蛋硬度	分组跳跃	\(w(w+1)/2\ge n\)，\(O(\sqrt n)\)
状压 DP	popcount、复杂度	\(n\cdot2^{n-1}\)
斐波那契周期	矩阵 / mod	周期表 + 矩阵恒等式
树状数组	运算性质	需可逆（min 不行）
竞赛图	出度为 0 节点数	最多 1 个
后缀表达式	含乘方求值	栈模拟；^ 右结合
模运算	恒等式判断	除法不能直接拆
哈希表大小	m 的选择	与数据周期互质
扫描线	矩形覆盖 / 面积	拆竖线 + 线段树 + 离散化
异或方程组	解的数量	\(2^{n-r}\)（自由元）
GDB	-O2 下 print	变量可能不可见
排序复杂度	最坏对照	快排 \(O(n^2)\)
拉格朗日插值	自然数幂和	多项式插值模板（了解）

11. 经验之谈

1. S 组初赛 = J 组全部 + 提高知识：J 组的基础（进制、二叉树、排序、DP 入门）不扎实，S 组会连错；先把 J 组指南 过一遍。
2. 数学是区分度：排列组合、容斥、数论、Catalan 必须能手算，且要会"构造验证"（枚举小数据）。
3. 概念辨析题逐项排除：S 组单选很多是"下列说法正确的是"，把每个选项当判断题。
4. 阅读程序拿分策略：先易后难；最后一题多选即使拿不准也要蒙上最可能的。
5. 错题本记"为什么想错"：例如把 set 的 lower_bound 当成 O(log n)、把负权图用 Dijkstra。
6. 模拟赛偏难不必焦虑：SCP2026-S1 明确标注"难度高于 CSP-S 初赛"，用它补知识点覆盖，别用分数自我打击。
7. 会写小脚本验证：KMP next 可行性、计数类题目，考场上心算小样例是最可靠的验证方式。
8. 多选题与"等价于求什么"题别猜得太快：SCP2025 阅读最后一问常给四个"文字描述"，先把代码里循环/递推的数学含义翻译出来再对照选项。
9. 优化陷阱题 = 保分题：-O2 下 GDB print、set 的 lower_bound、删掉 1ll、双重循环算复杂度——这类"考你会不会踩坑"的题记住结论就是送分。

参考链接

• NOI 大纲（2025 年修订版）
• CSP-S 2025 真题与解析（CSDN）
• 本站：普及组 Junior 第一轮通关指南