P3396 哈希冲突¶
思路：对于 \(p>\sqrt n\) ，余 \(k\) 的池子里面最多不超过 \(\sqrt n\) 个元素，可以暴力。对于 \(p<\sqrt n\)，我们换一种处理思路：
1 | |
这样的修改也是 \(O(\sqrt n)\) 的，预处理需要 \(O(n\sqrt n)\) ，故时间复杂度为 \(O((n+m)\sqrt n)\) 。
思路：对于 \(p>\sqrt n\) ，余 \(k\) 的池子里面最多不超过 \(\sqrt n\) 个元素，可以暴力。对于 \(p<\sqrt n\)，我们换一种处理思路：
1 | |
这样的修改也是 \(O(\sqrt n)\) 的，预处理需要 \(O(n\sqrt n)\) ，故时间复杂度为 \(O((n+m)\sqrt n)\) 。