P9737 题解

masonpop · 2023-11-09 11:38:35 · 题解

注意翻译有误，下标从 0 开始。

暴力是 O(n^2m^2k)，爆炸。发现这个判断矩形是否合法耗费了大量时间。

要么 0 个，要么 2 个，想到了什么？异或。如果给每对点随机权值，那么这差不多等价于矩形内异或和为 0。碰撞概率极低，预处理异或前缀和即可做到 O(n^2m^2+k)。

但这样还是过不了。考虑用科技优化那个 n^2m^2 的枚举。枚举左右所在的列，然后处理出这个范围内每一行的异或和。此时就是这样一个问题：选择一个长度至少为 2 的子序列使其异或和为 0，问选法数。这是经典问题吧，预处理异或前缀和后开个桶就行了。

复杂度 O(n^2m\log m+k)。代码不放了。