原题库负责让你认出一个方法；这篇配套笔记负责逼你在换了尺寸、边界、随机机制和目标函数之后，仍然能把方法重新搭出来。重点从第8题的有限随机游走和第7题的曲线分割开始，扩展到随机排列、几何概率、递推、最优停止、统计金融、随机矩阵、公平性、记录值、局部游程和比较下界十五组高频迁移题。
原题库中的第8题问：5×5网格中心的蚂蚁每次向四个方向等概率走，进入边界后停止，平均走多少步。真正值得带走的不是答案 \(9/2\)，而是第一步递推 \(E(s)=1+\mathbb{E}[E(s')]\)，以及“旋转、镜像后行为相同的位置可以归为同一类”这一压缩原则。25个位置并不需要写25个未知数；在对称性足够强时，中心、轴向相邻点和斜向相邻点已经能描述全部内部状态。
第7题问6个矩形最多把平面分成多少块。它的关键也不是记住122，而是观察到：加入第 \(k\) 个对象时，新对象的边界被旧对象切成若干段，每一段穿过一个旧区域并增加一个新区域。于是区域数满足“旧区域数 + 新边界段数”的递推。换成直线、圆、椭圆或圆盘内的弦，只要重新数清一对对象最多产生多少个互异交点，就能得到同一类答案。
下面的61道题是围绕原题库方法设计的教学变体，不冒充小红书原帖真题。每组先给一个最小模型，再改变尺寸、目标或边界；你要练的是识别“状态空间、单步增量、指标事件或不变量”发生了什么，而不是背下一组数字。
先写“走一步”，再给吸收态设值0；尺寸改变时，变的是状态图，不是建模句式。
不要从总区域数猜公式，先问新加入的边界被切成多少段；交点数才是递推的燃料。
把总量写成0/1指标之和，相关性通常不妨碍求期望；但它会影响方差和分布。
有限状态用递推，非负整数用尾和；别把“第一次发生”误当成一次独立试验。
先找奇偶、模数、染色或对称策略，再谈构造；“试几步没成功”不是证明。
建议每道题先遮住“答案”部分，给自己60–90秒写出状态、递推或不变量。做完后不要只核数字，还要回答最后一行的“迁移点”和“边界”。
| 方法簇 | 练习题数 | 你要输出的第一句话 | 对应原题 |
|---|---|---|---|
| 吸收随机游走 | 5 | “我先定义到达吸收边界前的期望步数。” | 第8、13、23、53题 |
| 曲线/弦分割 | 4 | “我先数新对象的边界段，而不是直接数总块数。” | 第7、17、35、36题 |
| 指标变量与线性期望 | 4 | “我把总量写成局部事件的指标和。” | 第12、41、50题 |
| 停止时间与尾和 | 4 | “我先写停止事件的尾概率，或定义当前部分匹配状态。” | 第10、24、40、46题 |
| 不变量与模运算 | 4 | “我先找每一步都不能改变的量。” | 第31、49、51、52题 |
| 随机排列与条件概率 | 4 | “我先说明样本空间和信息是怎样产生的。” | 第3、9、11、18、29、43题 |
| 几何概率与布朗过程 | 4 | “我先把连续事件改写成边界或面积问题。” | 第5、15、23、25、28、33题 |
| 递推、生成函数与数论 | 5 | “我按最后一步、最后一位或模数拆分。” | 第6、17、30、35、36、38、48、49题 |
| 最优停止、更新与重置 | 4 | “我比较立即收益和继续价值。” | 第10、20、24、37、39、42题 |
| 统计、相关性与金融机制 | 4 | “我先检查整体约束，再合并条件指标。” | 第4、21、26、44、45题 |
| 称量、信息与比较下界 | 4 | “我先算一次操作能提供多少有效信息。” | 第19、27、54题 |
| 随机矩阵与公平性 | 4 | “我先找交换对称，或检查交叉项是否消失。” | 第16、21、22、32题 |
| 记录值、首次出现与游程 | 4 | “我只看顺序或局部转移，不记住全部历史。” | 第9、29、46、50题 |
| 经典构造与增长 | 4 | “我先找一步能产生什么，再写递推或构造。” | 第14、17、35、38题 |
| 局部访问与游程计数 | 3 | “我先算一次局部机会，再用指标或回返概率相加。” | 第13、39、46、47题 |
对内部状态 \(s\)，若每一步走到 \(s'\) 的概率是 \(p(s,s')\)，到达边界后立即停止，可以写成 \(E(s)=1+\sum_{s'}p(s,s')E(s')\)，并令吸收状态的期望为0。压缩不是“看起来对称就合并”，而是要确认合并后的两个位置拥有相同的转移概率结构。
完整题面：在4×4方格中，位于中间2×2的任意一个格子。每次等概率向上、下、左、右移动一格；一旦进入外圈边界格就停止。平均需要多少步？
答案：\(2\)步。
4×4网格只有中间2×2的格子不是边界。无论从哪一个中心格出发，都有两个方向直接进入边界，另外两个方向进入同类的中心格。设期望步数为 \(e\)，则
整理得 \(e=2\)。这里的“1”是本次移动已经消耗的一步；边界方向的后续期望是0。
迁移点：状态压缩首先看转移结构，不是看坐标数量。一个状态也可以包含多个物理位置，只要它们在问题中完全等价。
边界：如果题目改成“走出网格外才停止”，外圈格不再是吸收态，中心格也不再只有一个方程，答案会改变。
完整题面：在3×5方格中，行列从1开始编号；边界格满足行号为1或3，或列号为1或5。蚂蚁从中心格 \((2,3)\) 出发，每次等概率向四个方向走一格，进入边界格即停止。求平均步数。
答案：\(\frac{12}{7}\)步。
内部格只有 \((2,2),(2,3),(2,4)\)。设中心格的期望为 \(x\)，左右两侧内部格的期望为 \(y\)。从中心出发，左右走到两侧，向上向下直接停：
从任意一侧内部格出发，只有朝中心的方向会继续，另外三个方向进入边界：
联立得 \(x=1+\frac12(1+\frac{x}{4})\)，所以 \(\frac78x=\frac32\)，最终 \(x=\frac{12}{7}\)。
迁移点：矩形不必有中心对称的完整二维状态；先按行列边界把内部转移图画出来，很多题会退化成一条短链。
边界：如果“边界”指网格外的围栏，而不是边界格本身，中心到边侧的状态数会增加，不能沿用这两个方程。
完整题面：在5×5方格中，边界格进入即停止。蚂蚁从内部斜向格 \((2,2)\) 出发，每次等概率向四个方向走一格。求平均步数。
答案：\(\frac{11}{4}\)步。
定义 \(x\) 为中心格 \((3,3)\) 的期望，\(y\) 为轴向内部格（如 \((2,3)\)）的期望，\(z\) 为斜向内部格（如 \((2,2)\)）的期望。三类方程分别是
第一式来自中心四步都走到轴向格；第二式中有一个方向到中心、两个方向到斜向格、一个方向出界；第三式中两个方向出界、两个方向到轴向格。解得 \(y=\frac72\)、\(z=1+\frac12\cdot\frac72=\frac{11}{4}\)。
迁移点：“对称性压缩”应当写成轨道：中心、轴向、斜向分别是旋转/镜像作用下的等价类。这样不容易漏掉某个方向的转移。
边界：若把边界改成“走出5×5区域才停”，原来的两个“0”会变成新的边界外邻居状态，不能只改答案不改方程。
完整题面：状态在 \(0,1,\ldots,10\) 之间。到达0或10就停止；在内部状态每次以相同概率加1或减1。从状态3出发，平均需要多少步停止？
答案：\(3(10-3)=21\)步。
设 \(E_i\) 是从 \(i\) 出发的期望步数。内部满足
这说明二阶差分为常数，解是二次函数 \(E_i=i(10-i)\)。代入 \(i=3\) 得21。也可以把它看成最简单的“边界条件决定二次势函数”问题。
迁移点：网格题的核心是离散拉普拉斯方程；一维版本先练熟，再回到二维状态压缩，能更快检查方程是否合理。
边界：这是公平随机游走；若向右概率不是 \(\frac12\)，期望不再是 \(i(N-i)\)，要重新解非对称递推。
完整题面：环上有 \(n\ge3\) 个点，蚂蚁从任意一点出发，每次等概率走向相邻点。求第一次访问过全部点的平均步数。
答案：\(\frac{n(n-1)}2\)步。
访问过的点不会散成几个孤岛，而是连续的一段。假设当前已经访问 \(k\) 个点，且刚刚扩张到这段弧的一个端点。把两侧第一个未访问点当成吸收边界，当前位置到左边界距离为1、到右边界距离为 \(k\)。一维赌徒破产的退出时间期望是两段距离的乘积，所以扩张到下一个新点平均需要 \(k\) 步。
从1个已访问点扩张到2个点花1步，从2个扩张到3个花2步，直到从 \(n-1\) 个扩张到 \(n\) 个花 \(n-1\) 步。因此总期望为
迁移点：不要把“每个点首次出现”当成独立等待；环结构使未访问区域始终只剩两个端口，连续弧才是最小状态。
边界：如果在环上加入“传送边”或允许一次跳到任意点，访问集合不再是连续弧，原递推失效。
加入一个新对象时，如果它的边界被切成 \(m\) 段，并且每段都穿过一个不同的旧区域，那么区域数增加 \(m\)。关键是确认交点互异、没有相切和多条曲线共点；否则“交点数=新增段数”的计数会重复。
完整题面：在平面上画8条直线，要求任意两条相交、任意三条不共点。最多能得到多少个区域？
答案：\(37\)块。
第 \(k\) 条直线与之前的 \(k-1\) 条直线产生 \(k-1\) 个互异交点，被切成 \(k\) 段；每段把一个已有区域切成两个，所以增加 \(k\) 个区域。初始平面是1块：
迁移点：“第 \(k\) 个对象贡献 \(k\)”来自开放曲线与前面对象的交点数；不要把它误套给闭合曲线。
边界：若三条直线共点，该点会同时承担多个交点，新增段数少于 \(k\)，37只是上界而非实际必然值。
完整题面：在平面上画5个圆，要求任意两个圆相交于两个不同点，所有交点互不重合且没有相切。最多能把平面分成多少个区域？
答案：\(22\)块。
第一个圆把平面分成2块。第 \(k\) 个圆与前面每个圆产生2个交点，因此边界有 \(2(k-1)\) 段，增加同样多的区域：
一般地，若每对闭合曲线最多产生 \(c\) 个互异交点，则 \(R_n=2+c\frac{n(n-1)}2\)。圆对应 \(c=2\)。
迁移点：先辨认对象是开放边界还是闭合边界；闭合曲线的第一条已经产生一个内部和一个外部区域。
边界：两个圆不相交、相切或多个交点重合，都会让实际区域数低于22；“最多”依赖一般位置条件。
完整题面：在平面上画3个椭圆，要求任意两个椭圆最多交于4个不同点，且不存在三曲线共点。最多能得到多少个区域？
答案：\(14\)块。
第一个椭圆得到2块；第二个最多与第一个交4点，增加4块；第三个最多与前两个各交4点，共8个互异交点，增加8块：
写成通式就是 \(R_n=2+4\frac{n(n-1)}2=2n^2-2n+2\)。这正是“每对闭合曲线的交点上限”驱动的二次增长。
迁移点：看到新几何对象时，先找“一对对象最多有几个交点”，而不是先找该对象的面积、长度或方程。
边界：任意两个一般椭圆并不必然相交4次；题目问最大值，所以必须说明可以把每一对交点安排成互异位置。
完整题面：在一个圆盘内部画6条弦，要求任意两条弦在内部最多相交一次、任意三条弦不共点、端点全部不同。最多能把圆盘分成多少个区域？
答案：\(22\)块。
第 \(k\) 条弦最多与前面 \(k-1\) 条弦各交一次，被切成 \(k\) 段，因此增加 \(k\) 个区域。圆盘开始只有1块：
它和8条直线的数字公式相同，但原因要重新说：直线的两端延伸到无穷远，弦的两端落在圆周；两者都属于“开放对象，每个新交点多切一段”的计数。
迁移点：相同答案不代表相同模型；面试中要交代初始区域和新对象的边界类型。
边界：若允许三条弦共点，多个交点只切出较少段；若弦端点重合，还要单独处理圆周上的顶点。
若总量可以写成 \(X=\sum_i I_i\)，其中 \(I_i\) 只取0或1，那么 \(\mathbb E[X]=\sum_i\mathbb E[I_i]\)。这一步不要求 \(I_i\) 相互独立；独立性通常是在求方差、分布或联合事件时才变得重要。
完整题面：一枚公平六面骰子独立投掷10次。平均会出现多少个不同的点数？
答案：\(6\left[1-\left(\frac56\right)^{10}\right]\approx5.031\)。
对每个面 \(j\) 定义 \(I_j=1\) 表示它至少出现过一次。某个面10次都没出现的概率是 \((5/6)^{10}\)，因此 \(\mathbb E[I_j]=1-(5/6)^{10}\)。六个面相加得到答案。
迁移点：“不同种类的数量”通常按种类建指标；不要先枚举所有投掷序列。
边界：若骰子有偏、每次概率变化或投掷之间相关，只需把单个面未出现的概率改掉；若要求不同面数量的方差，不能只用期望线性性。
完整题面：10个有标签的球独立、等概率放入4个有标签的盒子。定义一对球“碰撞”为它们落在同一个盒子。平均有多少对碰撞？
答案：\(\binom{10}{2}\frac14=\frac{45}{4}=11.25\)对。
对每一对球 \(\{i,j\}\) 定义 \(I_{ij}=1\) 表示同盒。由于第二个球与第一个球同盒的概率是 \(1/4\)，所以 \(\mathbb E[I_{ij}]=1/4\)。共有 \(\binom{10}{2}\) 对，直接相加即可。
迁移点：同一个盒子里有3个球时会贡献3对、4个球时会贡献6对；指标变量会自动把这些组合数算进去。
边界：若问题改成“有多少个盒子非空”，指标对象应改为盒子；若改成“至少有一对碰撞的概率”，不能用期望答案代替概率。
完整题面：把 \(1,2,\ldots,n\) 随机排列。逆序对是满足 \(i\lt j\) 但排列中 \(i\) 出现在 \(j\) 后面的数对。平均有多少个逆序对？
答案：\(\frac{n(n-1)}4\)。例如 \(n=8\) 时是14个。
固定数值对 \(\{i,j\}\)。在随机排列中，\(i\) 在 \(j\) 前和在 \(j\) 后等可能，因此该对成为逆序对的概率是 \(1/2\)。共有 \(\binom n2\) 对，故期望为 \(\binom n2/2\)。
迁移点：“两两关系的总数”优先考虑 pairwise indicator；这和生日配对、同盒碰撞是同一个拆法。
边界：若问逆序对的方差或尾概率，各球对指标并不独立，需要进一步处理协方差或使用更强的分布工具。
完整题面：在随机图 \(G(20,0.2)\) 中，每条边独立地以概率0.2出现。图中三角形的期望数量是多少？
答案：\(\binom{20}{3}(0.2)^3=9.12\)个。
任意固定的3个顶点形成三角形，需要3条边都出现，概率为 \(0.2^3\)。共有 \(\binom{20}{3}\) 个顶点三元组，所以直接相加得到9.12。
迁移点：不同三角形会共享边，指标之间确实相关；但求期望只需要逐个算“这个三元组成为三角形的概率”。
边界：若边的出现概率依赖于顶点、度数或社区，不能把每个三元组统一写成 \(p^3\)，要按三元组分别计算。
对非负整数值的停止时间 \(T\)，尾和公式是 \(\mathbb E[T]=\sum_{k\ge0}\Pr(T>k)\)。如果过程包含“已经匹配了多少个模式前缀”这样的局部记忆，则把状态写成递推往往更快。两种方法都在做同一件事：把无限的未来压缩成可计算的当前信息。
完整题面：反复投掷公平六面骰子，直到1–6每个点数都至少出现一次。平均需要投多少次？
答案：\(6H_6=6\left(1+\frac12+\cdots+\frac16\right)=\frac{147}{10}=14.7\)次。
已经收集 \(k\) 个不同面时，下一次收集新面的概率为 \((6-k)/6\)，等待新面的期望为 \(6/(6-k)\)。从0个到1个需要1次，再把 \(k=1,\ldots,5\) 的等待期望相加：
迁移点：“全部收集到”常常拆成多个阶段等待；每一阶段是几何等待，但各阶段的成功概率会变化。
边界：若问收集到至少 \(r\) 个不同面，最后的阶段数和求和上限改变；若各面概率不等，不能直接用 \(6H_6\)。
完整题面：反复投掷公平硬币，直到第一次出现连续4次正面。平均需要投多少次？
答案：\(2^{5}-2=30\)次。
设 \(E_i\) 表示当前末尾已有 \(i\) 个连续正面时，距离完成还需要的期望投掷数，\(i=0,1,2,3\)，并令 \(E_4=0\)。每个状态下一次反面回到 \(E_0\)，正面进入下一个状态：
从 \(i=3\) 向前展开，或使用一般结果，可得 \(E_0=2^{r+1}-2\) 在 \(r=4\) 时为30。这里不能把每4次投掷当成互不重叠的一组，因为模式可能跨组重叠。
迁移点：连续模式题只需保留“当前后缀与目标前缀的最长匹配长度”，不需要记住整段历史。
边界：改成出现“HTH”后，状态不再只是连续正面长度，必须保留部分匹配信息；不能机械套 \(2^{r+1}-2\)。
完整题面：反复投掷公平硬币，直到连续结果中第一次出现子串“HTH”。平均需要投多少次？
答案：\(10\)次。
设 \(E_0\) 为没有匹配到模式前缀，\(E_1\) 为末尾是H，\(E_2\) 为末尾是HT；出现HTH后停止。逐状态写递推：
第一式给出 \(E_0=2+E_1\)，第二式给出 \(E_1=2+E_2\)，代入第三式后得到 \(E_0=5+\frac12E_0\)，所以 \(E_0=10\)。
迁移点：HTH中的首尾H可以重叠；模式匹配状态必须保留这种“部分成功后不一定归零”的结构。
边界：若硬币不公平，把每个分支的 \(\frac12\) 换成真实概率即可，但状态转移结构仍然保留。
完整题面：反复投掷公平六面骰子，令 \(T\) 为第一次投出一个此前出现过的点数的投掷编号。求 \(\mathbb E[T]\)。
答案：\(\frac{1223}{324}\approx3.7747\)次。
事件 \(T>k\) 表示前 \(k\) 次全部不同。于是对 \(0\le k\le6\)，
逐项相加为 \(1+1+\frac56+\frac59+\frac5{18}+\frac5{54}+\frac5{324}=\frac{1223}{324}\)。尾和的好处是只需算“还没有停止”，而不必单独计算第一次重复发生在第2、3、…、7次的概率。
迁移点：只要停止事件是“前缀一直保持某种性质”，就优先检查 \(\Pr(T>k)\) 是否容易写出。
边界：如果要求某个指定面重复两次，或要求连续两次相同，尾事件会完全不同，不能复用这个乘积。
不变量可以是奇偶性、模 \(m\) 余数、棋盘染色，也可以是“两个子游戏始终保持相同”的对称策略。它的作用不是快速试出一个答案，而是把所有可能状态分成互不相通的类别。
完整题面：桌上有100颗石子，两人轮流取走1、2或3颗，取走最后一颗的人获胜。在双方最优时谁必胜？
答案：后手必胜。
100是4的倍数。先手取 \(k\in\{1,2,3\}\) 颗后，后手取 \(4-k\) 颗，使两人一轮合计取4颗。每次后手操作结束时，剩余石子仍是4的倍数，最终由先手面对4颗、后手拿走先手取后剩下的数量，后手取到最后一颗。
迁移点：“取1–3颗”不是要枚举100个局面，而是寻找回复策略 \(k\mapsto4-k\)。
边界：如果改成取1、3或4颗，模4的策略不再自动成立；需要重新找周期或计算P-position。
完整题面：8×8国际象棋棋盘去掉两个同色的角格，剩下的62个格子能否用31块1×2多米诺骨牌完全覆盖？每块骨牌只能覆盖共享一条边的两个格子。
答案：不能。
棋盘黑白相间，每块多米诺必定覆盖一个黑格和一个白格。8×8棋盘原本各有32格；两个角格同色，删掉后黑白格数变成30与32，不相等。31块骨牌最多只能同时覆盖31个黑格和31个白格，所以不可能完全覆盖。
迁移点：遇到铺砖题先染色；一个局部操作覆盖的颜色配额，往往比几何形状更快锁定可行性。
边界：若去掉的是一黑一白两个角，颜色计数不再阻止铺法，但“可能”仍需给出实际构造，不能把必要条件当充分条件。
完整题面：国际象棋棋盘上，一只马从黑格出发。它能否经过恰好7步回到某个黑格？
答案：不能。
把格子颜色看作 \((行号+列号)\bmod2\)。马的位移是一个方向走2格、另一个方向走1格，所以行列坐标之和改变奇数，颜色必然翻转。走7步是奇数次翻转，终点一定是白格，不可能落在黑格。
迁移点：棋盘移动题先把几何动作翻译成坐标模2变化；颜色只是模2不变量的可视化表达。
边界：“回到某个黑格”不等于“回到出发格”；本题只用颜色就能否定前者，若要求具体回到出发格，还需要额外的可达性分析。
完整题面：有两堆石子，初始分别为10和10。两人轮流从一堆中取走任意正数，取走最后一颗石子的人获胜。在最优策略下谁必胜？
答案：后手必胜。
后手采用镜像策略：先手从一堆取走 \(r\) 颗，后手就从另一堆取走 \(r\) 颗。每轮后两堆仍相等；当先手把一堆取空时，后手能把另一堆取空并拿到最后一颗。这里的不变量不是一个数字余数，而是状态的对称关系 \((a,a)\)。
迁移点：有些“不变量题”最自然的表达是配对回复，而不是模运算；先找能把对手动作复制回去的结构。
边界：若两堆初始不相等，或每次只能取固定数量，镜像策略可能失效；需要先判断初始状态是否属于对称的必败类。
排列题的陷阱经常不在算术，而在“随机的对象是什么”。是固定一个人看位置，还是随机选一个家庭再获得一句描述？是看无序位置集合，还是把旋转后的圆桌排列视为同一个？先把样本空间和信息生成机制固定，后面的对称性才有意义。
完整题面：20个人等概率围坐圆桌，旋转视为同一种座次。指定的A、B两人相邻的概率是多少？
答案：\(\frac{2}{19}\)。
先把A固定在一个位置，剩下19个位置给B和其他人。A两侧只有2个位置能让B相邻，因此概率是 \(2/19\)。是否把旋转视为同一座次不影响结果，因为分子分母都会同时除以旋转对称的数量。
迁移点：圆排列常可先固定一个参照物，再把问题变成线性位置计数。
边界：如果问A、B、C三人全部连续，或要求A和B不相邻，不能只把2换成一个直觉上的比例，要重新数位置或用补集。
完整题面：把10张卡随机排列，其中3张是标记卡。令 \(M\) 为最晚出现的标记卡所在位置，求 \(\mathbb E[M]\)。
答案：\(\frac{3(10+1)}{3+1}=\frac{33}{4}=8.25\)。
3张标记卡把未标记的7张卡分成最前、两张标记卡之间以及最后共4个间隔。随机位置的对称性使4个间隔中的未标记卡期望都为 \(7/4\)。最晚标记卡后面的未标记卡期望为 \(7/4\)，所以
一般地，\(r\)张标记卡放在 \(n\)个位置时，最晚位置期望为 \(r(n+1)/(r+1)\)。
迁移点：随机位置的极值通常转化成“极值后还有多少空位”；间隔对称比直接列最大位置分布更短。
边界：如果卡片不是随机排列，或标记卡之间有相关的生成规则，间隔不再等分，不能直接套这个公式。
完整题面：假设一周只有5个等可能出生日。一个家庭有两个孩子，性别和出生日独立；随机选一个家庭后得知“至少有一个孩子是星期一出生的男孩”。另一个孩子也是男孩的概率是多少？
答案：\(\frac{9}{19}\)。
每个孩子有 \(2\times5=10\) 种“性别×日期”类型。两个孩子的有序类型共有 \(10^2\) 种；至少一个是“周一男孩”的家庭有 \(10^2-9^2=19\) 种。若两个孩子都是男孩，则每个孩子有5种男孩日期，其中至少一个周一的有 \(5^2-4^2=9\) 种，所以答案是9/19。
迁移点：条件概率的计算单位是“满足信息的样本”，不是所有家庭；先写出信息排除了哪些情况。
边界：如果是先随机指定一个孩子，再告诉你这个孩子是周一男孩，另一个孩子仍有1/2概率是男孩。信息是怎样产生的，会改变答案。
完整题面：独立、等概率地从集合 \(\{1,2,3,4,5\}\) 的所有子集中选出有序的三个子集 \(A,B,C\)。求 \(A\subseteq B\subseteq C\) 的概率。
答案：\(\left(\frac12\right)^5=\frac1{32}\)。
对任意一个元素，它在 \((A,B,C)\) 中的出现模式共有8种等可能情况。要满足包含链，出现位必须从0到1单调变化，只允许 \(000,001,011,111\) 四种，因此单个元素成功概率为1/2。5个元素独立，答案为 \(2^{-5}=1/32\)。
迁移点：集合包含关系可以逐元素拆成位模式；这和二进制、染色以及模2不变量共享同一层结构。
边界：若选出的子集不是独立均匀，或只要求存在某种排列顺序使其成为链，样本空间会改变，不能继续用4/8。
连续概率题不一定要做复杂积分。先找几何对称性、半圆事件或调和边界条件，常常能把“面积/路径”问题压成一条比例关系。对于布朗运动，击中哪个边界和多久离开区间是两类不同的量，分别对应一次函数和二次函数。
完整题面：标准一维布朗运动从 \(x=3\) 出发，直到第一次到达0或10时停止。先到达10的概率是多少？
答案：\(\frac{3}{10}\)。
设 \(p(x)\) 是从x出发先到10的概率。布朗运动的局部平均性质给出 \(p''(x)=0\)，边界条件是 \(p(0)=0,p(10)=1\)，所以 \(p(x)=x/10\)。代入 \(x=3\) 得3/10。
迁移点：“先到哪个边界”先猜一次函数，再用边界值确定；离散随机游走也有同样的调和结构。
边界：如果向右有漂移，或边界不是0和10，线性比例需要改成带漂移的解；不能只看初始位置占区间的比例。
完整题面：标准布朗运动从0出发，令 \(T\) 为第一次到达 \(-2\) 或2的时间。求 \(\mathbb E[T]\)。
答案：\(2^2=4\)。
设 \(u(x)\) 是从x出发的平均退出时间，则 \(u''(x)=-2\)，并且 \(u(-2)=u(2)=0\)。由对称性 \(u(x)=4-x^2\)，所以 \(u(0)=4\)。
迁移点：同一条边界问题里，击中概率是一次函数，退出时间是二次函数；先判断要算哪一种量。
边界：如果问的是先到+2的概率，答案是1/2而不是4；“概率”和“时间”对应不同边界方程。
完整题面：在一个圆周上独立、均匀地取3个点，连接成三角形。圆心位于三角形内部的概率是多少？
答案：\(\frac14\)。
圆心不在三角形内部，当且仅当3个点全部落在某个半圆内。固定其中一个点作为半圆的起点；它成为包含全部其他点的最早点的对称计数给出概率 \(3/2^2=3/4\)。因此圆心在三角形内部的概率是 \(1-3/4=1/4\)。
迁移点：圆周几何先把“圆心是否在凸包内”改写成“是否存在半圆覆盖所有点”。
边界：若取点的分布不均匀，半圆覆盖概率不再是简单的3/4；若问三角形是否锐角，还要明确它与圆心位置之间的几何等价条件。
完整题面：独立、均匀地从区间[0,1]取两个点 \(U,V\)。求 \(\mathbb E[|U-V|]\)。
答案：\(\frac13\)。
在 \((u,v)\) 单位正方形上，\(|u-v|\) 关于对角线对称。于是
迁移点：两个独立连续变量的函数期望可以转成几何区域积分；先利用交换对称性减半区域。
边界：若点来自圆周、正方形或高维球，距离函数和积分区域都改变，不能把1/3当作“随机距离”的通用答案。
计数题看起来会指数爆炸，但最后一步往往只有有限种可能。把对象按最后一个动作分类，就得到递推；把整数按位权或模数分类，就得到更短的计数。关键是写清初值，以及递推覆盖的对象是否互斥且完备。
完整题面：长度为8的二进制字符串中，不允许出现连续的两个1。一共有多少个？
答案：\(55\)个。
设 \(T_n\) 为长度n的合法串数量。最后一位是0时，前面可以是任意合法串；最后一位是1时，前一位必须是0，前面相当于长度 \(n-2\) 的合法串。因此 \(T_n=T_{n-1}+T_{n-2}\)，初值 \(T_0=1,T_1=2\)。依次计算得 \(T_8=55\)，也就是斐波那契数 \(F_{10}\)。
迁移点：局部禁配模式通常按最后一个符号分类；“最后一步”递推是动态规划最小的原型。
边界：若改成不允许连续3个1，状态需要保留末尾连续1的长度，不能只用两个相邻项。
完整题面：使用数字1、2、3组成有序序列，允许重复，要求所有数字之和为6。这样的序列有多少个？
答案：\(24\)个。
设 \(T_n\) 为总和为n的序列数。最后一个数字只能是1、2或3，因此 \(T_n=T_{n-1}+T_{n-2}+T_{n-3}\)，并取 \(T_0=1,T_{-1}=T_{-2}=0\)。得到 \(T_1=1,T_2=2,T_3=4,T_4=7,T_5=13,T_6=24\)。
迁移点：先确认序列是否有序；如果改成“无序拆分”，同一个组合不再对应一个排列，递推和答案都会改变。
边界：若数字可以使用负数或0，状态可能不再是有限向前递推，必须重新定义问题。
完整题面：求 \(100!\) 的十进制表示末尾连续0的个数。
答案：\(24\)个。
每个末尾0来自一个因子10，也就是一对因子2和5。阶乘中2比5多，所以只需数5的个数：
被25、125等整除的数分别额外贡献第二个、第三个5，因此要继续除以5直到商为0。
迁移点：进制末尾问题先转成质因子计数；“最后一位/最后几位”不等于必须做大整数运算。
边界：换成二进制末尾0时，数的是因子2；换成任意进制b，要分解b并取各质因子指数的最小值。
完整题面：只允许使用面额7元和11元的硬币，且每种硬币可以使用任意非负枚。不能凑出的最大整数是多少？
答案：\(7\cdot11-7-11=59\)。
因为7和11互质，经典结论给出最大不可表示数 \(ab-a-b\)。也可以直接看模7：\(11\equiv4\pmod7\)，用 \(0,1,\ldots,6\) 枚11元硬币可以覆盖全部7种余数。对任意 \(n\ge60\)，选择 \(b\in\{0,\ldots,6\}\) 使 \(n-11b\) 被7整除；若需要 \(b=6\)，只能发生在 \(n\equiv3\pmod7\)，而此时不小于60的n至少是66，所以 \(n-11b\ge0\)。因此60及以后都可表示。
59本身逐一检查11元硬币数 \(b=0,\ldots,5\) 时，\(59-11b\) 都不是7的倍数；\(b\ge6\) 时已经超过59，因此59不可表示。
迁移点：可表示性问题先看最大公因数和模数；若gcd不为1，甚至不是所有足够大的整数都能表示。
边界：加入第三种面额后，二元Frobenius公式通常不能直接套用，需要利用结构或做有限状态搜索。
完整题面：把整数1到31写成二进制，所有表示中一共出现多少个数字1？
答案：\(5\cdot2^4=80\)个。
0到31正好对应全部32个5位二进制字符串。固定任意一位，恰有16个字符串在该位置为1；5个位合计 \(5\times16=80\)。去掉全零串不会减少任何1，所以1到31的答案仍是80。
迁移点：当区间刚好覆盖 \(0\) 到 \(2^n-1\) 时，位对称性可以直接计数；这是把数值问题转成均匀样本空间。
边界：对一般区间 \([1,N]\)，每一位不再恰好一半，需要按周期或高位分块统计。
停止题至少有两种语言：固定策略下，先写 \(T>k\) 的概率或等待阶段；可以主动停止时，先比较立即收益与继续价值。遇到清空、重置或部分匹配时，当前状态必须包含足以决定未来的全部信息。
完整题面：独立地从[0,1]均匀取数，直到累计和第一次超过 \(a\)，其中 \(0\le a\le1\)。令 \(N\) 为取数次数，\(S_N\) 为停止时累计和。求 \(\mathbb E[N]\) 和 \(\mathbb E[S_N]\)。
答案：\(\mathbb E[N]=e^a\)，\(\mathbb E[S_N]=e^a/2\)。取 \(a=1\) 就回到原题库的超额和问题。
事件 \(N>k\) 等价于前k个数的和不超过a。因为 \(a\le1\)，这部分区域完全落在单位立方体内，其体积为 \(a^k/k!\)。尾和公式给出
抽样次数是一个可积停止时间，且每次增量均值为1/2，因此由Wald恒等式，\(\mathbb E[S_N]=\mathbb E[N]/2=e^a/2\)。
迁移点：把阈值参数化后，原来的一道题变成一条曲线；尾和不仅给一个答案，还告诉你阈值如何改变等待时间。
边界：若 \(a>1\)，和小于a的区域会撞到立方体边界，不能继续使用单纯形体积 \(a^k/k!\)。
完整题面：独立观察最多两个[0,1]均匀样本。看到第一个样本 \(X\) 后，可以立即停止并获得X；也可以放弃X并必须接受第二个样本。最优策略下的期望收益是多少？
答案：\(\frac58\)。策略是第一轮看到 \(X\ge\frac12\) 就停，否则继续。
如果放弃第一轮，第二轮的期望固定为1/2。因此第一轮的最优决策是比较 \(X\) 和1/2：\(X\ge1/2\) 时停，否则继续。总期望为
迁移点：有限视野最优停止从最后一轮向前倒推；每一轮的阈值就是下一轮的继续价值。
边界：如果放弃后还可以无限观察，问题可能没有真正达到1的停止时刻，必须先补充观察成本或最大轮数。
完整题面：最多投3次公平六面骰子。每次看到点数后，可以立即停止并把该点数作为收益；如果前两次都不停止，第三次必须接受。如何制定最优策略？最优平均收益是多少？
答案：第二次的继续价值为 \(17/4\)，第一次的继续价值为 \(14/3\)；最优平均收益是 \(\frac{14}{3}\)。
第三次只能接受，期望为 \(V_3=7/2\)。第二次看到4、5、6时停，看到1、2、3时继续，因此
第一次看到5、6时停，看到1–4时继续，所以
迁移点：最优停止的阈值不一定是整数或固定常数，它由未来的最优价值递推出来。
边界：若收益是点数的非线性函数，或者每轮观察有成本，停止阈值和递推值都要重算。
完整题面：反复投掷公平六面骰子：出现2、4、6时把记录数加1；出现1或3时把记录清零；出现5时停止并以当前记录数为收益。最优策略下停止时记录数的期望是多少？
答案：\(1\)。
设 \(F(k)\) 为当前记录k时的最终期望。一步之后，偶数以1/2概率进入 \(F(k+1)\)，1或3以1/3概率进入 \(F(0)\)，5以1/6概率直接兑现k：
设 \(F(k)=ak+b\)，比较k的系数得 \(a=1/3\)，再比较常数项得 \(b=1\)。所以从初始记录0出发，\(F(0)=1\)。
迁移点：看到“清空”要把它当成回到固定状态，而不是把之前的记录继续累加；线性函数试探常能快速解出重置递推。
边界：如果1或3只减少记录1而不是清零，状态转移会改变；若停止面与清空面重叠，必须先说明操作优先级。
量化面试中的统计题常把“相关矩阵是否合法”“分组指标能否合并”“赔率是否真的公平”放在一起考。共同点是：先检查整体对象必须满足的约束，再区分条件均值、组间波动和信息生成机制。
完整题面：4个标准化随机变量两两相关系数都等于 \(\rho\)。为了使相关矩阵合法，\(\rho\) 的最小可能值是多少？
答案：\(-\frac13\)。合法范围是 \(-\frac13\le\rho\le1\)。
相关矩阵写成对角线为1、非对角线为 \(\rho\) 的形式。全1方向的特征值是 \(1+3\rho\)，与全1向量正交的3个方向特征值都是 \(1-\rho\)。半正定要求二者都非负，因此 \(\rho\ge-1/3\) 且 \(\rho\le1\)。
不想写特征值时，也可以看和的方差：\(\operatorname{Var}(X_1+\cdots+X_4)=4+12\rho\ge0\)，直接得到 \(\rho\ge-1/3\)。
迁移点：相关系数不是可以独立随意填写的表格；先找线性组合的方差或矩阵正半定约束。
边界：若相关系数不全相同，不能只检查一个下界；要检查完整矩阵的所有特征值或主子式。
完整题面：市场有高、低两个等概率状态，无风险利率为0。策略B在两个状态的收益均值都是10、标准差都是10；策略A在两个状态的均值/标准差分别为 \((1,0.5)\) 与 \((100,50)\)。A在每个状态内的夏普率都高于B，但合并后谁的整体夏普率更高？
答案：B更高。A的条件夏普率都是2，B都是1；合并后A约为0.83，B为1。
A的整体均值是 \((1+100)/2=50.5\)。整体方差等于组内方差平均值加组均值方差：
因此 \(S_A=50.5/\sqrt{3700.375}\approx0.83\)。B的两个状态均值相同，没有组间方差，\(S_B=10/10=1\)。
迁移点：分组内排序不能直接推出总体排序；合并后多出来的状态均值波动可能吞掉局部优势。
边界：若状态权重改变、收益均值为负，或夏普率采用不同年化口径，都要重新计算，不能只喊“辛普森悖论”。
完整题面：每个细菌独立地产生0、1、2个子代，概率分别为 \(1/5,1/5,3/5\)。从1个细菌开始，最终灭绝的概率是多少？
答案：\(\frac13\)。
设 \(q\) 为一个细菌谱系最终灭绝的概率。子代数生成函数为
一个谱系灭绝，当且仅当它产生的每个子代谱系都灭绝，所以 \(q=f(q)\)。整理得到 \(3q^2-4q+1=0\)，根为 \(1/3\) 和1；分枝过程取区间[0,1]内的最小不动点，故 \(q=1/3\)。
迁移点：随机递归过程要先写“一个节点的所有子树同时成功/灭绝”的方程；平均子代数大于1只说明可能存活，不直接给出灭绝概率。
边界：若不同代的子代分布变化，或多个细菌共享资源产生相关性，单一生成函数不再足够。
完整题面：三队实力为正数 \(a,b,c\)。两队实力为x、y时，前者获胜概率为 \(x/(x+y)\)。在A对B、B对C、C对A三场比赛中，赔率都为十进制3；每场下注1元，赢时净赚2元，输时亏1元。下注B、C、A这三个方向的总期望利润是否为正？
答案：是，严格为正。
三场下注方向的真实胜率之和是
每场的期望利润为 \(3p-1\)，总期望为 \(3(S-1)\)。令 \(x=b/a,y=c/b,z=a/c\)，则 \(xyz=1\)。通分可得 \(x/(1+x)+y/(1+y)+z/(1+z)>1\)，因为分子减分母等于 \(xy+yz+zx+1>0\)。所以 \(S>1\)，总期望严格为正。
迁移点：先把赔率换成“赢时赚多少、输时亏多少”，再检查一组局部概率是否能同时来自同一个全局强弱模型。
边界：赔率口径若是净赔率、含水位或不同场次下注额，利润公式会变；若赔率本身已经包含抽水，正期望结论也不自动成立。
算法题的完整答案通常有两半：先给一个真的能工作的策略，再说明为什么更少的查询或比较不可能。三叉天平、二叉回答和比较决策树，分别提供了不同的“信息容量”上界。
完整题面：9枚外观相同的硬币中恰有1枚较重。使用无砝码天平，每次称量只能得到左重、右重或平衡三种结果。最少几次能保证找出重币？
答案：2次，而且这是最优的。
把硬币分成3组，每组3枚，先称第一组和第二组。若平衡，重币在第三组；若不平衡，重币在较重的一组。此时只剩3个候选，再拿其中两枚互称：哪边重就选哪枚，平衡则第三枚是重币。
一次称量只有3种结果，1次最多区分3种候选；9种可能至少需要 \(3^2\ge9\)，因此不可能1次完成，2次构造达到下界。
迁移点：称量题先用结果数估计信息下界，再设计等分候选集的构造。
边界：如果未知硬币可能偏重或偏轻，候选状态会变成18种，并且每次称量的两侧配置也必须重新设计。
完整题面：给定2n个互不相同的数，只能通过两两比较，最少需要多少次比较才能同时确定最大值和最小值？
答案：\(3n-2\)次。
先把2n个数两两比较，做n次。每次比较的胜者进入“最大候选集”，败者进入“最小候选集”。再在n个胜者中比较n−1次找最大，在n个败者中比较n−1次找最小，总数为 \(n+(n-1)+(n-1)=3n-2\)。
下界来自候选淘汰：找最大至少要淘汰2n−1个最大候选，找最小至少要淘汰2n−1个最小候选。一次比较同时完成两种淘汰，必须是两个此前都没比较过的数；这种双重比较最多只有n次。因此至少需要 \((2n-1)+(2n-1)-n=3n-2\)次。
迁移点：最优比较算法的关键是让一次操作同时产生“胜者证据”和“败者证据”，再把两个候选集合分开处理。
边界：若只找最大值是2n−1次；若允许不比较而使用数值范围、哈希或先验分布，问题已经不是比较模型。
完整题面：未知密码是n位二进制串。每次只能提交一个完整猜测，系统只回答“正确”或“错误”，错误时不透露任何位的信息。最坏情况下保证找到密码，至少需要多少次提交？
答案：\(2^n-1\)次错误提交，随后第 \(2^n\)次必然正确。
一共有 \(2^n\)个可能密码。一次错误提交只排除自己猜的那一个，不会告诉你其他候选之间的关系；如果前 \(2^n-1\)个猜测都错，最后一个未尝试的密码才被迫确定。因此最坏情况需要 \(2^n\)次尝试，若按“错误次数”计就是 \(2^n-1\)次。
迁移点：看到“二元回答”不要立刻套 \(\log_2\)；要问两种回答是否都能均衡缩小候选集。
边界：如果系统告诉你每一位是否正确，或错误后返回汉明距离，信息量会大得多，答案不再是穷举式的 \(2^n\)。
完整题面：对8个互不相同的元素，只能通过比较判断大小。任何基于比较的排序算法，在最坏情况下至少需要多少次比较？
答案：至少 \(16\)次。
8个元素有 \(8!\)种可能的相对顺序。每次比较只有大小两种结果，深度为d的二叉决策树最多有 \(2^d\)个叶子，因此必须满足 \(2^d\ge8!\)。于是
迁移点：信息论下界先数需要区分的答案数量，再除以单次操作的分支数；这是“不能更快”的通用骨架。
边界：这个下界依赖元素互异且只能比较；如果允许直接访问键值、利用范围或使用非比较排序，决策树模型不再适用。
对称性不只出现在网格和圆桌里。随机矩阵的行列式、两组硬币的胜负、骰子总和与二十面骰子的比较，都可以通过交换样本、反射结果或消灭交叉项来简化。先说明随机对象和是否允许平局，答案才不会漂移。
完整题面：令 \(A\) 是 \(n\times n\) 矩阵，每个元素独立地以相同概率取+1或−1。求 \(\operatorname{Var}(\det A)\)。
答案：\(n!\)。
行列式展开为 \(\det A=\sum_{\sigma}\operatorname{sgn}(\sigma)\prod_i a_{i,\sigma(i)}\)。每个乘积包含均值为0的独立随机变量，所以 \(\mathbb E[\det A]=0\)。平方展开时，若两个排列 \(\sigma\ne\tau\)，至少有一个矩阵元素只出现一次，交叉项期望为0；只有 \(\sigma=\tau\) 时每个元素都平方为1。共有 \(n!\) 个排列，因此方差就是 \(n!\)。
迁移点：看到随机多项式或行列式，先展开并检查每个变量的出现次数；均值为0和独立性会大量消灭交叉项。
边界：如果元素有偏、彼此相关或取值不再是对称的±1，交叉项未必消失，不能照搬 \(n!\)。
完整题面：投掷三个独立公平六面骰子，令总和为X；再投一个独立公平二十面骰子，令结果为Y。比较X和Y时，X获胜、Y获胜、平局的概率分别是多少？
答案：\(P(X>Y)=P(X\lt Y)=19/40\)，平局概率为 \(1/20\)。
把三个六面骰子的每个点数 \(d\) 替换为 \(7-d\)，则总和X变成 \(21-X\)；把二十面骰子的点数Y替换为 \(21-Y\)。这个变换保持联合分布，并把事件 \(X>Y\) 与 \(X\lt Y\) 一一对应，所以两种胜率相同。
平局只可能发生在 \(X=Y\) 且 \(X\in\{3,\ldots,18\}\)。对每一个三骰结果，二十面骰恰有一个点数能与之相等，因此平局概率是 \(1/20\)。剩下的概率平均分给两种胜负结果，得到 \((1-1/20)/2=19/40\)。
迁移点：公平性常由保持样本空间的双射证明；比较期望值不能替代胜负概率。
边界：若题目规定平局由某一方获胜，或骰子面值不是对称区间，必须重新处理反射后的事件。
完整题面：独立观察 \(n\) 个来自同一连续分布的随机变量，分布没有原子，因此几乎必然没有并列最大值。第1个样本成为最大值的概率是多少？
答案：\(1/n\)。
最大值一定落在某一个位置。由于n个位置完全对称，任何一个位置成为最大值的概率相同；这些事件互斥且并集为全集，所以每个概率都是 \(1/n\)。这个证明不需要知道具体分布函数。
迁移点：只要样本可交换且几乎无并列，极值位置通常先用标签对称性解决，再考虑数值大小。
边界：若分布不同、存在并列或观察机制偏向某些位置，交换对称不成立；离散分布尤其要先处理平局。
完整题面：两组各有 \(n\) 枚公平硬币。比较两组正面数，若第一组更多则A赢，第二组更多则B赢，相等则平局。求A获胜概率。
答案：\(\frac12\left[1-\frac{\binom{2n}{n}}{4^n}\right]\)。
交换两组硬币会把A赢映成B赢，因此两种胜率相等。平局概率是两组正面数相等：
最后一个等式是Vandermonde恒等式。于是A胜率为剩余概率的一半。
迁移点：公平性问题先找交换对称；剩下的难点通常只是一项平局概率。
边界：若两组硬币数量不同、硬币有偏或平局有特殊裁决，交换对称会改变。
许多序列题的具体数值并不重要，重要的是它们第一次出现的顺序、是否刷新历史极值，或相邻符号何时发生变化。把这些事件逐位置或逐类型写成指标，能把看似依赖全历史的问题降维。
完整题面：把 \(1,2,\ldots,n\) 随机排列。若第k个元素大于它前面的所有元素，就称它是一个记录最大值。平均有多少个记录最大值？
答案：\(H_n=1+\frac12+\cdots+\frac1n\)。
看前k个位置时，这k个数中的最大值等可能出现在任何一个位置。第k个位置成为最大值的概率为1/k。定义指标 \(I_k\) 表示它是否成为记录最大值，线性相加得到 \(\mathbb E[\sum_kI_k]=H_n\)。
迁移点：记录值只关心“是否刷新当前极值”，不关心前缀里具体有哪些数。
边界：若元素允许相等，需要说明相等时是否刷新；若排列带偏，位置对称也可能失效。
完整题面：将 \(1,2,\ldots,n\) 随机排列，要求从第二个位置开始，每个新数都必须严格大于此前所有数，或严格小于此前所有数。满足条件的概率是多少？
答案：\(\frac{2^{n-1}}{n!}\)。
满足条件的排列删掉最后一个元素后仍满足条件。最后一个元素必须是当前集合的最大值或最小值，因此每一步反向删除都有2种选择；只剩一个元素时停止，合法排列数为 \(2^{n-1}\)。除以总排列数 \(n!\) 得答案。
迁移点：正向规则很长时，尝试从最后一步反推；“最后一个必须是极值”会把递推变成二叉选择。
边界：若条件只比较相邻两个数，反向删除不再保持原性质；必须区分局部单调与前缀极值。
完整题面：反复投掷公平六面骰子。求在第一次投出奇数之前，2、4、6三个偶数面都已经至少出现过一次的概率。
答案：\(\frac1{20}\)。
每个面第一次出现的先后顺序等可能。事件要求三个偶数面占据首次出现顺序的前三位；前三位内部有 \(3!\) 种排列，后三个奇数面内部有 \(3!\) 种排列。因此概率为 \(3!\cdot3!/6!=1/20\)。
迁移点：无限重复试验如果只问首次出现的相对顺序，就可以压成一次随机排列。
边界：如果要求偶数面连续出现，或要求每个偶数面恰好出现一次，重复次数的结构不能被首次顺序完全替代。
完整题面：连续投掷12次公平硬币。游程是一个极大的同面连续块，例如HHTTHT包含4个游程。游程数的期望是多少？
答案：\(\frac{12+1}{2}=\frac{13}{2}\)。
第一枚硬币一定开启一个游程。对于第 \(i\) 枚与第 \(i-1\) 枚，二者不同的概率为1/2；每次不同就新增一个游程。于是 \(\mathbb E[R]=1+11/2=13/2\)。
迁移点：“块的数量”通常等于1加上相邻转移次数；它比直接枚举所有字符串更稳。
边界：若硬币有偏但仍独立，两个相邻结果不同的概率变为 \(2p(1-p)\)；若有时间相关性，需重新算转移概率。
绳子、骨牌、棋盘路径和多边形对角线看起来不是同一类题，但都要求把一个大目标拆成局部动作：两端点火让剩余时间减半，最左侧铺法决定递推，最后一步决定路径数，交点决定新增区域。构造题要同时写出可执行步骤和每一步维护的量。
完整题面：有两根绳子，每根从一端单独点燃都恰好燃烧60分钟，但燃烧速度沿绳子不均匀。如何准确测出45分钟？
答案：第一根两端点燃，第二根一端点燃；第一根烧完时点燃第二根另一端，再过15分钟即为45分钟。
时刻0同时把第一根两端点燃、第二根一端点燃。第一根无论各段快慢如何，30分钟后必然烧完；此时第二根已经单端燃烧了30分钟，按“单端还需30分钟”的时间计，剩余部分从另一端也点燃后，两端同时烧完只需15分钟，总计45分钟。
迁移点：不均匀对象不能按长度分割，但可以使用整体时间和“两端减半”这一不变量。
边界：如果绳子不能同时从两端点燃，或每根绳子的总燃烧时间不同，构造需要改变；不能把几何中点当作时间中点。
完整题面：用1×2骨牌铺满2×7棋盘，每块骨牌可旋转。共有多少种不同铺法？
答案：\(F_8=21\)种，其中 \(F_1=F_2=1\)。
若最左侧竖放一块，剩下2×6；若横放，则必须在两行各放一块，剩下2×5。因此 \(T_n=T_{n-1}+T_{n-2}\)，初值 \(T_0=T_1=1\)，所以 \(T_7=F_8=21\)。
迁移点：铺法计数先看最左边的局部形状；只要两种分支互斥且覆盖全部可能，递推就成立。
边界：加入正方形砖、缺格或要求颜色限制后，最左侧状态可能需要记录更多信息，不能只保留棋盘长度。
完整题面：在一个凸六边形内部画出全部对角线，假设没有三条对角线在同一个内部点相交。最多把六边形分成多少个区域？
答案：\(25\)块。
六边形有 \(\binom62-6=9\)条对角线。任意4个顶点确定一对相交对角线，内部交点共有 \(\binom64=15\)个。逐条加入对角线时，每个内部交点把它多切一段，因此总区域数为 \(1+9+15=25\)。
迁移点：多边形分割可以把“新增段”转成“新增交点+1”；边界上的顶点不算内部交点。
边界：正六边形等特殊形状可能出现三条对角线共点；题目若不排除这种退化，25只是一般位置下的最大值。
完整题面：从5×5棋盘左上角走到右下角，每一步只能向右或向下。共有多少条不同路径？
答案：\(\binom84=70\)条。
从左上到右下必须走8步，其中4步向右、4步向下。只需选择4个位置放向右步，剩下位置自动向下，因此路径数为 \(\binom84=70\)。动态规划写法则是 \(P(i,j)=P(i-1,j)+P(i,j-1)\)，边界为1。
迁移点：网格路径的递推和组合数是同一件事的两种表达；递推更容易加入障碍和权重。
边界：若允许向左、向上或重复访问，简单的组合数不再适用，必须重新定义状态和是否允许循环。
当题目问访问次数、相邻模式次数或某类局部块的数量时，最稳的起点仍然是指标变量和一次返回概率。全局路径很复杂，但每次从一个局部状态出发，成功或返回的概率往往很简单。
完整题面：简单对称随机游走从0出发，每次加1或减1，直到第一次到达−3或3为止。把时刻0的起点也算作一次访问，访问0的次数期望是多少？
答案：\(3\)次。
每次访问0后，下一步到+1或−1。以从+1出发为例，在区间[0,3]中先回到0的概率是 \((3-1)/3=2/3\)；从−1出发同理。因此每次离开0后返回0的概率都是2/3，访问次数包含初始访问，服从成功概率 \(1/3\) 的几何型计数，期望为 \(1/(1-2/3)=3\)。
迁移点：访问次数可以拆成“当前访问+是否回返”的重复试验；先找一次回返概率，不必枚举完整路径。
边界：若停止边界改成−2和3，左右返回概率不同，需要按第一次离开方向分别计算。
完整题面：连续投掷10次公平硬币。相邻的两个位置同时为正面，就记作一次HH出现；允许HHH贡献两个重叠的HH。HH出现次数的期望是多少？
答案：\(\frac{9}{4}\)次。
共有9个相邻位置对。对第i个相邻对定义 \(I_i=1\) 表示两次都是H；即使不同位置对共享一枚硬币，也不影响期望线性性。每个指标的期望是 \(1/4\)，所以总期望为 \(9/4\)。
迁移点：局部模式的“出现次数”优先按起点位置计指标；重叠不需要额外修正，只要题目确实把重叠算作多次。
边界：若要求“至少出现一次HH”的概率，9个事件的并集需要处理相关性，不能把 \(9/4\) 当成概率。
完整题面：连续投掷10次公平硬币。一个正面游程是一个极大的连续H块；例如THHT中的HH是长度为2的游程。长度恰好为2的正面游程数量期望是多少？
答案：\(\frac{11}{16}\)。
从位置1开始的长度2游程需要HHT，概率为1/8；从位置9开始需要THH，概率也为1/8。内部起点2到8共7个，每个需要THHT，概率为1/16。指标相加得到 \(1/8+7/16+1/8=11/16\)。
迁移点：局部模式计数最容易漏掉序列两端；先把“左边是否存在、右边是否存在”分开处理。
边界：如果把HHH中的两个相邻HH也算作两次模式，题目就不再是“极大游程”，答案会变成另一种指标计数。
题面读完后先写状态、边界和一步转移。暂时不追求算出数字，先确认“历史被压缩成什么”。
把网格尺寸、曲线交点上限、盒子数量、模式或取石子规则改掉，再从原理重算。
最后用一句话回答：如果边界、独立性、一般位置或信息机制改变，哪一行推导首先失效？
“我先把题目翻译成最小状态。若是随机游走，我写当前状态的一步期望并给吸收态设边界；若是分割题，我数新对象被交点切出的段；若是期望题，我拆成指标变量；若是停止题，我看尾概率或部分匹配状态；若是可达性题，我先检查不变量。最后再说明题面改变时哪个假设不能继续使用。”
第8题的4.5依赖“进入边界格就停”，第7题的122依赖矩形处于一般位置；同样地，线性期望不等于独立性，条件概率不等于忽略信息机制，模运算也不能替代目标状态的构造证明。面试中先复述假设，往往比先报数字更重要。
这61道题表面上横跨网格、几何、排列、骰子、模式匹配、统计、公平游戏和博弈，但真正反复出现的只有几种局部结构：一步转移、一个新增边界段、一件局部事件、一个尚未停止的前缀、一个无法改变的类别。题面变化时，数字会变，局部结构往往不变。
随机游走只需要当前位置；HTH需要部分匹配长度；环上覆盖需要连续访问弧和当前端点。状态越大，越容易把题做成暴力枚举。
分割题看新增区域，指标题看新增事件贡献，收集题看新增种类。直接猜总量公式，通常会掩盖边界条件。
棋盘颜色、模4余数、两堆相等关系都是把不可达状态提前删掉的过滤器；这是证明效率，而不是技巧炫技。
如果你能对每道变体先说出“最小状态是什么、单步变化是什么、停止/目标条件是什么、哪个假设一改就失效”，即使当场没有算完，也已经掌握了比背答案更稳定的面试能力。
本笔记以站内《小红书量化面试题库3–54：52道题的完整推导与面试方法》中的第7题、第8题及相关方法索引为起点；61道练习题、数值答案、推导和边界说明均为本笔记的教学扩展，不属于原帖题面。原题库对小红书公开题目范围、题面条件和作者短答案的来源说明，仍以其文末资料索引为准。
数学公式与练习答案按标准概率、离散随机过程、组合计数和棋盘不变量推导；题面中的边界、一般位置、独立投掷和胜负规则若被改写，答案应随模型重新计算。