\(\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\) 的位編號的集合，
則會有
，\(\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\}\)，有
是哈希函式，
證明：
\(P(k) \iff 3 \mid k\)：如果 \(a\) 對應的整數是立方數，則有 \(\forall i, 3 \mid a_i\)，此時，\(f(a)\) 的每一項都 \(\equiv 0 \pmod 3\)，故成立，
線性性成立：
，
我們來分析哈希函式的正確率：
對于一個如上構造的哈希函式 \(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\)，
于是讓我們來計算一下時間復雜度：
- 質因數分解 \(\mathcal O(na^{0.5})\)
- 預處理前綴和 \(\mathcal O(h \log a)\)（考慮到一個數的質因數分解最多為 \(2 \times \cdots \times 2\)）
- 詢問 \(\mathcal O(qh)\)
總時間復雜度 \(\mathcal O(na^{0.5} + h(\log a + q))\)，
考慮到時限為 \(\rm 3s\)，可以取 \(h = 300\)，
可以通過，（其實這 \(h\) 個哈希函式也可以狀壓，大概會有 \(\dfrac 1\omega\) 的常因子優化）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/510992.html
標籤：其他
下一篇：leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal 從中序與后序遍歷序列構造二叉樹(中等)