建模。标准的步长 2 约瑟夫问题：从 1 号开始，每个持枪者淘汰下一个存活者。设 \(J(n)\) 为 \(n\) 人问题的幸存者编号（编号从 1 开始、从 1 号起数）。

推导。建立两条递推。\(n=2m\) 偶数：第一轮淘汰 \(2,4,\dots,2m\) 全部偶数号，剩 \(m\) 人 \(\{1,3,\dots,2m-1\}\)，枪回到 1 号——与 \(m\) 人问题同构，子问题编号 \(i\) 对应原编号 \(2i-1\)，故 \(J(2m)=2J(m)-1\)。\(n=2m+1\) 奇数：第一轮先由奇数号持枪者淘汰全部偶数号 \(2,4,\dots,2m\)（共 \(m\) 人），随后枪到 \(2m+1\) 号、它淘汰 1 号，剩 \(\{3,5,\dots,2m+1\}\)，从 3 号重新对应子问题编号 1，即 \(J(2m+1)=2J(m)+1\)。联立：

闭式：写 \(n=2^m+L\)（\(0\le L\lt 2^m\)），则 \(J(n)=2L+1\)。对 \(n=100=64+36\)：

检验。链式递推逐层核对：\(J(3)=3\)（三人：1 杀 2，3 杀 1）→ \(J(6)=2J(3)-1=5\) → \(J(12)=2J(6)-1=9\) → \(J(25)=2J(12)+1=19\) → \(J(50)=2J(25)-1=37\) → \(J(100)=2J(50)-1=73\)，与闭式一致 ✓。小情形手算：\(J(5)=3\)（杀 2、4、1、5，剩 3）✓。二进制口径：\(100=(1100100)_2\)，把最高位的 1 移到末尾得 \((1001001)_2=73\) ✓。

面试怎么讲。「先算小情形找规律，再写奇偶递推，最后给闭式 \(J(n)=2(n-2^{\lfloor\log_2 n\rfloor})+1\)；100 = 64 + 36，幸存者 73 号。递推的洞见是一轮过后问题规模减半、旧编号是新编号的仿射函数。」

建模。「装法」＝重量之和不超过 \(W\) 的包裹子集。这是子集和（subset-sum）的计数版：与「能否恰好装满」的判定版只差最后一步统计口径。先约定：空集（一件不放）计为 1 种装法；若题意要求至少装一件，答案减 1。

推导。动态规划：设 \(dp[j]\)＝「已处理件中，总重恰为 \(j\)」的子集数，初始 \(dp[0]=1\)（空集）、其余为 0。逐件包裹 \(w_i\) 更新，容量维度倒序扫（保证每件只用一次）：

答案 \(\sum_{j=0}^{W}dp[j]\)。复杂度 \(O(nW)\)、空间 \(O(W)\)。

检验。小例全枚举：重量 \(\{2,3,5,7\}\)、\(W=7\)。16 个子集的总重：0、2、3、5、7、5（2+3）、7（2+5）、9、8、10、12、10、12、14、15、17；不超过 7 的恰 7 个（\(\varnothing\)、\(\{2\}\)、\(\{3\}\)、\(\{5\}\)、\(\{7\}\)、\(\{2,3\}\)、\(\{2,5\}\)）。DP 复算：处理 2 后 dp[2]=1；处理 3 后 dp[2]=dp[3]=1... 终态 \(dp[0]{=}1,dp[2]{=}1,dp[3]{=}1,dp[5]{=}2,dp[7]{=}2\)，求和 7 ✓。边界：全部重量大于 \(W\) 时答案为 1（只有空集）；重量为 0 的包裹会以 2 倍复制方案数（放或不放都不超重），实现时应留意。

面试怎么讲。「这是 0/1 背包计数：状态是『恰好装满 \(j\)』的方案数，倒序更新防重复选取，最后对 \(j\le W\) 求和。若面试官要判定版『恰好装满 \(W\)』，答案就是 \(dp[W]\)；若要连续容量上界的前缀统计，把求和换成前缀和（见 033 章）。」

建模（尾零）。末尾的每个零来自一个因子 \(10=2\times5\)；\(100!\) 中 2 的幂次远多于 5，所以尾零数 \(=5\) 的幂次，用勒让德公式（Legendre's formula）数。

推导（尾零）。5 的倍数每个贡献至少一个 5，25 的倍数再贡献一个，125 以上超出范围：

检验（尾零）。2 的幂次 \(\lfloor100/2\rfloor+\lfloor100/4\rfloor+\lfloor100/8\rfloor+\cdots=50+25+12+6+3+1=97\gg24\)，瓶颈确在 5 ✓。量级：\(100!\approx9.3\times10^{157}\)，157 位数字带 24 个尾零，占约 15%，与「5 的密度约 1/5」的直觉一致。

