Posts

光剑的后日谈 #3. 这次来聊聊什么是许愿机。 If bird born with no shackles 现在我们需要写一段代码，用矩阵快速幂求解一个递推数列： $$ \begin{cases} f(0)=f(1)=f(2)=1 \\ f(n)=f(n-1)+2f(n-2)+5f(n-3), n \geq 3 \end{cases} $$ 我们知道我们将数列中的相邻几项写成一个向量 $(f(i), f(i+1), f(i+2))$，然后找到一个矩阵乘上它转移到下一个向量 $(f(i+1), f(i+2), f(i+3))$，那么这个矩阵怎么算呢？ 猜肯定是一个办法，但肯定不好。手动求解，待定系数也是一种方法。 然而，我们还有更加优雅的做法。 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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 from z3 import * def solve_transition_matrix(): # 1. 创建求解器 s = Solver() # 2. 定义我们需要求解的 3x3 转移矩阵 M # 变量 m_r_c 代表矩阵第 r 行第 c 列的元素 (全是整数) M = [[Int(f'm_{r}_{c}') for c in range(3)] for r in range(3)] # 3. 定义“任意”时刻的输入向量状态 # 设 f0, f1, f2 分别代表 f(i), f(i+1), f(i+2) # 我们使用 Ints 创建符号变量，这些将作为全称量词的变量 f0, f1, f2 = Ints('f0 f1 f2') # 构造当前向量 V_i v_current = [f0, f1, f2] # 4. 根据递推公式定义期望的输出向量 V_{i+1} # 题目递推式: f(n) = f(n-1) + 2f(n-2) + 5f(n-3) # 对应到我们的符号: 下一项 f3 = f2 + 2*f1 + 5*f0 f3 = f2 + 2 * f1 + 5 * f0 # 构造下一刻向量 V_{i+1} = [f(i+1), f(i+2), f(i+3)] v_next = [f1, f2, f3] # 5. 核心逻辑：构造约束 # 约束条件：M * v_current == v_next # 这个等式必须对“所有”的 f0, f1, f2 都成立 constraints = [] for r in range(3): # 矩阵乘法：第 r 行 点乘 输入向量 row_product = sum(M[r][c] * v_current[c] for c in range(3)) # 结果必须等于输出向量的对应项 constraints.append(row_product == v_next[r]) # 使用 ForAll (全称量词) # 读作：对于任意整数 f0, f1, f2，上述约束(And(constraints))都必须成立 s.add(ForAll([f0, f1, f2], And(constraints))) # 6. 求解并打印结果 if s.check() == sat: m = s.model() print("成功找到转移矩阵 M：") print("-" * 15) # 将 z3 的解转换为 Python 整数并格式化输出 for r in range(3): row_vals = [m.evaluate(M[r][c]).as_long() for c in range(3)] print(f"| {row_vals[0]:^3} {row_vals[1]:^3} {row_vals[2]:^3} |") print("-" * 15) # 验证一下文章开头的直觉 # 第一行应该是 0 1 0 (输出 f1) # 第二行应该是 0 0 1 (输出 f2) # 第三行应该是 5 2 1 (输出 5f0 + 2f1 + 1f2) else: print("未找到满足条件的矩阵。") if __name__ == "__main__": solve_transition_matrix() 用 Python 运行这段代码（当然你需要先使用 pip install z3-solver 来解决库的依赖），你会得到这样的输出： ...

