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

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

题目（根据解答与程序还原）

现存材料可确定八项内容：求解三类递推式，证明 Pascal 递推对应组合数，并完成错排数、众数和满足 $a_i>3a_j$ 的数对统计三道编程题。原题完整输入输出格式没有留存，我在下面只保留能从解答与程序确定的任务和算法。

查看解答与实现分析

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. 本次作业串起了什么

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