题目 拜谢 @CXiii 提供题目。 NOIP 模拟赛签到题。我们有 $2^n$ 个点，编号 $0 \cdots 2^n-1$。对于一个包含 $[0, 2^n)$ 中整数的集合 $S$，我们有图 $G_S$： 当且仅当 $\exist x \in S \text{ s.t. } i \text{ xor } j = x$ 时，$i$ 与 $j$ 间有一条无向边。 对所有满足 $G_S$ 连通，且元素数量（在使得图连通的集合中）最小的 $S$ 计数。模 998244353。 初步分析与转化 使用异或的性质。$i \text{ xor } j = k \Leftrightarrow i \text{ xor } k = j$，所以，可以视为我们从一个点 $i$ 出发，每一步异或上一个 $S$ 中元素走到另一个点，重复任意多次走动而抵达终点 $j$。 考虑异或的结合律。所以这个过程整体等价于 $i$ 异或上一个常数 $k$。我们知道，$k$ 是 $S$ 中的一些元素的异或和，但又有 $k = i \text{ xor } j$。 ...

我想诸位应该都用过结构化绑定（structure bindings）吧。或者听说过“模式匹配”这个工具（我之前的一些文章中就用过）。 今天来聊聊这个有趣的语言特性。 依然先放代码： 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 #lang racket (define-syntax pmatch-if (lambda (stx) (syntax-case stx (quote any/p ?) [(_ val any/p t f) #'t] [(_ val x t f) (identifier? #'x) #'(let ([x val]) t)] [(_ val (? predicate pat) t f) #'(if (predicate val) (pmatch-if val pat t f) f)] [(_ val (quote x) t f) #'(if (equal? val 'x) t f)] [(_ val x t f) (not (pair? (syntax->datum #'x))) #'(if (equal? val 'x) t f)] [(_ val (pat1 . pat2) t f) #'(if (pair? val) (let ([x (car val)] [y (cdr val)]) (pmatch-if x pat1 (pmatch-if y pat2 t f) f)) f)]))) (define-syntax pmatch-inner (syntax-rules () [(_ v) (error "pmatch: match failed:" v)] [(_ v [pat body ...] rest ...) (let* ([tmp v] [failure (lambda () (pmatch-inner tmp rest ...))]) (pmatch-if tmp pat (begin body ...) (failure)))])) (define-syntax-rule (pmatch v clauses ...) (let ([tmp v]) (pmatch-inner tmp clauses ...))) 什么是模式匹配 模式匹配并不是“字符串模式匹配”，它是一种语言特性。 ...

光剑的后日谈 #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 为奇数难度会飙升）。半小时通过大样例。 ...