Posts

做到了 ABC448E，感觉很精妙。 题目中有个部分是模意义下等比数列求和。那么来讲讲它的几种做法。 公式 直接套公式。 $$ \sum_{i=0}^n a^i = \frac{a^{n+1}-1}{a-1} $$然后用逆元。不讲。 如果等比数列不是从 1 开始的，提取首项为公因数即可。下面所有讨论都默认 1 为首项。 更好的方法 公式法需要逆元，在逆元不存在时就寄了。而恰好，448E 的模数不是质数。 我们有几种方法来处理这个情况 下文定义 $$ f(l, a) = \sum_{i = 0}^{l-1} a^i $$分治求和 洛谷已经有篇文章讲过这种手法了。我在场上推出来也受到了它的启发。 大概来说，我们将序列平均分为两部分。 $$ f(l, a) = \begin{cases} (1+a^{l/2})x, \; l \text{ is even}\\ x+a^{(l-1)/2}(ax+1), \; l \text{ is odd} \end{cases} $$其中 $x := f(\lfloor \frac{l}{2} \rfloor, a)$。 这样，做分治再套快速幂就可以以 2log 复杂度解决。不过这样不够优秀。 两种优化的分治 维护幂信息 注意到每层递归重算快速幂非常不优。我们在计算 $f(l, a)$ 时顺便维护 $a^l$，在计算完 $x$ 之后将 $a^{\lfloor \frac{l}{2} \rfloor}$ 平方就得到 $a^l$。 ...

引入 给定字符串 $S$ 与模式串 $P$。问 $P$ 的最长的是 $S$ 的子串的前缀的长度。 我会暴力！ $O(nm)$，非常显然。不讲。 喜欢哈希的小朋友们你们好啊！ 注意到答案具备单调性。于是我们使用二分，外加哈希来检验。 复杂度 $O(n\log m)$，其中 $n$ 是 $S$ 的长度，$m$ 是 $P$ 的长度。 已经很优秀了，但是还不够，毒瘤出题人出了 $n=m=3\times 10^7$ 的数据范围！ 等价重写 Hash 的算法相当于二分匹配前缀长度，然后枚举前缀匹配起始点。 重写为另一种等价的形式：枚举前缀匹配的起始点，然后二分产生的匹配的长度。 现在，Hash 的问题在于每次重新二分一看就非常不优。 当然我不是让大家写分散层叠（分散层叠也完全用不上）。但是我们获得了一些优化的可能。 包的 假设现在我们在一个匹配起始点 $i$，有一个长度为 $l$ 的匹配（意味着匹配的结束点在 $e = i + l - 1$）。 考虑一个起始点在 $i$ 之后的匹配：假设起始点为 $j$。 有两种可能： $j \leq e$ $j > e$ 我们先处理所有第一种情况，然后我们重置 $i = e + 1$ 就可以继续处理第二种情况。 注意到第一种情况具备非常神奇的特性：$[j, i + l)$ 这段下标区间内 $S$ 的子串，等于 $P$ 长度为 $i + l - j$ 的前缀，而同时，当前起始点在 $i$ 的匹配中，与这部分对齐的一段后缀也等于这段子串！ ...

原题链接 一句话总结：四个关键点是“支架”。 首先注意到右下角的 $n \times n$ 区域内的雪必须全部清除，否则连目的地都不安全，一定会有人生病。 于是我们只需要在左下和右上两块区域中设法开出一条路来。 注意到有八个点，一旦清扫完成就不需要清扫别的点。这些点是 $(n+1, 1), (n+1, n), (2n, 1), (2n, n), (1, n+1), (1, 2n), (n, n+1), (n, 2n)$。感性理解一下。 事实上，只需要在这些点中取最小代价，就得到了最优答案。 因为任何一种合法答案，都必然包含这八个点中的一个。 回到开头的省流，四个关键点是 $(1, 1), (1, n), (n, 1), (n, n)$。 直观上理解，它们不能全都走别的点的路径离开，必须有一个有属于自己的路。或者说，它们支撑了整个网格的结构，如果不移走其中一个的话就动弹不得。 具体的，我们最终肯定需要挪动这四个点到右下角。那么考虑第一次操作它们所在的任意行列。不可能在不使这四个点都不超出左上角 $n \times n$ 区域的情况下进行一次操作。 那么至少有一个点要移动到有雪的区域，我们需要清理它的落点。这落点一共可能有八个，就是上面列出的那些。 所以必然清理这八个点中的至少一个。同时，清理其中任意一个都足够了，不需要额外清理其他点。所以这八个点的代价取 $\min$ 就是答案。 代码： 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 #include <bits/stdc++.h> using namespace std; int t; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> t; for (int _ = 0; _ < t; ++_) { int n; cin >> n; int64_t term1 = 0; vector c(2 * n + 1, vector<int64_t>(2 * n + 1)); for (int i = 1; i <= 2 * n; ++i) { for (int j = 1; j <= 2 * n; ++j) { cin >> c[i][j]; if (i > n && j > n) { term1 += c[i][j]; } } } int64_t term2 = c[1][n + 1]; term2 = min(term2, c[1][2 * n]); term2 = min(term2, c[n][n + 1]); term2 = min(term2, c[n][2 * n]); term2 = min(term2, c[n + 1][1]); term2 = min(term2, c[n + 1][n]); term2 = min(term2, c[2 * n][1]); term2 = min(term2, c[2 * n][n]); cout << term1 + term2 << '\n'; } return 0; }