推导（幂塔）。设塔值 \(t\) 满足 \(t=x^t\)（在塔前面再添一层 \(x\) 不改变其值）。代入 \(t=2\)：\(2=x^2\)，得候选 \(x=\sqrt2\approx1.4142\)。收敛性检查：迭代 \(t_{k+1}=x^{t_k}\) 收敛的充要条件是 \(x\in[e^{-e},\,e^{1/e}]\approx[0.0660,\,1.4447]\)；\(\sqrt2\lt e^{1/e}\approx1.4447\)，且在稳定不动点 \(t=2\) 处 \(|t\ln x|=2\ln\sqrt2=\ln2\approx0.693\lt1\)，迭代收敛，塔值确为 2。数值验证：从 \(t_0=1\) 起迭代 \(1\to1.414\to1.632\to1.760\to\cdots\to2\) ✓。

检验（幂塔，经典陷阱）。若题目改成「塔值等于 4」，同样的代数给 \(x=4^{1/4}=\sqrt2\)——同一个 \(x\)，两个「解」。矛盾的解释：\(t=4\) 也满足 \(t=(\sqrt2)^t\)，但它是不稳定不动点（\(|4\ln\sqrt2|=2\ln2\approx1.386\gt1\)），迭代永远不会到达它；无穷幂塔按迭代极限定义，取值为 2 而非 4。这说明「解方程」只是必要步骤，「验证收敛」才是完整答案。

面试怎么讲。「尾零 24 个：勒让德公式数 5 的幂，20+4。幂塔 \(x=\sqrt2\)，但我会主动加上收敛域检查 \(x\in[e^{-e},e^{1/e}]\)，并点破『塔值 4 也解出 \(\sqrt2\)』的陷阱——4 不稳定、不可达。这两题都是『代数给出候选、结构给出裁决』的范例。」

建模。分两层。第一层：若 \(x,y\) 独立同分布 \(\mathrm{Bin}(n,\tfrac12)\)，同值率是被分布完全决定的量；第二层：观测到 47%，与独立基准的偏离度决定「相关性」，进而决定可预测性。先算基准。

推导（独立基准）。\(P(x=y)=\sum_k\binom nk^2\Big/4^n\)。由范德蒙德恒等式 \(\sum_k\binom nk^2=\binom{2n}{n}\)，故

数值：\(n=1\) 恰 \(\tfrac12\)；\(n=2\) 为 \(6/16=37.5\%\)；\(n=50\) 约 7.96%（近似式 7.98%，相当准）。

推导（解读 47%）。观测值 47% 最贴近 \(n=1\)（伯努利 0/1）情形的基准 50%。独立伯努利的同值率恰为一半，47% 意味着同值率比独立基准低 3 个百分点。对两个公平的 0/1 变量，相关系数与同值率有一一对应：\(\rho=2P(x=y)-1=2\times0.47-1=-0.06\)，即微弱负相关（也可能是噪声，见下）。

推导（可预测性）。用 \(x\) 预测 \(y\) 的天花板由 \(R^2=\rho^2\) 给出（线性回归框架见 026 章）：\(\rho^2\approx0.0036\)，即 \(x\) 至多解释 \(y\) 变异的 0.36%。若非要说策略，最优猜测是「\(y=1-x\)」（反着猜），胜率 53%——比瞎猜（50%）只高 3 个点。这个优势是否真实存在还取决于样本量 \(T\)：检验「同值率 47% 对 50%」需 \(z=\frac{0.03}{0.5/\sqrt T}=0.06\sqrt T\gt1.96\)，即 \(T\gt(1.96/0.06)^2\approx267\) 对观测（019 章的检验框架）。样本不足时，47% 更可能是巧合。

检验。一致性：同值率低于一半对应负相关、反着猜，方向自洽 ✓；界：\(P(x=y)\in[0,1]\) 对应 \(\rho\in[-1,1]\)，47% 落在中间偏负 ✓；量级：\(|\rho|=0.06\) 属「几乎不相关」，任何声称「强预测」的结论都与 \(R^2=0.36\%\) 矛盾。

面试怎么讲。「先算独立基准：同值率 \(=\binom{2n}{n}/4^n\)，伯努利情形是 50%；47% 偏离基准 3 个点，对应 \(\rho=-0.06\)、\(R^2\approx0.4\%\)——预测价值几乎为零。再补统计审慎：需要约 267 对观测才能确认这 3 个点不是噪声。结论：47% 的重合更像弱相关或巧合，不足以支撑预测策略。」