某道毒瘤题的做题记录 - lhx_Oier
source link: https://www.cnblogs.com/lhx-oier/p/16754608.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
某道毒瘤题的做题记录
ABC 238 G
给定一个序列 a，和 q 次询问，每次询问询问是否有
∃k∈N,∏i=lrai=k3
显然可以对 ai 进行质因数分解，并预处理出每个质因数的前缀和，则可以在 O(n1.5+q×alna) 的时间内暴力解决。
注意到做的前缀和相当于三进制不进位加法，则定义 Ai 为 A 中三进制位为 i 的位编号的集合，
则会有
，bitset 优化即可，时间复杂度：O(n1.5+q×aωlna)，其中 ω≈10。
考虑用哈希函数解决本题。如果存在一个函数 f(x):NO(a/lna)→N（输入实际上是质因数分解），满足 f(a+b)=f(a)+f(b)，且存在一个性质 P(x)，使得 P(f(x)) 是 x 对应的整数是立方数的必要条件，就称 f 是一个哈希函数。
于是，对于任意的 {xi}，有
是哈希函数。
证明：
P(k)⟺3∣k：如果 a 对应的整数是立方数，则有 ∀i,3∣ai，此时，f(a) 的每一项都 ≡0(mod3)，故成立。
线性性成立：
。
我们来分析哈希函数的正确率：
对于一个如上构造的哈希函数 f，设一个区间是立方数的概率为 p，则有
| 概率表 | 是立方数 | 非立方数 |
|---|---|---|
| 预测正确 | p | 23 |
| 预测错误 | 0 | 13−p |
，准确率 = 准确预测总预测准确预测总预测=p+23≥23，失误率 ≤13，就定义最高失误率 l:=13。
设我们有 h 个哈希函数，则 h 个哈希函数都失误的概率为 lh，定义 L:=lh。因为我们有 Q 次询问，则至少有一个哈希函数失误的概率为 1−(1−L)Q，我们将证明这个柿子 ≤QL：
数学归纳法：
- Q=1 时左 =1−(1−L)=L，右 =1L=L（总不可能零次询问吧）
- Q>1 时：
进行移项，化为 (1−L)Q≥1−QL，进行变换：
(1−L)Q≥1−QL(1−L)Q−1(1−L)≥1−QL(1−L)Q−1≥1−(Q−1)L(1−(Q−1)L)(1−L)≥1−QL1−(Q−1)L−L(1−(Q−1)L)=1−QL+(Q−1)L≥1−QL
证毕。
设有 c 个测试点，则失误率 ≤c×q×lh。
于是让我们来计算一下时间复杂度：
- 质因数分解 O(na0.5)
- 预处理前缀和 O(hloga)（考虑到一个数的质因数分解最多为 2×⋯×2）
- 询问 O(qh)
总时间复杂度 O(na0.5+h(loga+q))。
考虑到时限为 3s，可以取 h=300。
可以通过。（其实这 h 个哈希函数也可以状压，大概会有 1ω 的常因子优化）
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK