这个题是刚考挂 CSP 回来写的。
Idea：lxl Solution：lxl Std：lxl Data：lxl
对这题的评价：4/11
题意简述
一个长为 $n$ 的整数序列， $m$ 次查询。每次给出 $l, r, p$ ，查询区间 $[l,r]$ 中所有子序列分别去重（即一个子序列中出现多次的数只留下一个）后的和 $\bmod\ p$ 。
$1\le n, m, a_i\le 10^5, 1\le p\le 10^9$ ，不强制在线。
主要思路
一个长度为 $len$ 的询问，如果一个数 $x$ 出现了 $k$ 次，对答案的贡献是 $x(2^{len - k}(2^k - 1))$ 。
$2^{len - k}$ 是除了 $x$ 以外的数的子序列个数， $2^k - 1$ 是所有 $x$ 构成的子序列中包含 $x$ 的种数。
把出现个数为 $i$ 的数的和记为 $s_i$ ，则只需要维护 $s$ 即可。
肯定是离线下来莫队，但是模数不同不好求答案。
发现出现个数大于 $\sqrt{n}$ 的数的个数不会超过 $\sqrt{n}$ ，所以将出现次数大于 $\sqrt{n}$ 的数用一个东西来维护，复杂度就是单次 $O(\sqrt{n})$ 的了。
然后快速幂要用那种 $O(\sqrt{n})$ 预处理 $O(1)$ 求幂次的方法（就是处理 $2^0, 2^1, 2^2, \dots, 2^{\sqrt{n}}$ 和 $2^{\sqrt{n}}, 2^{2\sqrt{n}}, \dots, 2^{n}$ ）。
出现次数大于 $\sqrt{n}$ 的数可以用哈希表来维护。 unordered_set 居然没被卡。
于是就时间复杂度 $O((n + m)\sqrt{n})$ ，空间复杂度 $O(n)$ 了。
参考代码
1 |
|