（一篇习作记录） 我思我见：何为“最美少年”？ 在我们这个时代，“最美少年”的称谓频频见诸报端，它赞美着那些品学兼优、拥有杰出事迹的年轻人。然而，抛开这些具体的标签，我们是否曾真正深入地思考过：究竟什么，才构成了一位少年真正的“美”？在我看来，要解答这个问题，必须先拆解其核心——“美”的本质与“少年”的精神。 欲论少年之美，必先探寻“美”的本质。美为何物？是卢浮宫里《蒙娜丽莎》的神秘微笑，是唐诗宋词中凝练的意境，是俊朗秀丽的容颜，亦或是危难中闪耀的人性光辉。美似乎无处不在，却又无从捕捉，它横跨东西，贯通古今，难以被一个统一的定义所禁锢。 然而，在我看来，一切“美”的背后，都潜藏着两种共性：其一为“非凡”，指向稀缺与卓越；其二为“向往”，源自人类内心深处的渴望与认同。我们不会赞叹一块随处可见的顽石，却会为温润剔透的美玉而心动；我们不会惊艳于孩童稚拙的涂鸦本身，却会被其背后那份纯粹的专注与热情所打动。从嶙峋的古树到浩瀚的繁星，从巧夺天工的建筑到熊熊燃烧的火焰，甚至是雷霆风暴、巨型武器，这些事物之所以能带来震撼的美感，皆因其蕴含着打破平庸、超越寻常的力量。美，正是这种“非凡”与“向往”的结合体，是人类对稀缺、卓越之物的本能追寻。 倘若“美”是我们渴望攀登的非凡高峰，那么“少年”，便代表着攀登本身——那份一往无前的姿态与信念。常言道：“人的成长，就是逐渐认识到自己‘比不上’‘做不到’的过程。”这是一个向现实妥协、被经验磨平棱角的过程。而“少年”恰恰是这一过程的反面。它并非一个年龄的标签，而是一种生命的原初状态——一颗尚未对世界说“我不行”，尚未向现实低头，依旧满怀热爱与笃信，坚信自己能够创造“非凡”的心。 当这两种特质交汇，一幅“最美少年”的画像便跃然纸上。一个坚信自己能够创造“非凡之美”的少年，本身就是一种“超乎寻常”的美好。这样的人，我们通常称之为“强者”。强者之强，在于能为常人所不能为，能创造不可思议的奇迹。 真正的强者之美，并非仅仅体现在拥有的力量或技艺上，更在于掌握了获取力量的方法与永不熄灭的信念。这正如一位传奇企业家所言：“即便夺走我的一切，将我扔到沙漠中央，只要有一支商队经过，我就能东山再起。”知识和技能可以被传授，可以被遗忘，但那份从零到一、探索未知的方法论，那种“我能行”的内在驱动力，才是更本质、更强大的力量。这，也正是“少年”精神的核心。 因此，我心目中的“最美少年”，他/她或许没有惊艳的外貌，或许尚未取得惊人的成就，但他/她的心中燃烧着一团火焰——坚信自己拥有创造非凡的潜能，并为之不懈地探索、努力，对生活报以最纯粹的热爱与激情。 这份美，无关外在，直抵灵魂。它是不向局限低头的勇气，是面对未知敢于开拓的锐气，是相信“我能成为强者”的生命意气。这份美，不为岁月所侵蚀，不为困境所磨灭，它是一种精神的肖像，一种生命最昂扬的姿态。这，便是我所认为的，真正的“最美”。

l’oiseauetl’enfant，鸟儿与孩子。 非常喜欢的诗歌，是经典法语歌曲的译本。但也可以视作独立的现代诗。 译者不明。但是最早可确认的来源是《怪物被杀就会死》完结感言，很可能是阴天的作品。 就像是一个眼睛明亮的孩子 目送飞向远方的鸟儿 就像一只青鸟飞跃地球 凝望这美丽的世界 美丽的小船随波而起舞 沉醉于生活，爱与清风 悠扬的歌曲于浪中诞生 离开了白色的沙滩 纯洁的白色，诗人的血液 他们在歌唱，歌颂着爱 把生命的每一天装点成节日 将黑暗用光明来取代 启明的光辉点亮了生命的白昼 为了唤醒那些城市中晦暗的眼睛 在那里，清晨将梦境扰乱 是为了还给我们一个爱的世界 爱是你，爱是我 鸟儿是你，孩子是我 我只是一个孤独于影中的孩子 看见了被繁星点亮的夜 而你，我的星星，一同编织了我们的舞曲 来点燃我熄灭的太阳…… 注：对原文有两处修改。“美丽的小船随波而起舞”原文是“美丽的小船于随波而起舞”，是一个笔误，所以修正。“是为了还给我们一个爱的世界”原文是“是为了给我们一个爱的世界”，这里是我的修改。