原题链接 一句话总结：两个只能动一个 经过艰苦卓绝的努力，我们发现在 $a \geq b$ 时，答案为 $a - b$。原因很简单：这时除了将 $b$ 加一，我们的任何操作都会让 $a$ 变大，而无益于让二者相等。 这就让我们可以用 $b$ 控制 $a$ 的大小，让数据范围中的值域限制有了意义。 注意到执行一次操作 3 就会让 $a$ 变得不小于 $b$。这样就会落入 $a \geq b$ 的情况中，最优策略是固定的了。 所以我们最多执行一次操作 3。 那么，我们需要决策的，就仅仅是在这次操作之前，操作 1 和操作 2 的执行情况。 一种方法是枚举让 $a$ 加了多少，让 $b$ 加了多少。但平方复杂度肯定会超时。 回收伏笔：两个只能动一个。也就是说，操作 1 和操作 2 中至少有一种没有被执行。 证明：假设操作 1 执行了 $i$ 次，操作二执行了 $j$ 次。 那么我们的总代价就是 $i + j + ((a + i) \text{ or } (b + j)) - (b + j)$。 ...

AI 作品。笑点自寻。 不过其实挺深刻的。 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 #include <iostream> #include <complex> #include <vector> #include <cmath> #include <iomanip> using Complex = std::complex<double>; constexpr double PI = 3.14159265358979323846; // 强制编译器内联，坚决不留任何函数调用栈 #if defined(__GNUC__) || defined(__clang__) #define FORCE_INLINE __attribute__((always_inline)) inline #elif defined(_MSC_VER) #define FORCE_INLINE __forceinline #else #define FORCE_INLINE inline #endif // ========================================================== // 1. 蝴蝶操作（Butterfly）的模板完全展开 // ========================================================== template <int N, int I> struct Butterfly { FORCE_INLINE static void apply(Complex* out) { // 编译期常量计算旋转因子 W_N^I (编译器在 -O3 下会直接将其折叠为常数) constexpr double angle = -2.0 * PI * I / N; const Complex w(std::cos(angle), std::sin(angle)); // 核心蝴蝶计算 Complex t = w * out[I + N / 2]; Complex u = out[I]; out[I] = u + t; out[I + N / 2] = u - t; // 递归实例化下一个蝴蝶操作 Butterfly<N, I + 1>::apply(out); } }; // 蝴蝶操作递归终点 template <int N> struct Butterfly<N, N / 2> { FORCE_INLINE static void apply(Complex* /*out*/) { // 递归终止，什么都不做 } }; // ========================================================== // 2. FFT 递归深度的模板完全展开 (分治阶段) // ========================================================== template <int N, int Stride = 1> struct FFT_Unrolled { FORCE_INLINE static void apply(Complex* out, const Complex* in) { // 1. 编译期静态分治：偶数部分和奇数部分 FFT_Unrolled<N / 2, Stride * 2>::apply(out, in); FFT_Unrolled<N / 2, Stride * 2>::apply(out + N / 2, in + Stride); // 2. 对当前层执行完全展开的蝴蝶操作 Butterfly<N, 0>::apply(out); } }; // FFT 分治递归终点 (N = 1) template <int Stride> struct FFT_Unrolled<1, Stride> { FORCE_INLINE static void apply(Complex* out, const Complex* in) { out[0] = in[0]; // 直接赋值，底层汇编就是一条 MOV 指令 } }; // ========================================================== // 3. 动态分派器 (运行时根据 k 调用对应的实例化代码) // ========================================================== void fft_dispatch(int k, Complex* out, const Complex* in) { switch (k) { case 0: FFT_Unrolled<1>::apply(out, in); break; case 1: FFT_Unrolled<2>::apply(out, in); break; case 2: FFT_Unrolled<4>::apply(out, in); break; case 3: FFT_Unrolled<8>::apply(out, in); break; case 4: FFT_Unrolled<16>::apply(out, in); break; case 5: FFT_Unrolled<32>::apply(out, in); break; case 6: FFT_Unrolled<64>::apply(out, in); break; // 你可以继续写到 7, 8... 但建议不要超过 10，否则编译器会崩溃 default: std::cerr << "K out of bounds for unrolled FFT!" << std::endl; } } // ========================================================== // 4. 测试代码 // ========================================================== int main() { constexpr int K = 3; constexpr int N = 1 << K; // N = 8 std::vector<Complex> in(N); std::vector<Complex> out(N); // 构造一个简单的测试信号 for (int i = 0; i < N; ++i) { in[i] = Complex(i, 0); } // 调用 K=3 的展开 FFT fft_dispatch(K, out.data(), in.data()); // 打印结果 std::cout << std::fixed << std::setprecision(2); for (int i = 0; i < N; ++i) { std::cout << "out[" << i << "] = " << out[i].real() << " + " << out[i].imag() << "i\n"; } return 0; }

