1746F

考虑出现次数都是 \(k\) 的倍数存在必要条件：区间总和为 \(k\) 的倍数。 如果给每个正整数 \(i\) 都赋随机数 \(a_i\) 并对每次查询求区间和，错误的概率大概为 \(\frac{1}{k}\)。 跑 \(30\sim 40\) 次即可，时间复杂度为 \(O(Tn\log n)\) ......

对集合的一些判断可以考虑随机化哈希。 给每个数随一个权，如果集合 \(S\) 中每个数的出现次数都是 \(k\) 的倍数，那 \(S\) 中元素的权值之和就会是 \(k\) 的倍数，否则会是一个在 \([0,k)\) 中随机的值。 也就是说如果这个集合不满足要求，我们做一次这个检测，有 \(\fra ......

prologue 数组范围一定要看好了开，不然容易我一样，调试调了一页多。 还有就是不要傻乎乎地只跑一次和哈希，因为和哈希（从下面地佬的题解中才知道）它其实算作是一种 trick（类比SA（Stimulate_anneal）。 analysis 这个题目的第二个询问时询问一个区间里面出现过的正整数的 ......

[题目链接](https://codeforces.com/problemset/problem/1746/F)。 这个数据范围，显然出题人出这题的本意不是让我们用带修莫队过题（当然有人过），而我们又难以找到很好的 $\text{DS}$ 维护方法。 故考虑另辟蹊径。对于所有 $a_i,x$，不妨把 ......