模意义 01 背包的快速做法

cyffff · 2025-04-21 18:59:10 · 算法·理论

来自 [[广东省队集训 2025] 操作]()。

记模数为 m。

考虑加入一个数，这会让我们执行两次对位或操作，其中对位或操作为指定两个长度相等的区间 [l_1,r_1],[l_2,r_2]，将前者中为一的位置在后者中的对应位置也标一。

考虑分治，将两个区间均分作两段并分别递归，若执行对位或操作的区间完全相等则返回。

考虑这样做的时间复杂度，每出现对位的 (1,0)，整个数组中的 1 的数量就会减少 1，根据势能分析递归总次数即为 O(m\log m)。

但是还有可能出现对位 (0,1)，这会导致上述分析出现一些问题。考虑我们是模意义 01 背包，不断加 v 会出现若干个环，那么每一组的对位 (0,1) 均会在其环上对应一组对位 (1,0)，故势能分析依然正确。

使用树状数组维护区间哈希值判区间相等，时间复杂度 O(m\log^2 m)。