魔怔了。破防了。 refresh remainder rethink review relation reverse reserve reunion regret return || T1 retry T2 remind T3 remain T4 renew || @Halberd_Cease : 我来押 NOIP T1：rebuild T2 rehash T3 relink T4 remove 带来好运的黄黑之王。在 NOIP 遇到 NOI plus 还能说什么呢？ 建议评黄黑黑黑。呼应一下诡秘。 获得了严格不超过 140pts。除了 T1 签到之外其他几个题一点不会，随便拼了一些零碎暴力。 只能说比去年 63pts 的招笑分数好一点吧。

简单技巧。实用的小 trick。 一般而言多维偏序（比如大于等于 3 维的偏序）做法是 CDQ 分治。但是当维度比较多（比如 5D 以上）时 CDQ 会极其难写，并且带有很多 log，实际效率很劣。 bitset 能够以 $O(\frac{n^2d}{w})$ 时间和 $O(\frac{n^2}{8})$ 空间解决这类问题。 方法非常简单：高维偏序，要求我们统计满足在每一维度上的属性都被当前元素偏序的元素的集合。“在每一维度上都被偏序”就是每个维度上的独立偏序条件的逻辑与，在集合上，对应的就是交集。 这可以用 bitset 维护，于是做完了。 具体的，我们设 ans[i] 是一个 bitset，维护被 i 偏序的元素的集合，第 j 位为 1 代表 j 被 i 偏序。那么，我们枚举每个维度，设 f[i] 是这个维度上被 i 偏序的元素的集合（同样，第 j 位为 1 代表 j 在这一维度上被 i 偏序。），令 ans[i] = ans[i] & f[i] 即可。 例题：【模板】三维偏序/陌上花开。以及 CF1826E Walk the Runway，等等。 放一个后面那道题的代码： 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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 #include <bits/stdc++.h> using namespace std; int m, n; array<int, 5005> p; array<bitset<5005>, 5005> e; array<long long, 5005> ans; array<array<int, 5005>, 505> r; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> m >> n; for (int i = 1; i <= n; ++i) { cin >> p[i]; } for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { cin >> r[i][j]; } } for (int i = 1; i <= m; ++i) { vector<pair<int, int>> tmp(n + 2); for (int j = 1; j <= n; ++j) { tmp[j] = {r[i][j], j}; } sort(tmp.begin() + 1, tmp.begin() + n + 1); bitset<5005> cur; cur.set(); int banned = 0; for (int j = 1; j <= n; ++j) { while (banned <= n && tmp[banned].first < tmp[j].first) { cur[tmp[banned].second] = false; banned++; } e[tmp[j].second] |= cur; } if (i == m) { for (int id: views::values(tmp)) { e[id].flip(); for (int pre = e[id]._Find_first(); pre <= n; pre = e[id]._Find_next(pre)) { ans[id] = max(ans[id], ans[pre]); } ans[id] += p[id]; } } } long long final = 0; for (int i = 1; i <= n; ++i) { final = max(final, ans[i]); } cout << final; return 0; }

对 $2^{61}-1$ 快速取模的实现存档。 1 2 3 4 5 6 7 8 9 10 11 template <typename T> constexpr uint64_t mod(T res) { constexpr uint64_t mod_p = (1ull << 61) - 1; res = (res >> 61) + (res & mod_p); res = (res >> 61) + (res & mod_p); if (res == mod_p) { return 0; } return res; }

splitmix64 的实现存档。 1 2 3 4 5 6 7 8 9 10 #include <cstdint> uint64_t splitmix64(uint64_t x) { // 固定的“魔法”常数，都是精心挑选的 x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; x = x ^ (x >> 31); return x; }

