题解：P12201 Hash Killer Phantasm

· · 题解

这个题非常简单，只需要暴力就行了，根本用不着构造。

根据生日悖论，只需要随 \sqrt{p} 个字符串就会出现哈希相同的字符串。所以先随出一组在 (b_1,p_1) 下冲突的字符串，再以它们两个为字符集，随机生成新的字符串。不难发现，生成的所有字符串在 (b_1,p_1) 下都是冲突的，因为它们的组成部分的哈希都是一样的，接着随出在 (b_2,p_2) 下冲突的字符串就行了。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

mt19937 rnd(random_device{}());

string str_rand(int n){
    string ans;
    for (int i=0;i<n;i++) ans.push_back(rnd()%26+'a');
    return ans;
}

string str_rand2(int n,const string &s1,const string &s2){
    string ans;
    for (int i=0;i<n;i++) ans+=(rnd()&1?s1:s2);
    return ans;
}

int strhash(const string &s,int b,int p){
    int val=0;
    for (int i=0;i<int(s.length());i++) val=(1ll*val*b+s[i]-'a'+1)%p;
    return val;
}

unordered_map<int,string> mp;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int b1,p1,b2,p2;
    cin>>b1>>p1;
    string s1,s2;
    while (true){
        string s=str_rand(7);
        int h=strhash(s,b1,p1);
        auto it=mp.find(h);
        if (it!=mp.end() and it->second!=s){
            s1=it->second;
            s2=s;
            break;
        }else{
            mp[h]=s;
        }
    }
    mp.clear();
    cin>>b2>>p2;
    while (true){
        string s=str_rand2(32,s1,s2);
        int h=strhash(s,b2,p2);
        auto it=mp.find(h);
        if (it!=mp.end() and it->second!=s){
            cout<<it->second<<"\n"<<s;
            // cout<<"\n";
            // cout<<strhash(it->second,b1,p1)<<" "<<strhash(s,b1,p1)<<"\n";
            // cout<<strhash(it->second,b2,p2)<<" "<<strhash(s,b2,p2)<<"\n";
            break;
        }else{
            mp[h]=s;
        }
    }
    return 0;
}

后记：题目中计算字符串哈希的代码会爆警告，建议改一下。