题解：P12060 [THUPC 2025 决赛] Now or Never

紊莫 · 2025-05-30 08:21:05 · 题解

首先利用 bitset 建立线性基，对于一个查询，我们有如下贪心：

设当前位为 i，如果 [i,m) 这些位都可以消成 0，那么退出，否则尽可能把 i 这个位变成 1，然后 i\gets i+1。

正确性显然，暴力做复杂度是 O(\frac{nm^2+qm^3}{\omega}) 的。

暴力代码。

称线性基中能被我们随意操作的位为关键位。

那么我们只需要把线性基消元成关键位独立的形式就可以预处理所有后缀的关键位上的基中元素的异或和。

正解代码。

复杂度是 O(\frac{nm^2+qm^2}{\omega})。