自动搬运

查看原文

来自洛谷，原作者为

	undefined_Ryan 这个家伙很懒，什么也没有留下

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

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

以下是正文

啊？这题是数学构造？

$p\le10^9+7$，由生日悖论，直接随机即可。取 $n=20$，期望时间复杂度 $O(n\sqrt p)$。

#include <bits/stdc++.h>
using namespace std;
int b,p,k;
string rnd(int n) {
    string s;
    for (int i=1;i<=n;++i) s+=char(rand()%26+'a');
    return s;
}
int strhash(const 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;
}
string s;
unordered_map<int,string> mp;
int main() {
    cin>>b>>p;
    while (s=rnd(20),k=strhash(s,b,p)) {
        if (mp.count(k)&&mp[k]!=s) {
            cout<<mp[k]<<endl<<s<<endl;
            break;
        }
        else mp[k]=s;
    }
}