Hash Killer Phantasm

_H17_ · 2025-04-28 13:57:22 · 题解

题目分析

哈希冲突的概率可以转化为生日悖论，相当于有 p 天，同时有 n 个人，求生日相同的概率。

根据生日悖论的结论：有 n 天，其中有相同生日的人时，期望总人数是 O(\sqrt{n}) 的（具体证明见 OI-wiki）。

根据生日悖论，模数是 p 的哈希期望上需要 O(\sqrt{p}) 次，所以随即多个字符串依次判断，期望时间复杂度 O(l\times\sqrt{p}\log{p})。

其中 O(\log p) 是 map 的时间复杂度，可以用哈希优化。

这里 l 别太小，有随机性即可（注意下文由于是类似 \texttt{01} 串的东西，所以 l 应该取大一点）。

但是我们需要卡双哈希，很显而易见的是：对于两个卡掉 b_1,p_1 的字符串 x,y，把它们当作两个字符（显然这两个串是在 b_2,p_2 哈希意义下不同的，但是一直可以卡 b_1,p_1，所以可以当字符）。

然后我们使用同样的方法把 x,y 当作字符进行随机，搞出一个也满足 b_2,p_2 的即可。

时间复杂度 O(l\times \sqrt{n}\log n)。

其中 O(\log n) 是 map 的时间复杂度，可以用哈希优化。

代码

#include<bits/stdc++.h>
using namespace std;
int b1,p1,b2,p2;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<char>randchar('a','z'),randindex(0,1);
int strhash(string s, int b, int p) {
    int val = 0;
    for (int i = 0; i < s.length(); i++)
        val = (1ll * val * b + s[i] - 'a' + 1) % p;
    return val;
}
map<int,string>hashval1,hashval2;
string x,y;
string randstring1(int len=7){//生成字符串
    string s;
    for(int i=1;i<=len;i++)
        s+=randchar(rnd);
    return s;
}
bool check1(string s,string&x,string&y){//检查第一个哈希
    int hashv=strhash(s,b1,p1);
    if(hashval1.count(hashv)){
        x=s,y=hashval1[hashv];
        if(x==y){
            x=y="";
            return 1;
        }
        return 0;
    }
    hashval1[hashv]=s;
    return 1;
}
string randstring2(int len=37){//对“字符”生成字符串
    string s;
    for(int i=1;i<=len;i++)
        s+=(randindex(rnd)?x:y);
    return s;
}
void check2(string s){//检查第二个哈希
    int hashv=strhash(s,b2,p2);
    string x,y;
    if(hashval2.count(hashv)){
        x=s,y=hashval2[hashv];
        if(x==y)
            return;
        cout<<x<<'\n'<<y;
        exit(0);
        return;
    }
    hashval2[hashv]=s;
    return;
}
int main(){
    cin>>b1>>p1>>b2>>p2;
    while(check1(randstring1(),x,y));//找“字符”
    while(1)
        check2(randstring2());
    return 0;
}