P3396 哈希冲突 题目链接 从这篇博客来做的这道题 分析： 看到这个题的数据范围是有点懵，这能怎么做啊？ 先看暴力 O ( n 2 ) O(n^2) O(n2) ， for (int i = x; i <= n; i += p)ans += value[i]; 如果我们做预处理的话， a n s [ p ] [ x ] ans[p][x] ans[p][x] ， % p \%p

P3396 哈希冲突 题目背景 众所周知，模数的 hash 会产生冲突。例如，如果模的数 p = 7 p=7 p=7，那么 4 4 4 和 11 11 11 便冲突了。 题目描述 B 君对 hash 冲突很感兴趣。他会给出一个正整数序列 value \text{value} value。 自然，B 君会把这些数据存进 hash 池。第 value k \text{value}_

https://www.luogu.com.cn/problem/P3396 思路：先考虑暴力怎么做，用 a n s [ i ] [ j ] ans[i][j] ans[i][j]记录在 m o d i mod\ i mod i的情况下第 j j j组的答案，显然我们在可以 O ( n 2 ) O(n^2) O(n2)的时间复杂度下预处理出来，空间复杂度也是 O ( n 2 ) O(n^2)