洛谷 P3396 哈希冲突

Vanilla_chan · 2021-04-02 09:26:15 · 题解

Problem

P3396 哈希冲突

Solution

本文摘自基础数据结构学习笔记

先想两种极端的做法

• 对于每个询问，暴力计算k,k+p,k+2\times p\dots的value之和。
• 预处理出ans[p][k]表示在\bmod p的意义下，余数为k的value之和。

第一种方法时间\rm O(n^2)，空间\rm O(1)；第二种方法时间\rm O(1)，空间O(n^2)。

考虑根号分治。

对于p\le \sqrt n，我们预处理，保存在数组ans[p][k]中。空间\rm O(\sqrt n\times\sqrt n)=\rm O(n)，时间上预处理\rm O(n\sqrt n)，修改\rm O(\sqrt n)，查询\rm O(1).

对于p>\sqrt n，我们不预处理，每一次询问暴力统计。每次统计的数量不会超过\dfrac np\le \sqrt n.

Code