Madoka 酱亲亲！ | 【解题报告】P11431 [COCI 2024/2025 #2] 差异 / Različitost

HomuraAkemi · 2024-12-20 20:34:23 · 题解

拆位是平凡的。接下来只需要考虑 01 序列上的问题。

显然 c_i=a_i\oplus b_i 这个序列的循环节长度为 \operatorname{lcm}(n,m)。对于长度为 \operatorname{lcm}(n,m) 的整段是不难拆贡献后计算的，接下来只需要考虑长度 \lt \operatorname{lcm} 的散段。

经典结论就是 x\to (x+n)\bmod m 连边会形成若干个环，每个环长为 m/\gcd(n,m)（证明留作练习）。然后注意到每一个环的含义是：a_i 第一次匹配的是 b_i，第二次是 b_{(i+n)\bmod m}，依此类推。那么直接计算它能取到几次，然后利用环上前缀和计算即可。

细节较多，代码实现较为繁琐。精细实现的话，时间复杂度 \Theta((n+m)\log V)。

Madoka 酱可爱，亲亲 Madoka 酱！