题目
题意：给定一个字符串 $s$，求不同于 $s$ 的字符串 $t$，使得 $Hash(s) = Hash(t)$，其中 $displaystyle Hash(s) = sum_0^{len-1} x_i imes p^i$，$4 leq p,m leq 10^9$ 且$m$为质数，所有输入输出的字符串内的字符ASCII码的取值范围为 $[31, 126]$.
分析
由于最终哈希值会模 $m$，所以最多 $m$ 种哈希值，可以先建立起 $sqrt m$ 个不同哈希值的表。
具体的，利用枚举3位字符串得到 $(126-31)^3 approx 10^6$个字符串的哈希值，用map存，近似达到 $sqrt m$ 个哈希值。
先从表中选取一个字符串作为高3位，计算出低3位哈希值应该为多少，在从表中查找这个值，找到一个就退出，最多执行 $10^6$ 次。
那么单次不击中（没找到）的概率为 $displaystyle frac{m - sqrt m}{m}$，因此连续 $10^6$ 次不击中的概率为 $(frac{m - sqrt m}{m})^{1e6} = 0.00004539$，这个概率非常小，可认为总能找到答案
#include<bits/stdc++.h> using namespace std; typedef long long ll; map<int, string>mp; vector<ll>vec; const int L = 33, R = 136; ll p, m; string str; //97^3组哈希值，达到sqrt(m) void dfs(int pos, ll v, ll pw, string s) { if(pos >= 4) { mp[v] = s; //hash(s)=v vec.push_back(v); return; } for(int i = L;i <= R;i++) dfs(pos+1, (v + i * pw)%m, (pw * p) % m, s + (char)(i)); } //查找哈希值x是否存在 bool find(ll x) { auto it = lower_bound(vec.begin(), vec.end(), x); return it != vec.end() && (*it == x); } //求hash(s) ll Hash(string s) { ll ans = 0; ll pw = 1; for(auto ch : s) { ans += (ll)ch * pw; ans %= m; pw = pw * p % m; } return ans; } int main() { cin >> p >> m >> str; ll h = Hash(str); //printf("hash: %lld ", h); dfs(1, 0, 1, ""); sort(vec.begin(), vec.end()); // ll pw = 1; for(int i = 1;i <= 3;i++) pw = pw * p % m; for(auto i : vec) { ll v = (h - (i * pw) % m + m) % m; if(find(v)) { //string t=mp[v]+mp[i]; //printf("hash2: %lld ", Hash(t)); cout << mp[v] << mp[i] << endl; return 0; } } }