简单技巧。实用的小 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; } 分块优化 三维偏序模板直接套 bitset 会爆空间。解决方法是分块处理：将所有元素划分进一个个大小为 B 的块里。 ...

对 $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。 ...

1 2 3 4 5 6 7 8 关于 <我的问题> 这个问题，请不要给出一个平衡各方的中立答案。 请你提出**三种不同且有明确立场的观点**。对于每一种观点，请你评估： - 观点名称：给这个观点起个名字。 - 核心论点：简要阐述其主要逻辑。 - 被接受程度：评估这个观点在当前专家和公众讨论中的普遍程度（高/中/低）。 - 信心指数：你（作为LLM）认为这个观点在未来成为现实的可能性有多大（1-10分）。

光剑后日谈 #2. 在 Scheme/Racket 的世界里，我们常说“一切代码皆为 S-expression”。一个函数调用是 (函数名 参数1 参数2)，一个列表是 (元素1 元素2 元素3)，它们都遵循着括号包裹、前缀表示的统一形式。 但细心的你可能会问，'(a b c) 或者 #'(+ 1 stx) 呢？开头的那个 ' 或 #' 字符，怎么看也不像是列表的一部分。它们是如何融入这套 S-expression 体系的？ 答案很简单：它们是一种语法糖。我们都知道 'exp 等价于 (quote exp)，#'exp 等价于 (syntax exp)。这个单引号 ' 仿佛是一个别名，在 Racket 读取我们的代码时，就悄无声息地将它转换成了标准的形式。这种在“读取阶段”就生效的转换规则，被称为读取器宏（Reader Macro）。 读取器宏背后，是整个 Lisp 家族语言引以为傲的宏系统。宏是一种强大的元编程工具，它本质上是一个在编译期（或称为“展开时”）执行的函数。这个特殊的函数，它的输入是代码（以语法对象的形式），输出也是代码。它允许我们对代码进行任意复杂的、图灵完备的变换，从而彻底扩展语言本身的语法。 那么，亲手编写一个宏，究竟是怎样的体验呢？ 宏之初体验：编写你的第一个宏 when 让我们从一个简单的需求开始。在编程中，我们经常遇到一个场景：“当某个条件成立时，执行一系列操作”。用 Racket 的 if 可以这样写： 1 2 3 4 5 (if (< user-level 5) (begin (display "权限不足！") (log-warning "Attempted access by low-level user.")) #f) 每次都写 (begin ...) 有点繁琐（更何况 Racket 强制 if 有两个分支，那个不需要的分支混淆了语义）。如果我们能创造一个新语法 when，让代码变成下面这样，岂不是更清晰？ ...

一个由不可以总司令想到的有趣概率/期望题。 题面 一套卷子上有 $n$ 道判断题。你不知道它们的答案，但是你知道存在一个常数 $p \in [0, 1]$，对任意一道题，它的答案是“正确”的概率为 $p$。 你决定采用一种策略来答题：选择一个常数 $p' \in [0, 1]$，对于任意一道题，你以 $p'$ 的概率选择“正确”。 求问： 若要使得期望做对题数最多，应该选择怎样的 $p'$？期望做对题数是多少？ 若要使得期望全对概率最大，应当选择怎样的 $p'$？期望全对概率是多大？ 解答 这是一个非常棒的问题！它涉及了期望、概率和优化策略，我们来一步步分解它。 首先，我们来明确一下变量和事件： $n$: 题目的总数。 $p$: 任意一道题的真实答案是“正确”的概率。 $1-p$: 任意一道题的真实答案是“错误”的概率。 $p'$: 你回答任意一道题为“正确”的概率。 $1-p'$: 你回答任意一道题为“错误”的概率。 你的回答策略和你不知道的真实答案是相互独立的。 1) 使得期望做对题数最多 我们要计算做对题数的期望值，并找到使这个期望值最大的 $p'$。 计算单题做对的概率 首先，我们考虑只做对一道题的概率。有两种情况可以做对一道题： 题目的真实答案是“正确”（概率为 $p$），你也回答“正确”（概率为 $p'$）。这件事情发生的概率是 $p \cdot p'$。 题目的真实答案是“错误”（概率为 $1-p$），你也回答“错误”（概率为 $1-p'$）。这件事情发生的概率是 $(1-p) \cdot (1-p')$。 由于这两种情况是互斥的，所以做对任意一道题的概率 $P(\text{单题正确})$ 是两者之和： $P(\text{单题正确}) = p p' + (1-p)(1-p')$ 计算期望做对题数 设 $X$ 为你做对的总题数。$X$ 可以看作是 $n$ 个独立的伯努利试验的和，其中每次试验“成功”（即做对题）的概率为 $P(\text{单题正确})$。 ...

从上一篇文章 https://www.luogu.com.cn/article/a0rd1bxx 的线性代数大学习中，我们知道旋转可以视为乘以一个矩阵。 那么，记 $R_\theta$ 是旋转 $\theta$ 对应的矩阵。 设旋转 $\alpha$ 的变换 $f_\alpha (P) = R_\alpha P$，以及相应的旋转 $\beta$ 角的变换 $f_\beta (P) = R_\beta P$。 显然有旋转 $\alpha + \beta$ 角等于先转 $\alpha$ 再转 $\beta$，也就是说 $f_{\alpha+\beta}(P) = f_\alpha(f_\beta(P))$ 恒成立。那么，代入函数的定义： $R_{\alpha+\beta}P = R_\alpha (R_\beta P)$ 用结合律，就有 $R_{\alpha+\beta}P = (R_\alpha R_\beta) P$ 既然对任意向量两个矩阵的变换结果相同，那么它们肯定是相同的。有 $R_{\alpha+\beta} = R_\alpha R_\beta$ 这样，由于我们知道 $R_{\alpha+\beta}$ 中包含 $\sin (\alpha+\beta)$ 和 $\cos (\alpha+\beta)$ 项，我们就可以用矩阵乘法算出来 $R_{\alpha+\beta}$，然后从中取出相应的项。 计算过程如下： $R_{\alpha+\beta} = R_\alpha R_\beta = \begin{pmatrix} \cos\alpha & -\sin\alpha \\ \sin\alpha & \cos\alpha \end{pmatrix} \begin{pmatrix} \cos\beta & -\sin\beta \\ \sin\beta & \cos\beta \end{pmatrix}$ ...