光剑第二作！ 前言：什么是魔法？ （注：这个前言可以跳过。它是最终成果展示。感到迷惑很正常，请先阅读正文。） 什么是魔法？ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 (define-syntax delay (syntax-rules () ((delay x) (lambda () x)))) (define (lazy-variable thunk) (cons #f thunk)) (define (is-calculated? variable) (car variable)) (define (force variable) (if (is-calculated? variable) (cdr variable) (begin (set-car! variable #t) (set-cdr! variable ((cdr variable))) (cdr variable)))) (define-syntax stream-cons (syntax-rules () ((stream-cons a b) (cons a (lazy-variable (delay b)))))) (define (stream-car x) (car x)) (define (stream-cdr x) (force (cdr x))) (define (int-from n) (stream-cons n (int-from (+ n 1)))) (define nature-numbers (int-from 1)) 真成四十行代码了。感兴趣的读者可以数一数，刚好 39 行。 ...

致谢 Gemini 2.5 Pro 0325 && 0506：文本润色、事实正确性审查，以及帮助我学习、理解和回忆这些内容。 myster1ous： 给予我巨大的启发，帮助我构建出 prev 函数。 前言 本文是光剑系列的第一作，又名《lambda 演算，邱奇编码与优雅的计算模型》。 本文的目的是带领大家踏上一段奇妙的旅程：我们将使用 λ 演算（Lambda Calculus）这一极简的计算模型，并通过丘奇编码（Church Encoding）这一巧妙的技术，一步步构建出我们日常编程中熟悉和依赖的计算体系，例如数字、布尔逻辑乃至更复杂的数据结构。 为了方便演示和实践，本文中的所有代码示例都将使用 Scheme 语言。Scheme 是 Lisp 家族的一员，它的语法是 S-表达式 (Symbolic Expressions)。S-表达式不仅简洁优雅，而且其结构与 λ 演算的表达方式惊人地契合。 在我们开始之前，让我们先快速了解一下 S-表达式： 核心是列表 (List)： S-表达式的基本形式是由圆括号 () 包围起来的列表。 结构：(操作符 参数1 参数2 ...)： 列表中的第一个元素通常是操作符（即要应用的函数），其余元素则是传递给该操作符的参数。 原子 (Atom) 与嵌套： 列表中的元素可以是原子（如数字 123、符号 x、+），也可以是另一个 S-表达式。这种嵌套能力使得 S-表达式可以表示复杂的树状结构。 例如，表达式 (+ 1 (* 2 3)) 在 Scheme 中表示数学上的 1 + (2 * 3)。 这里： 最外层的 (+ 1 (* 2 3)) 是一个 S-表达式。+ 是操作符，1 和 (* 2 3) 是它的参数。 (* 2 3) 本身也是一个 S-表达式。* 是操作符，2 和 3 是它的参数。执行它会得到 6。 所以整个表达式 (+ 1 6) 最终会计算得到 7。 理解了 S-表达式，我们就可以更顺畅地进入 λ 演算的世界了。 ...

光剑系列的第七作！ 前六作： 第一篇：Let’s build our mathematics by using lambda calculus && church encoding! 第二篇：惰性求值、无穷流与发生的魔法 第三篇：协程、生成器与 call/cc 的控制流 第四篇：动态作用域、词法作用域与表达式求值的环境模型 第五篇：基于环境模型的解释器 第六篇：调用栈、de bruijn 索引与堆栈的内存模型 朱约（juyo）/瓦帕德（vaapad）是光剑七式的最后一技。很高兴我们的“光剑”终于抵达了这里！不过也许会有续集。 [此处应有温杜的图片] 一点说明 我更新了工具，本文使用 racket（scheme 的一种实现和变体）完成。这些代码大多可以直接挪用在 scheme 中，但是 match 除外，请使用自己的模式匹配库。我也转载了一个简单的模式匹配库：https://www.luogu.com.cn/article/4kw6oewn 注意使用 #lang racket。 发现有不少 racket 的在线环境，懒得下 racket 的话可以直接用。给一个：https://onecompiler.com/racket 引子 在前作中，我们提到过“call/cc”也即“call-with-current-continuation”的存在。它可以捕获当前的“续延”（coutinuation）并将它作为一个一等公民值。 续延代表程序的“计算上下文”，也即“我们接下来要做什么？”调用一个续延，可以让我们瞬间跳回续延被捕获的那个时间点，还原环境（包括堆和栈，不过那是具体的内存模型。环境是更抽象的“数据上下文”。）以及更重要的，“计算”。 看上去真是神秘又强大（事实上，从 call/cc 和条件判断，我们可以造出其余的所有控制流。）。我们的第五作实现了一个 scheme 子集的解释器，但是也没有实现这个功能。 那么，这个操作是如何实现的呢？“剩下的计算”是如何被表示的呢？这就是我们今天要探讨的话题。 CPS 变换 一个例子 先看下面这段代码： 1 2 3 4 5 6 (define (fact-cps n k) (if (= n 0) (k 1) (fact-cps (- n 1) (lambda (v) (k (* v n)))))) 从名字就可以看出，这是一个计算阶乘的函数。不过它看上去非常的不同寻常。 那个叫做“k”的参数是什么东西？它在干什么？ 事实上，这个“k”就是一个外部传入的续延。它代表“当前函数执行完毕后，还要进行哪些操作”。 现在让我们来看看代码。条件判断很寻常。 ...

算法 trick 的记录。 系列前作：https://www.luogu.com.cn/article/yc9w22em 拆贡献！拆贡献！交换维度！交换维度！时间逆流！时间逆流！操作顺序反演！操作顺序反演！递推！递推！分离常量！分离常量！不同的项分开算！ 优化一些代数式计算的复杂度时，最简单常用的技巧就是试着拆开，然后分离常量和变量，将不同类项分开处理。而当你推不出一些式子时，可以放弃推式子而使用递推。交换求和顺序/交换 DP 转移顺序/维度是破解循环依赖，找到好的计算顺序的方法，这和拆贡献是相关的：拆贡献其实就是变换了统计的第一维度。从按照整体的统计变成按照单个元素统计。 双指针就是“在不合法和不优之间的境界线上游走”，同时也是“一种扫描线”，并且是“在复杂度允许的情况下，枚举一定量信息以确定更多条件”的体现。 而“枚举一定量信息”在 DP 中也很常用。DP 的经典套路就是随便乱设状态，加入信息直到能够转移为止，然后利用种种洞察和优化去掉一部分维度，优化转移直到时空复杂度达标。 在做任何题的时候，第一步考虑性质刻画。无论是操作的性质还是维护信息的性质。性质就是限制，能够帮你找出正解。 一个好的性质刻画也很重要。一个愚蠢的性质刻画会极大地妨碍你做题。所以如果你觉得性质刻画太笨，就试着简化。 “信息学”的本质就是对于信息的处理。算法对于复杂度的优化本质上是减少不必要的对信息的处理（计算）。所以当你试图确定复杂度或者优化复杂度时，不妨思考一下“这个题，至少需要处理哪些信息？如何避免处理不必要的信息？” 信息即向量，操作即矩阵。 写了线性代数大学习，你应当能知道这点。有许多操作都是线性/仿射的，可以写成矩阵。从而拥有结合性，可以用快速幂或者线段树等方法处理。 孤链压缩权值线段树/01 trie。线性空间复杂度，从此整数可重集再也不用平衡树。 线性筛线性预处理积性数论函数。要点在于筛 n = i * p 时用到的 p 和 i 满足 p 不大于 i 的最小质因子。比埃筛更好写。 以后再也不要 naive 地 $O(n \log n)$ 算 d(i) 了。 利用单调性等等贪心性质简化问题。 有交不优 => 钦定末尾。 有时二维问题按第一维排序，而后第二维更小就一定更优所以无脑排除一些。剩下的就满足二维偏序（相当于利用贪心性质额外制造了一个维度上的单调性。这里的贪心性质是“a 被 b 包含 => b 的所有解都不劣于 a 的对应解/a 能干的所有 b 都能干”） 两种证明贪心的策略： 局部上，交换论证/调整法：调整一定能导出不劣的解。 整体上，必要性 => 充分性：我们至少需要多少操作，然后让这些操作发挥最大的效益。 增量更新并不要求旧的答案一定是新的答案。在旧答案总数很小时，可以暴力枚举它们判断它们是否是新的答案。或者，如果容易确定哪些不是新的答案，排除它们即可。 对于一些非常复杂的操作，可以考虑寻找不变量。常见的不变量常常和奇偶性或者两类元素的差有关。因为总和是容易变的，但是有时对于两类东西的作用是相同的，就可以被作差消去。 当操作是对两个相邻元素（或者类似的，一个元素附近的几个元素）时，这样的关于奇偶性或者奇偶下标的元素的差的不变量比较容易出现。 不变量和另一种思想紧密相关，即状态而非过程。在很多贪心或者博弈论的题中，常常有复杂的流程模拟，直接陷进去就做不出来了。 这时可以考虑最终状态或者解的性质，有时能够得到非常简洁优雅的结果。就像解方程一样。 ...