Advertisement
playerr17

Untitled

Jan 10th, 2023
143
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.85 KB | None | 0 0
  1. const int mod = 1e9 + 7;
  2. int p[100100];
  3.  
  4. string gen_str() {
  5.     string s;
  6.     forn(i, 0, 20) {
  7.         s += 'a' + rnd() % 26;
  8.     }
  9.     return s;
  10. }
  11.  
  12. int get_hash(string s, int start) {
  13.     int h = 0;
  14.     forn(i, 0, sz(s)) {
  15.         h = (h * 1ll * p[1] + s[i] - 'a' + 1) % mod;
  16.     }
  17.     h = h * 1ll * p[start] % mod;
  18.     return h;
  19. }
  20.  
  21. void solve(){
  22.     int P, h;
  23.     cin >> P >> h;
  24.     forn1(i, 0, 100000) {
  25.         p[i] = (i == 0 ? 1 : p[i - 1] * 1ll * P % mod);
  26.     }
  27.     unordered_map<int, string> st;
  28.     forn(i, 0, 1e5) {
  29.         string a = gen_str();
  30.         st[get_hash(a, 20)] = a;
  31.     }
  32.     forn(i, 0, 1e5) {
  33.         string a = gen_str();
  34.         int hash = get_hash(a, 0);
  35.         if (st.contains((h - hash + mod) % mod)) {
  36.             cout << st[(h - hash + mod) % mod] << a << endl;
  37.             return;
  38.         }
  39.     }
  40. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement