Solution of ABC438G

题目链接 题外话: 数竞党的防御性证明会用严谨的逻辑说明结论的正确性,而对“解题思路是如何想到的”一类的问题没有任何启发;oier/acmer 的题解则大多会提示我们从哪里入手,却不加严谨的证明。而本题解采取折中的方案:既对解题思路没有任何启发,也不加严谨的证明。 考虑 gcd 的动机在于,对于这样的题,$k$ 巨大。 于是考虑循环节。发现循环节是 $\mathrm{lcm}(n, m)$。 这时,我们考虑完整的循环节。 发现在 $n$ 与 $m$ 不互素时这是麻烦的,而 $n$ 与 $m$ 互素时一个循环节内每对 $(a_i, b_j)$ 刚好出现且仅出现一次。 这时考虑 $g = \gcd(n, m)$。 发现,对于任意 $r$,一个模 $g$ 余 $r$ 的 $i$ 只会和模 $g$ 余 $r$ 的 $j$ 配对。 这样就能够把非互素情形转化为互素情形。 对于互素情形,循环节是容易处理的。 考虑多余的一部分。这时,考虑枚举 $i$,寻找能与 $i$ 配对的 $j$。 记 $n' = n / g, m' = m / g$。 这时,对于一个下标 $i$,能够与它配对的任意 $j$ 与 $kn'+i, k \in \N$ 在模 $m'$ 意义下同余。 ...

December 28, 2025

May the force be with you

假设你刚刚看过这篇文章:浅谈valarray。 现在我们需要模仿 valarray 写一个科学计算库。其中,我们需要支持形如 a + b 的写法,a 和 b 是两个向量,这个表达式的值是两个向量的和,即逐元素相加得到的新向量。 没错。这是运算符重载板子。你也许会写出类似这样的代码: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 template<typename T> struct Vector { std::vector<T> data; // 构造函数,方便初始化 Vector(size_t n = 0) : data(n) {} Vector(std::initializer_list<T> l) : data(l) {} T operator[](size_t i) const { return data[i]; } T &operator[](size_t i) { return data[i]; } size_t size() const { return data.size(); } Vector operator+(const Vector &rhs) const { Vector res(size()); // 初始化大小 for (size_t i = 0; i < size(); ++i) { res[i] = data[i] + rhs[i]; } return res; // 依赖 NRVO } }; 题外话: 注意加法中的 const& 参数类型。它是为了方便接受临时 Vector 对象(右值):普通左值引用会 CE。 ...

December 27, 2025

Evaluation Order of Function Arguments

You might assume that computers evaluate function arguments from left to right. However, that is not always the case. In fact, many programming languages—such as C++ and RnRS Scheme—leave the evaluation order of arguments unspecified. As shown in this post, ignoring this detail can trigger undefined behavior, leading to a Wrong Answer (WA) or Runtime Error (RE). The Behavior in C++ and Scheme Consider the following C++ code: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 void foo(int x, int y) { cout << x << " " << y << "\n"; } int counter() { static int x = 0; x++; return x; } int main() { foo(counter(), counter()); return 0; } If you compile and run this using GCC 15.2 with -O2, you might notice the output is 2 1. The compiler chose to evaluate the arguments from right to left. ...

December 21, 2025

数数

题目 拜谢 @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$。 ...

December 18, 2025

Pattern Matching

我想诸位应该都用过结构化绑定(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 ...))) 什么是模式匹配 模式匹配并不是“字符串模式匹配”,它是一种语言特性。 ...

December 13, 2025

What is meant by miracle?

光剑的后日谈 #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 来解决库的依赖),你会得到这样的输出: ...

December 6, 2025

什么是美?

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

December 6, 2025

鸟儿与孩子

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

December 3, 2025

re:从 no egg 开始的 2025 OI 赛季

魔怔了。破防了。 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 的招笑分数好一点吧。

November 29, 2025

Bitset 维护高维偏序

简单技巧。实用的小 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 的块里。 ...

November 28, 2025