CSP2025 游记。标题本来打算起“既渡厄劫，自登天门”，但是转念一想我似乎还没有渡过劫难，甚至连准确的估分都做不到。那么就换个标题吧。 在我学习 OI 的三年以来，一个巨大的疑问始终悬挂在心头：我到底会做什么题？ 这个疑问从未消解过。在我刚学 OI 的时候，水平很菜，理解力不高，外加自己学的也不是非常刻苦，导致什么都不会。 后来几年里，我学会了很多东西，做了不少题。然而每每点进一道新的洛谷/CF/at 题，却又发现自己完全不会。尤其是梦熊比赛的题目。 一直觉得自己的实力应当有提高，然而却不知道到底高了多少，现在又是什么情况。 就这样渡过了 2024 CSP。因为题目的水分得到了提高一等。在场上觉得自己做不了不去想正解，在下场之后才发现题怎么这么简单。 之后的一年似乎什么都没干。跟着代码源（机构）训练了一整年，做的全是 CF/at 题目，OI 题倒是没做多少。 每次被 CF 任意难度的题（从 1200 到 2000 的简单题）创死。ABC 成绩也一直没有长进，很少 6 题，我到现在 at 都没有突破 1600. 比较逆天的是代码源普及组课程（L4 上）结课测试，被当场击杀，T2 和 T3 都想假了，两题一共只有 10 pts，整场比赛得分 140 pts。 然后就到了 11 月。秋天开始了。 在我的记忆里，我好像还是当初五年级全校最小的 OIer，还有着充足的时间和光明的未来。但现在我已经初三（学籍初二）了，离退役也不远了。 2024-2025 的一整年如同飞一般滑过，未来滚滚而来，不问人们意见。 初赛，我一直认为初赛虽然不重要，却是挺有意思的。可以拿到文化课去当思考题。 我之前的初赛分数一直都不高，常常挂在程序判断/填空上。这次初赛，我在第二题就被卡住了：没学 KMP ;) 试图现场理解 border 是什么，弄错了几次感觉题目有问题，最后发现是自己理解错了然后切掉了。 选择题都比较简单，后面的几个程序题一眼看上去还是同样困难。然而，令人惊讶的是，在长时间的奋力思考下，我最终都成功理解了它们的意图。唯一的例外是最后那个 (t, n) 门限的组合构造，不过我至少填出了 43 题之外的其他题。 最后得分 97. 复赛。没什么好讲的，该会就会，不会就不会。T1 类似于 duel 和密码锁，不过中间想错一次，又没有注意到 n 是偶数（事实上我考前几天才做过一个保证 n 是偶数的题：https://www.luogu.com.cn/problem/P11452，这个题 n 为奇数难度会飙升）。半小时通过大样例。 ...

如题，一种 lisp 列表的增强版，支持 $O(\log n)$ 级别的随机访问和修改，并且无缝可持久化。 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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 #lang racket/base (define (length-geq? l n) (let loop ([cur l] [len 0]) (cond [(>= len n) #t] [(null? cur) #f] [else (loop (cdr cur) (add1 len))]))) (struct alist (roots) #:transparent) (struct single-tree (root size) #:transparent) (struct tree-node (val l r) #:transparent) (define (alist-cons head l) (let ([rt (alist-roots l)]) (if (length-geq? rt 2) (let ([a (car rt)] [b (cadr rt)] [rest (cddr rt)]) (if (= (single-tree-size a) (single-tree-size b)) (alist (cons (single-tree (tree-node head (single-tree-root a) (single-tree-root b)) (add1 (* 2 (single-tree-size b)))) rest)) (alist (cons (single-tree (tree-node head #f #f) 1) rt)))) (alist (cons (single-tree (tree-node head #f #f) 1) rt))))) (define (alist-car l) (let ([head (car (alist-roots l))]) (tree-node-val (single-tree-root head)))) (define (alist-cdr l) (let ([head (car (alist-roots l))] [rest (cdr (alist-roots l))]) (if (= (single-tree-size head) 1) (alist rest) (let* ([root (single-tree-root head)] [lson (tree-node-l root)] [rson (tree-node-r root)] [size (arithmetic-shift (single-tree-size head) -1)]) (alist (cons (single-tree lson size) (cons (single-tree rson size) rest))))))) (define (get-binary x) (define width (integer-length x)) (define res (make-vector width #f)) (let loop ([i (sub1 width)]) (when (>= i 0) (when (not (zero? (bitwise-and 1 (arithmetic-shift x (- i))))) (vector-set! res i #t)) (loop (sub1 i)))) res) (define (access-in-single-tree p idx) (define width (integer-length idx)) (define bin (get-binary idx)) (let loop ([i (- width 2)] [cur p]) (if (>= i 0) (if (vector-ref bin i) (loop (sub1 i) (tree-node-r cur)) (loop (sub1 i) (tree-node-l cur))) (tree-node-val cur)))) (define (random-access l pos) (set! pos (add1 pos)) ;; 0-base => 1-base (let ([roots (alist-roots l)]) (let loop ([cur roots] [i pos]) (let ([rt (car cur)]) (if (> i (single-tree-size rt)) (loop (cdr cur) (- i (single-tree-size rt))) (access-in-single-tree (single-tree-root rt) i)))))) (define (set-in-single-tree p idx v) (define width (integer-length idx)) (define bin (get-binary idx)) (let loop ([i (- width 2)] [cur p]) (let ([org (tree-node-val cur)] [lson (tree-node-l cur)] [rson (tree-node-r cur)]) (if (< i 0) (tree-node v lson rson) (if (vector-ref bin i) (tree-node org lson (loop (sub1 i) rson)) (tree-node org (loop (sub1 i) lson) rson)))))) (define (random-set l pos v) (set! pos (add1 pos)) (define res (let ([roots (alist-roots l)]) (let loop ([cur roots] [i pos]) (let ([rt (car cur)]) (if (> i (single-tree-size rt)) (cons rt (loop (cdr cur) (- i (single-tree-size rt)))) (cons (single-tree (set-in-single-tree (single-tree-root rt) i v) (single-tree-size rt)) (cdr cur))))))) (alist res)) ;; tests (define a (alist '())) (set! a (alist-cons 3 a)) (set! a (alist-cons 5 a)) (displayln (random-access a 0)) (set! a (alist-cons 7 a)) (set! a (alist-cons 9 a)) (displayln (random-access a 2)) (set! a (random-set a 2 'a)) (displayln (random-access a 2)) (displayln (random-access (alist-cdr a) 1)) 概述 一种基于完美二叉树以及斜二进制分解的结构。lisp 列表的上位替代，支持 $O(1)$ 的 car/cdr/cons，$O(\log n)$ 的随机访问修改。完全可持久化，支持不可变性和结构共享。 ...

