自动搬运

查看原文

来自洛谷，原作者为

	bcdmwSjy ‎

搬运于2025-08-24 23:13:40，当前版本为作者最后更新于2025-04-19 16:43:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

根据生日悖论，只需要随 $\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;
}

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