考虑这么一个题目： 维护整数多重集，支持插入删除，查询全局 xor 和以及全局加一。 如果不考虑全局加一，就是唐题。不过全局加一和异或本质不兼容，比较难搞。 本文介绍的就是用以解决这一问题的技巧。 考虑维护一棵 01 Trie。与普通的用于按位贪心的 Trie 不同，这棵 Trie 按照从低位往高位的顺序。 简单来说，根节点是从低往高第 0 位，是一个超级源点。它的两个孩子是从低往高第 1 位，位权为 1，这两个孩子的孩子（即深度为 2 的那一层节点）的位权为 2，以此类推。 插入、删除和普通 01 Trie 相同。 查询全局 xor 和也比较好做。我们在每个节点上维护 count（子树中的元素计数）和 xor_sum（子树中元素的异或和）。 加法是重点。 注意到最低位为 0 的元素加一之后最低位为 1，而最低位为 1 的元素加一之后最低位为 0，并产生一个进位。 那么从根节点出发，先交换两个儿子，然后递归操作那个本次操作前当前位为 1 的子树。 结束了。 扩展：全局异或上一个数 考虑维护全局懒标记：Trie 中的一个值 v 的实际值是 v xor tag。 全局异或就变成了对 tag 的简单更新。 现在考虑如何在有 tag 的情况下做全局加一。 很简单：套用之前交换子树和递归进位的逻辑。不过，注意 Trie 中当前位为 1 的子树未必是真实产生进位的子树，因为 tag 的当前位可能为 1，这时，Trie 中的 1 子树的真实值为 0，反而是 0 子树的真实值为 1。

省流：gemini 3.1 Pro 对这个经典难题提出了一个优于暴力的做法。 区间加区间异或和怎么做？ 具体的，你需要维护一个整数数组，支持两种操作： 将一个连续区间内所有元素加上一个整数 查询一个连续区间内的元素的异或和 这个题有任何比较好的做法吗？ 这是一个在算法竞赛（如 Codeforces、Luogu）中非常经典的高级数据结构难题。 区间加（Addition）和区间异或和（XOR Sum）在本质上是“不兼容”的。因为加法会产生进位（Carry），一个加法操作可能会同时改变多个连续的高位，这导致传统的线段树（Segment Tree）无法在 $O(\log n)$ 的时间内合并和下传 Lazy Tag。 目前解决这个问题最通用且高效的经典做法是：分块（Square Root Decomposition / Block Decomposition），结合按位拆分与二分查找。 以下是详细的做法和原理解析： 核心思想：按位拆分 + 余数定理 我们要查询区间异或和，实际上等价于：对于每一位 $k$（$k \in [0, 30]$），统计区间内该位为 $1$ 的数字个数。如果个数为奇数，那么异或和的第 $k$ 位就是 $1$。 假设一个数字原来是 $x$，被加上了 $v$。那么 $x+v$ 的第 $k$ 位是否为 $1$，完全取决于它们对 $2^{k+1}$ 的余数。 具体规律如下： 设 $M = 2^{k+1}$， $H = 2^k$。 那么 $(x + v)$ 的第 $k$ 位为 $1$，当且仅当： $$ (x \bmod M + v \bmod M) \bmod M \ge H $$如果我们将 $y = x \bmod M$ 看作原数组的属性， $V = v \bmod M$ 看作懒标记（Lazy Tag），因为 $y \in [0, M-1]$ 且 $V \in [0, M-1]$，上述条件其实等价于 $y$ 落在了两个连续的区间内： ...

