某道毒瘤题的做题记录

(text{ABC 238 G})

题意

给定一个序列 (a)，和 (q) 次询问，每次询问询问是否有

[exists k in mathbb N, prod_{i=l}^r a_i = k^3 ]

非正解

显然可以对 (a_i) 进行质因数分解，并预处理出每个质因数的前缀和，则可以在 (mathcal O(n^{1.5} + q times dfrac {a}{ln a})) 的时间内暴力解决。
注意到做的前缀和相当于三进制不进位加法，则定义 (A_i) 为 (A) 中三进制位为 (i) 的位编号的集合，
则会有

[(A oplus B)_0 = (A_0 cap B_0) cup (A_1 cap B_2) cup (A_2 cap B_1) ]

[(A oplus B)_1 = (A_1 cap B_0) cup (A_0 cap B_1) cup (A_2 cap B_2) ]

[(A oplus B)_2 = U - (A oplus B)_0 - (A oplus B)_1 ]

，(tt bitset) 优化即可，时间复杂度：(mathcal O(n^{1.5} + q times dfrac {a}{omega ln a}))，其中 (omega approx 10)。

题解

考虑用哈希函数解决本题。如果存在一个函数 (f(x) : mathbb N^{mathcal O(a/ln a)} to mathbb N)（输入实际上是质因数分解），满足 (f(a + b) = f(a) + f(b))，且存在一个性质 (P(x))，使得 (P(f(x))) 是 (x) 对应的整数是立方数的必要条件，就称 (f) 是一个哈希函数。
于是，对于任意的 ({x_i})，有

[f(a) := sum_{i=1}^{} x_ia_i ]

是哈希函数。
证明：
(P(k) iff 3 mid k)：如果 (a) 对应的整数是立方数，则有 (forall i, 3 mid a_i)，此时，(f(a)) 的每一项都 (equiv 0 pmod 3)，故成立。
线性性成立：

[sum_{i=1}^{} x_ia_i + sum_{i=1}^{} x_ib_i = sum_{i=1}^{} x_i (a_i + b_i) = f(a+b) ]

。
我们来分析哈希函数的正确率：
对于一个如上构造的哈希函数 (f)，设一个区间是立方数的概率为 (p)，则有

概率表	是立方数	非立方数
预测正确	(p)	(dfrac 23)
预测错误	(0)	(dfrac 13-p)

，准确率 = (dfrac{{准确预测}}{{总预测}} = p + dfrac 23 ge dfrac 23)，失误率 (le dfrac 13)，就定义最高失误率 (l := dfrac 13)。
设我们有 (h) 个哈希函数，则 (h) 个哈希函数都失误的概率为 (l^h)，定义 (L := l^h)。因为我们有 (Q) 次询问，则至少有一个哈希函数失误的概率为 (1 - (1 - L)^Q)，我们将证明这个柿子 (le QL)：
数学归纳法：

• (Q = 1) 时左 (= 1 - (1 - L) = L)，右 (= 1L = L)（总不可能零次询问吧）
• (Q gt 1) 时：
  进行移项，化为 ((1 - L)^Q ge 1 - QL)，进行变换：
  (begin{array}{l} (1 - L)^Q ge 1 - QL \ (1 - L)^{Q - 1} (1 - L) ge 1 - QL \ (1 - L)^{Q - 1} ge 1 - (Q - 1)L \ (1 - (Q - 1)L) (1 - L) ge 1 - QL \ 1 - (Q - 1)L - L(1 - (Q - 1)L) = 1 - QL + (Q - 1)L ge 1 - QL end{array})
  证毕。

设有 (c) 个测试点，则失误率 (le c times q times l^h)。
于是让我们来计算一下时间复杂度：

1. 质因数分解 (mathcal O(na^{0.5}))
2. 预处理前缀和 (mathcal O(h log a))（考虑到一个数的质因数分解最多为 (2 times cdots times 2)）
3. 询问 (mathcal O(qh))

总时间复杂度 (mathcal O(na^{0.5} + h(log a + q)))。
考虑到时限为 (rm 3s)，可以取 (h = 300)。
可以通过。（其实这 (h) 个哈希函数也可以状压，大概会有 (dfrac 1omega) 的常因子优化）