P11431 [COCI 2024/2025 #2] 差异 / Različitost 题解

前言

来点不带脑子的做法，但有点卡常，在 COCI 的土豆评测机上过不去。

思路

不妨设 $n\leq m$，且下文的所有下标均从 $0$ 开始。

看见异或还要求和可以先拆位。

拆位后考虑对于每个 $a_i$ 求出其贡献，设 $f_{i,j}$ 为第 $i$ 个数在第 $j$ 次出现时会与谁异或，则有 $f_{i,j}=(f_{i,j-1}+n)\mod m$，初始状态为 $f_{i,0}=i$。看到这种东西可以直接倍增，设 $sum_{i,j}$ 代表 $a_i$ 第 $j$ 次出现时当前位已经累计遇到了多少个 $1$（那么 $0$ 的个数就是 $2^j$ 减去 $1$ 的个数），则有 $sum_{i,j}=sum_{i,j-1}+sum_{f_{i,j-1},j-1}$。

于是对于 $a_i$，其在最终序列中的出现次数为 $\lfloor\frac{k}{n}\rfloor+[i< (k\mod n)]$，倍增算完 $sum$ 数组后直接统计即可，复杂度是 $\mathcal{O}(n\log^2 V)$。

时限不怎么宽裕，但在 lg 评测机上压力不大。