MCOI R4 D

w33z8kqrqk8zzzx33 · 2020-08-08 16:46:41 · 题解

D：【Dream and Strings】

m=997 部分分

当 S 随机，H(S) 函数可以看做一个随机在 [0,m) 里面的数。

如果随机选取长度为 |S| 的字符串，选出来的字符串是一个哈希碰撞可能性大概就是 \frac{1}{m}。

计算期望，得到需要的选取次数是 m。

时间复杂度是期望 O(|S|*m)；如果采用 dfs 那么可以达到期望 O(m)。

正解

首先，把 |S| 长度降低到 50 来让 O(|S|*m) 降低到 O(m)。可以把 S 的长度为 |S|-50 后缀保持一样，直接固定前 50 字符的哈希一样。

考虑以上的拓展：如何快速选出来一大堆随机字符串呢？来选出来 O(n) 个字符串，不一定需要 O(n) 的时间，因为存在更好的字符串表示方法。

例如如果造出来 O(\sqrt n) 个前缀以及 O(\sqrt n) 个后缀，会形成 O(n) 个字符串，但是只需要 O(\sqrt n) 的时间来构造和判断有没有构造一个哈希值。

具体方法：

• 用任意方法构造 O(\sqrt{m}) 级别的长度为 25 的前缀以及它们的哈希
• 用任意方法构造 O(\sqrt{m}) 级别的长度为 25 的后缀以及它们的哈希
• 注意给定长度为 25 的前缀的哈希与长度为 25 的后缀的哈希，长度为 50 的整体哈希等于 (P\cdot b^{25}+S)\bmod m
• 有 T；想要 P\cdot b^{25}+S\equiv T\pmod m
• 等价 T-P\cdot b^{25}\equiv S\pmod m
• 对所有 S 存一个 set 或者 unordered_set；这样可以直接 O(1) 或者 O(\log\sqrt n) 时间找到存在不存在一个 S 来把前缀补成 m。

为了安全，std 固定生成 2\times10^5 个前缀和后缀。

可以这样分析成功概率。我们将前缀和后缀抽象为均匀随机函数，整体哈希自然也是均匀随机函数。没有一个碰撞的概率是

其中 Q 为产生前缀后缀数量。想要

则