题解：P12201 Hash Killer Phantasm

· · 题解

只要随机生成 \sqrt p 个字符串就会出现哈希值相同的字符串（这里涉及一个数学概率论中一个有趣的悖论：birthday paradox），所以随机生成字符串并检验，数量级可以接受。先考虑其中一组哈希，随机拼接字母 a 到 z 生成字符串并用一个 map 维护是否存在此前生成的字符串与新生成的字符串哈希值相同，并随时记录每个哈希值所对应的字符串，直到获得一组配对，再每次随机选择这对字符串中的一个拼接出一个新的字符串，这样可以保证第一组哈希值保持相同，得到第二组配对。尝试不同的参数作为两次生成的字符串的长度，实测很多都能通过（比如我用的 11 和 45）。使用 mt19937 rnd(random_device{}()) 实现。