w33z Round 2 A

w33z8kqrqk8zzzx33 · 2021-01-20 11:07:28 · 题解

观察到在纯暴力里面，栈永远仅包含 01 值，操作也全是 01 值操作，相对浪费。
于是可以 \omega 个求值处一起计算；将当前状态用一个 unsigned long long 等结构绑起来。
对每一个 \omega 求值块，处理出来在这个块里的所有变量在块里所含有的值，用一个类似与转置的方法，可以 O(\omega^2) 暴力解决。 最后，可以直接用栈模拟这一块，和暴力本质没区别。
整体时间复杂度 O(nm/\omega)。