作业一：递推式与基础算法

本篇按作业目录中的解答笔记与三份程序整理。原笔记只保留了部分递推式的求解过程，没有完整题干；下面对能从解答确定的内容直接分析，对无法唯一还原的题干不额外虚构。

1. 递推式：$T(n)=T(n/2)+n$

假设 $n=2^k$，令 $S(k)=T(2^k)$，则

$$S(k)=S(k-1)+2^k,\qquad S(0)=1.$$

展开：

$$S(k)=1+\sum_{i=1}^k2^i=2^{k+1}-1.$$

代回 $n=2^k$：

$$T(n)=2n-1=\Theta(n).$$

递归树也能看出：每层代价依次为 $n,n/2,n/4,\ldots$，几何级数总和为 $\Theta(n)$。

2. 递推式：$T(n)=2T(n/2)+n$

主定理中 $a=2,b=2$，有

$$n^{\log_ba}=n.$$

$f(n)=\Theta(n)$ 与临界项同阶，属于主定理第二种情形：

$$T(n)=\Theta(n\log n).$$

递归树每层都有总计 $n$ 的工作，共 $\Theta(\log n)$ 层，也得到相同结论。

3. 每层按 $7/8$ 衰减的递归树

原解答记录“第 $k$ 层代价为 $(7/8)^kn$”。因此总工作量为

$$n\sum_{k\ge0}\left(\frac78\right)^k=8n=\Theta(n).$$

即使递归树有 $\Theta(\log n)$ 层，也不能简单相乘成 $n\log n$；每层代价在几何衰减，总和仍为线性。

若原式是常见的 $T(n)=7T(n/8)+n$，主定理也给出 $\Theta(n)$，因为 $n$ 多项式地大于 $n^{\log_87}$。

4. Pascal 递推等于组合数

递推定义满足边界

$$C(n,1)=1,\qquad C(n,n)=1,$$

以及

$$C(n,k)=C(n-1,k-1)+C(n-1,k).$$

对 $n$ 归纳。假设规模 $n-1$ 时成立，则

$$\begin{aligned} C(n,k) &=\binom{n-1}{k-1}+\binom{n-1}{k}\\ &=\binom nk. \end{aligned}$$

最后一步是 Pascal 恒等式。边界也与组合数一致，因此递推确实计算 $\binom nk$。

5. 编程题一：错排数

错排数 $D_n$ 表示 $n$ 个元素的排列中，没有任何元素留在原位置的方案数。程序使用递推：

$$D_n=(n-1)(D_{n-1}+D_{n-2}),\qquad D_0=1,D_1=0.$$

理解方式：观察元素 1 被放到位置 $j$。

• 若元素 $j$ 回到位置 1，两者构成二元交换，剩余 $n-2$ 个元素错排；
• 若元素 $j$ 不回位置 1，可把结构对应到剩余 $n-1$ 个元素的错排。

$j$ 有 $n-1$ 种选择，所以得到递推。程序只保留前两项，时间 $O(n)$、空间 $O(1)$，并对模数 $998244353$ 取模。

原程序在 $n=0$ 或 $n=1$ 时直接输出变量 c，其初值为 0；这会让 $D_0$ 错成 0。若题目保证 $n\ge2$ 不影响评测，否则应显式处理两个边界。

6. 编程题二：众数

程序用计数数组统计每个非负整数出现次数，再从小到大扫描，只有遇到严格更大频次才更新答案。因此并列时返回数值最小的众数。

若最大值为 $U$，时间为 $O(n+U)$、空间为 $O(U)$。这种做法依赖值域小且非负；若值域很大或包含负数，应改用哈希表，或排序后扫描连续段。

7. 编程题三：统计 $a_i>3a_j$ 的数对

目标是统计

$$i<j\quad\text{且}\quad a_i>3a_j$$

的有序位置对。原程序每读入一个 $a_j$，扫描此前所有 $a_i$，因此时间 $O(n^2)$、空间 $O(n)$。

归并排序优化

分治处理左右区间后，两侧各自有序。对左半元素 $a_i$，用单调指针在右半中找到满足 $a_i>3a_j$ 的最大范围；指针无需回退，跨区间计数为线性，再做正常归并。

递推为

$$T(n)=2T(n/2)+O(n)=O(n\log n).$$

比较 $a_i>3a_j$ 时要使用足够宽的整数类型，避免 3 * a[j] 溢出。与普通逆序对相比，计数条件改变了，但“左右有序后用双指针统计跨区间对”的核心完全相同。

8. 本次作业串起了什么

• 递推式不能只看递归层数，还要看每层总代价；
• 数学递推通常需要边界和归纳步骤一起证明；
• 值域有限时，计数数组能把排序问题化为线性统计；
• 看到“满足某种大小关系的跨位置数对”，应联想到归并分治优化。