前缀异或与随机哈希实战：洛谷P6273完全平方数子段计数

又是信奥刷题打卡的一天。今天刚把洛谷 P6273eJOI 2017 的 MagicAC 掉趁热打铁写一篇完整复盘。这题在洛谷的难度标签不算特别高但我真心觉得它非常适合用来打通一个经典套路前缀异或 随机哈希 统计相等前缀。光看题解就是一瞬间的事但自己从 TLE 一路调到 WA 再到 AC踩过的坑比看十篇题解都值。如果你正在备战信奥已经能熟练写 C 和 STL但一遇到“区间统计”“奇偶性”“完全平方数”这类题就头皮发麻那这篇就是写给你的。我会把题目本质、数学转化、工程实现、调试经验全部拆开讲清楚文末还会给出可直接 AC 的完整代码。看完你会发现这题表面叫“魔法”核心其实是一个特别朴素的计数问题。1. 先看懂题目魔法子段到底在考什么1.1 题意翻译与本质题目大意不复杂给一个长度为 n 的序列问有多少个连续子段满足——子段内所有数的乘积是一个完全平方数。举个例子序列[2, 3, 6]中子段[2]乘积 2不是平方数不合法子段[3]乘积 3不是平方数不合法子段[6]乘积 6不是平方数不合法子段[2, 3]乘积 6不合法子段[3, 6]乘积 18不合法子段[2, 3, 6]乘积 36是6^2合法。所以答案是 1。这个“乘积是完全平方数”的条件在质因数分解的世界里有一个非常漂亮的等价说法对区间内所有数做质因数分解把每个质数的指数全部加起来如果每个质数的指数都是偶数那这个乘积就是完全平方数。换句话说我们完全不关心指数具体是多少只关心指数的奇偶性。偶数就是 0奇数就是 1。这一下就把一个乘法问题拉到了模 2 的世界里。1.2 为什么“乘积为平方数”可以变成“异或为 0”这是整道题最关键的一步推导我单独拎出来讲。假设我们给每个质数一个“状态位”比如质数2对应第 0 位质数3对应第 1 位质数5对应第 2 位……那么每个数都可以表示成一个二进制向量第 k 位表示“这个质数在这个数里出现了奇数次还是偶数次”。奇数记 1偶数记 0。于是mask(2)因为2 2^1只有 2 出现奇数次向量是000...001mask(3)向量是000...010mask(6)因为6 2^1 * 3^1两个质数都出现一次向量是000...011。现在关键来了两个数相乘对应质数的指数是相加的而相加之后再看奇偶其实是异或。也就是说mask(a * b) mask(a) xor mask(b)这个性质非常重要。它意味着我们可以像处理前缀和一样处理前缀异或。定义pref[i] mask(a[1]) xor mask(a[2]) xor ... xor mask(a[i])那么区间[l, r]的乘积向量就是pref[r] xor pref[l-1]如果区间乘积是完全平方数等价于这个向量全是 0等价于pref[r] xor pref[l-1] 0 pref[r] pref[l-1]所以题目瞬间变成统计有多少对前缀状态相等。再加一个空前缀pref[0] 0答案就是所有相同前缀状态里任选两个的组合数之和。这就是整道题的核心思路。理解了这一步这道题你已经会了一半。2. 从质因数分解到状态压缩2.1 朴素思考枚举区间为什么必挂拿到这种题第一反应肯定是枚举左右端点然后对区间内每个数做质因数分解维护所有质因子的奇偶性。但 n 的范围是 1e5区间数量就是 n(n1)/2大约 5e9 个区间每个区间还要做质因数分解。这个复杂度无论怎么优化都是不可能过的。所以必须走前缀这条路。用前缀状态把区间查询变成两个前缀状态的比较一下子把 O(n^2) 的枚举压缩成 O(n) 的扫描。但这又带来一个新问题前缀状态怎么存如果质因子种类很少比如只有 26 个字母那种题我们用一个 int 的 26 个二进制位就够了。可本题中 ai 最大到 1e9质因子的种类理论上可能非常多多到什么程度一个 1e9 以内的数最多有 9 个左右的不同质因子但 n 个数完全可以各自贡献一个不同的大质数。也就是说整个序列里可能出现的不同质因子数量最坏可以接近 n也就是 1e5 级别。用 1e5 个二进制位去表示一个状态每做一个前缀就要复制一份内存和时间都会爆炸。所以需要一个聪明的办法把状态压缩成轻量级的 key。2.2 用哈希压缩质因子奇偶状态竞赛里处理这种“动态出现、数量未知”的质因子集合最常用的做法就是随机哈希。具体做法是第一次遇到某个质数 p 时给它随机分配一个 64 位的整数h(p)。然后每个数的 mask 就是它所有出现次数为奇数的质因子的h(p)异或起来。因为异或满足结合律和交换律所以mask(a * b) mask(a) xor mask(b)依然成立。就是说我们不需要老老实实存 1e5 位的向量只要用一个unsigned long long就能表示一个前缀的奇偶状态。前缀计算也变成pref[i] pref[i-1] xor mask(a[i])统计答案时用一个unordered_mapunsigned long long, long long记录每个前缀状态出现过多少次一边扫描一边累加。整个过程极其干净。2.3 质因数分解的工程优化素数表解决完状态压缩还有一个隐藏的复杂度坑质因数分解本身。如果暴力从 2 试除到 sqrt(x)也就是最多到 31623每个数最坏要跑三万多次。n 是 1e5最坏就是 30 亿次取模这是必 TLE 的。正确做法是预处理一个 31623 以内的素数表。31623 以内的质数一共只有大约 3401 个。这样每个数最坏只需要试除 3401 个质数总次数降到 3.4 亿级别C 能在 1 秒左右跑完配合快速 IO 才能稳稳通过。素数表用一个最简单的埃氏筛就行代码也不长。这一步属于典型的“看着不起眼不加就 TLE”的工程优化后面踩坑部分我还会再提。3. 随机哈希这道题真正的考点3.1 为什么不能直接开 bitset 存状态有人可能会问既然质因子最多 1e5 种那我直接用一个bitset100000表示状态不行吗理论上可以但实际完全不可行。一个bitset100000就是 12.5KB每个前缀状态都存一份的话1e5 个前缀就是 1.25GB内存直接爆炸。就算不全部存下来只排序比较排序过程反复复制大 bitset 的时间也是天文数字。更关键的是我们根本不知道质因子的总种类数。它是边读入边出现的你没法在一开始就确定 bitset 的长度。动态扩容的 bitset 又慢又难写。所以随机哈希几乎是唯一现实的选择。它的本质是用一个极小概率的哈希冲突换取 O(1) 的状态比较。3.2 随机哈希原理与冲突分析给每个质数分配一个 64 位随机数这里的“随机”必须是真的随机最好是每次运行都不同。否则如果哈希映射关系固定出题人可以把数据构造到大量产生碰撞。为什么随机值就能保证正确性因为两个不同的奇偶向量它们的哈希值恰好相等的概率大约是 2^-64。n 1e5 时总共有大约 5e9 对前缀状态碰撞期望数量是5e9 / 2^64 ≈ 2.7e-10这个概率比比赛时电脑断电的概率还低实际做题完全不需要担心。当然如果心里实在过不去可以用双哈希给每个质数分配两个独立的 64 位随机值组成一个pairull, ull作为状态计数时用map。这样碰撞概率降到 2^-128属于理论上的“绝对稳妥”。但代价是代码更啰嗦、常数更大。我一般单哈希就够用了。3.3 稳一点双哈希方案双哈希的实现思路很简单把前面代码里的getHash改成返回两个随机值即可。状态 key 从ull换成pairull, ull计数容器从unordered_map换成map或者自定义一个 pair 的 hash。如果你追求极致的保险可以这样写struct Node { ull a, b; bool operator(const Node other) const { return a other.a ? b other.b : a other.a; } bool operator(const Node other) const { return a other.a b other.b; } };然后用mapNode, long long统计。不过实测单哈希在本题已经非常稳我最终 AC 的版本就是单哈希。4. 完整 C 代码与逐段解析4.1 AC 代码单哈希下面是完整可用的 AC 代码关键部分都加了注释。我建议你先自己抄一遍跑通再往下看逐段拆解。#include bits/stdc.h using namespace std; using ull unsigned long long; // 自定义哈希防止 unordered_map 被极端数据卡掉 struct CustomHash { static uint64_t splitmix64(uint64_t x) { x 0x9e3779b97f4a7c15ULL; x (x ^ (x 30)) * 0xbf58476d1ce4e5b9ULL; x (x ^ (x 27)) * 0x94d049bb133111ebULL; return x ^ (x 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x FIXED_RANDOM); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; // 预先生成 sqrt(1e9) 以内的质数表加速分解 const int LIM 31623; vectorbool isPrime(LIM 1, true); isPrime[0] isPrime[1] false; vectorint primes; for (int i 2; i LIM; i) { if (isPrime[i]) { primes.push_back(i); if (1LL * i * i LIM) { for (int j i * i; j LIM; j i) { isPrime[j] false; } } } } // 给每个质数随机分配一个 64 位哈希值 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); unordered_mapint, ull, CustomHash hashVal; hashVal.reserve(200000); auto getHash [](int p) - ull { auto it hashVal.find(p); if (it ! hashVal.end()) return it-second; ull h rng(); if (h 0) h 1; // 避免哈希值为 0影响奇偶判断 hashVal[p] h; return h; }; // 统计前缀状态出现次数空前缀状态为 0 unordered_mapull, long long, CustomHash cnt; cnt.reserve(200000); cnt[0] 1; long long ans 0; ull pref 0; for (int i 1; i n; i) { int x; cin x; // 对当前数分解质因数只把指数为奇数的质因子异或进 mask ull cur 0; for (int p : primes) { if (1LL * p * p x) break; if (x % p 0) { int c 0; while (x % p 0) { x / p; c; } if (c 1) cur ^ getHash(p); } } if (x 1) cur ^ getHash(x); // 更新前缀状态并计数 pref ^ cur; auto it cnt.find(pref); if (it ! cnt.end()) ans it-second; cnt[pref]; } cout ans \n; return 0; }4.2 关键代码段拆解第一个值得仔细看的是质因数分解部分。注意我并不是完整记录每个质因子的指数而是只关心指数是奇数还是偶数。对于指数为偶数的质因子它的奇偶性是 0异或上它没有任何影响所以可以直接跳过。这意味着12 2^2 * 3^1产生的cur只会异或hash(3)而不会异或hash(2)。这样写既节省时间也避免状态被无关质因子干扰。第二个关键点是getHash函数里的h 0特判。随机数生成器理论上可能生成 0如果某个质数的哈希值是 0那么这个质数的奇偶性就永远不影响任何状态严格来说是一个逻辑漏洞。概率极低但加一行判断成本几乎为零属于写了不亏的防御性代码。第三个关键点是计数顺序if (it ! cnt.end()) ans it-second; cnt[pref];先累加已经出现过的次数再把自己加进去这保证统计的每一对都是i j的前缀对不会出现同一个位置和自己配对的情况。如果反过来答案会凭空多出 n 个。5. 踩坑实录从 TLE、WA 到 AC5.1 为什么会 TLE分解方式不对我第一次提交 TLE 得非常冤枉因为代码逻辑完全正确问题就出在质因数分解上。我当时图省事直接写成for (int d 2; 1LL * d * d x; d) { ... }自以为每个数分解时 x 会不断变小循环能提前 break。但在极端数据下比如 n 1e5所有 ai 都是接近 1e9 的大质数每个数都要从头试除到 31623总循环次数接近 30 亿次TLE 是必然的。换用素数表之后同样数据只需要跑约 3.4 亿次速度提升接近 9 倍稳稳 AC。注意这不是特例。信奥里凡是涉及对多个数做质因数分解的题第一件事就是考虑要不要预处理素数表。 别等到 TLE 了才想起来。5.2 为什么会 WA类型溢出与边界处理WA 的坑主要集中在三个地方。第一答案变量要用long long。n 1e5 时全部子段数为 n(n1)/2 ≈ 5e9已经超过int的范围。如果忘了开long long大数据直接爆掉。第二剩余质因子的处理。分解完小于 sqrt(x) 的因子后如果 x 还大于 1说明剩下的 x 本身是一个大质数需要单独异或一次getHash(x)。但这里有个反向边界如果 x 原本就是 1分解循环直接退出剩余 x 还是 11不是质数不能异或。所以判断条件必须是if (x 1)而不是if (x ! 1)。虽然这两种写法在这道题里结果一样但逻辑上区分清楚能避免在其他题目里犯糊涂。第三哈希值为 0 的特殊处理。前文已经提过随机哈希值如果恰好为 0会让某个质因子失去作用导致该质因子出现次数为奇数的区间被误判为合法。虽然概率极低但在对拍大数据时确实可能成为唯一的 WA 来源。5.3 哈希冲突到底要不要怕很多刚开始接触随机哈希的选手会陷入一个焦虑万一两个不同的状态哈希冲突了怎么办我的答案是单 64 位随机哈希在 OI 常规数据范围内冲突概率可以忽略不计。你更需要担心的不是哈希冲突而是unordered_map被卡。这里说的“被卡”不是指哈希冲突而是指标准库的unordered_map在遭遇精心构造的 key 分布时可能退化到接近 O(n^2) 的复杂度。比如某些版本的 STL 内部用取模桶如果 key 是恶意构造的等差数列每次查找都可能踩到同一个桶。解决办法就是自己写一个 CustomHash把 key 做一次 splitmix64 扰动后再散列。这也是我上面代码里那个看起来很长的结构体的作用。这个技巧在洛谷很多题解里都有属于竞赛 C 选手的必备防身术。5.4 本地对拍验证模板随机哈希最怕的不是慢而是“感觉对了但答案偶尔不对”。所以本地对拍是必须的。我的对拍思路很简单写一个 O(n^2) 暴力程序再写一个随机数据生成器然后循环跑几百组数据比较两边的输出。暴力程序核心就几行long long brute(const vectorint a) { int n a.size(); long long ans 0; for (int l 0; l n; l) { vectorint cnt(100, 0); // 只处理小范围数据 for (int r l; r n; r) { int x a[r]; for (int p 2; p * p x; p) { while (x % p 0) { x / p; cnt[p] ^ 1; } } if (x 1) cnt[x] ^ 1; bool ok true; for (int v : cnt) if (v) { ok false; break; } if (ok) ans; } } return ans; }生成器就随机生成 n 在 1 到 10、ai 在 1 到 30 的小数据。然后写个脚本循环对拍。如果小数据跑 500 组全对基本上代码逻辑和哈希安全性就都稳了。这个对拍习惯强烈建议养成。信奥里很多“看起来对了但交上去 WA”的题都是靠对拍揪出隐藏 bug 的。6. 这类题的通法总结与扩展6.1 套路识别看到“偶数次/平方数/奇偶性”怎么想刷题多了你会发现信息学竞赛特别喜欢把“奇偶性”和“前缀”组合在一起出题。一旦题目里出现这些关键词脑子里就要立刻拉响警报出现“每个质因子出现次数为偶数”“乘积为完全平方数”这类说法先想质因数分解再想模 2 状态向量出现“区间统计”先想能不能用前缀状态把区间变成两个端点的比较出现“状态数量未知、可能很多”先想随机哈希最后看到“统计相等状态对”就是C(cnt, 2)累加。这条链路就是 P6273 的全部骨架。下次再遇到类似的题哪怕题目换了一层壳也能快速套上这个思考框架。6.2 两道同套路变式这个套路最常见的变式是第一统计一个字符串中有多少子串使每个字符出现次数都是偶数。因为字符集只有 26 个所以不用哈希直接用一个 int 的 26 位当状态前缀异或之后用数组计数就行。第二在本题基础上改条件统计有多少子段使得恰好有 k 个质因子的出现次数为奇数。做法是维护前缀哈希状态然后对每个前缀去查询它异或上所有“恰好 k 位置为 1”的掩码后得到的值出现过多少次。这个就要用unordered_map配合枚举了复杂度会多一个组合系数但思想完全一致。你看一个套路吃透能打一片题。6.3 我的刷题心得最后说点个人体会。我做这道题最大的收获不是学会了随机哈希这个技术点而是明白了“先推数学再写代码”的价值。第一次做的时候我直接上手写暴力写完发现不对第二次想用 bitset写完发现内存爆炸直到我老老实实把“乘积为平方数”翻译成“前缀异或相等”代码反而半小时就写完了。动笔之前先想清楚转化关系永远比盲目调代码省时间。P6273 的“魔法”不在题目本身而在那个“把所有数的乘积拉回质因数指数奇偶性”的瞬间。你如果也想通了这一点这题就真的学会了。