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

拆位是平凡的。接下来只需要考虑 $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 酱！