前言 · 一点吐槽 为什么诸位都如此热衷于 vscode 啊？ 我随便一翻都能看到 inf 篇介绍 vscode 配置的文章，真是够了。 不如来玩点神秘的：Emacs。 什么是 Emacs？ Emacs 是一款由 GNU 开源软件基金会完全自主研发的开源文本编辑器。在这款编辑器中，你将在一个叫做“buffer”的环境中冒险，与 elisp 邂逅，并探明“Emacs pinky”的真相…… 不开玩笑了。Emacs 是知名的老牌文本编辑器，与 vi/vim 齐名，长期处于编辑器鄙视链的顶端。它的主要优势是无与伦比的可定制性——它是 Lisp Machine 思想的继承者，整个编辑器内核连同各种功能都由一种叫做 elisp 的语言写成，并且自带一个 elisp 解释器。这意味着用户可以像修改游戏 Mod 一样，自由地修改编辑器的任何代码，或者增加自己的函数，把它打造成任何你想要的样子。 它的可定制性是图灵完备的：理论上，你可以用它来做任何事情，包括但不限于浏览网页，管理日程，与朋友吹水，又或者……原神，启动！ 如何获取？ 最简单的方法是访问 GNU Emacs 项目官网或者其 GitHub 仓库然后下载。你也可以用你的包管理器，比如 Windows 的 winget 或 scoop，macOS 的 brew，或者 Linux 的 apt、pacman 等等。在包管理器里搜 emacs 通常就能找到。 装好后先别急着打开，因为这时的 Emacs 没有任何配置，外观简陋，功能匮乏，保证劝退。我们需要给它注入灵魂。 如何配置？（新手的捷径） 好问题。你肯定听说过 Emacs 的配置极其困难，但作为一个刚入门的新手（就像我），想快速上手其实非常简单。 要义在于：不要自己从头配！ 靠自己一行行攒配置所消耗的时间精力是巨大的，很可能在你配出一个好用的编辑器之前，就已经失去兴趣了。 我们可以直接站在巨人的肩膀上，搜寻一些别人做好的 Emacs 发行版。比如经典的 Doom Emacs、Spacemacs、Centaur Emacs 或者 Prelude。 ...