原题链接 挺神妙的一个题吧。自己做的时候完全没做明白，看题解也看到晕晕乎乎的。今天重新从哈集幂的视角理解了一下，才发现确实挺妙（而且典）。 面对这个题首先做一些小转化。考虑一条边，它在哪几条路径上？我们用一个掩码（$k$ 位二进制数）表示这个集合。第 $i$ 位为 1 代表这条边在 $a_i$ 与 $b_i$ 间的简单路径上。 我们考虑给树赋一个根，然后把每条边和它连接的两个点中深度较大的对应起来。一条路径经过这条边，当且仅当一个端点在这个点的子树中，而另一个端点不在子树中。这样，我们对每个点维护一个掩码，第 $i$ 位代表第 $i$ 条路径在该点子树中的端点的数目的奇偶性。不难发现这个掩码其实和这个点对应的边的掩码相等。 容易预处理这个掩码。具体的，考虑对第 $i$ 条路径的一个端点 $a$，$\text{mask}_a = \text{mask}_a \text{ xor } 2^i$。然后我们做一次 dfs，对每个点，先处理它的所有子节点，然后它的掩码异或上它所有子节点的掩码的异或和。 然后，我们就注意到，挑选一些边涂色，这时被满足（即有至少一条边被涂色）的简单路径的集合就是这些边对应的掩码（集合）的并集（或者按位或）。 至此，我们就完成了所有平凡的预处理工作。问题被转化为： 给定若干集合，求最少需要选取多少集合才能使得它们的并集为全集。 这个问题是本题的核心，也是一个非常经典的 NP-hard 问题。 我们考虑将最优化问题转化为判定问题：从小到大枚举需要多少集合，再判定这是否可行。 注意到答案最大等于全集大小。因为每个集合至少贡献一位，否则直接去除它更好。 进一步转化为计数问题：选出 $x$ 个集合，有多少种方案使得它们的并集为全集？ 原题在这里要求选出的集合互不相同，但选出重复集合并不影响。 考虑哈集幂。我们构造一个长度为 $2^k$ 的序列 $a_i$（数组），其中第 $s$ 个位置是选出 $i$ 个集合，其并集是掩码为 $s$ 的集合的方案数。 显然有 $a_i = (a_1)^i$，这里的乘法是并集卷积，即 $(\text{or}, \times)$ 卷积。意思是，$a\times b$ 的第 $k$ 位是所有满足 $i \text{ or } j = k$ 的 $a_i \times b_j$ 的和。 ...

我是 comfyUI 萌新。这篇文章技术干货不多，仅仅是下载和配置过程的记录。 省流：垃圾 最近听说了 Z-image turbo。非常感兴趣，于是打算部署一发。 comfyUI 是一款美观易用的本地部署应用。主要战场是扩散生图模型和视频生成，但同样支持 LLM。 主要特性是可以用图形化方式配置工作流（你可能想到了 scratch。没错，就是类似那样）。 我使用了它来运行 Z-image turbo。 下载非常简单。你需要访问官网，然后下载一个安装包。 有人可能用的是 portable。但我选择了 for Windows 的那个打包好的版本。 下载之后无脑跟随指示。 然后会自动下载和配置 pytorch，大概会下载几个 G（pytorch 本体 2.4GB 左右）。 可能会遇到神秘报错。忽略即可。只要能跑通就不是问题。 之后点击 comfyUI.exe 启动。过程也很简单。 可能会提示你选择一个目录放数据。这个目录建议选择空间大的盘符放，因为以后模型权重也要放在里面。 去官网下载 Z-image turbo 的权重。hugging face 不能直连，所以选择 modelscope。 实测这个仓库可用。 进入模型文件一栏，在 split_file 中，分别从 vae、diffusion model 和 text encoder 中挑一个你中意的下载下来。 注意模型的名字标明了量化的程度。text encoder 中，最大的那个无后缀的模型是全精度的。diffusion model 中，BF16 后缀的是全精度的。 量化精度高的模型性能更好。但是会更加消耗显存和算力，所以根据硬件资源量力而行。否则生成速度可能会非常缓慢，并且大量动用虚拟内存，甚至直接崩掉。 下载的模型权重放在你之前选择的那个目录（比如叫做 comfyUI-data）下的 \models\ 中的 \diffusion_models，\text_encoders 和 \vae 中。 注意绝对不是 \ComfyUI\resources\ComfyUI\models。如果你忘记了之前选了哪个目录，你可以进入 comfyUI，点击图标打开菜单，然后选择帮助一栏下的“open folder”，“open model folder”（英文）或者“打开模型文件夹”（中文）。 ...

醒醒，星星。