QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#560312#669. Hashucup-team1198#ML 0ms0kbC++201.9kb2024-09-12 15:05:322024-09-12 15:05:34

Judging History

This is the latest submission verdict.

  • [2024-09-12 15:05:34]
  • Judged
  • Verdict: ML
  • Time: 0ms
  • Memory: 0kb
  • [2024-09-12 15:05:32]
  • Submitted

answer

#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

int MOD;

int add(int a, int b) {
  return a + b >= MOD ? a + b - MOD : a + b;
}

int sub(int a, int b) {
  return a >= b ? a - b : a + MOD - b;
}

int mul(int a, int b) {
  return (1ll * a * b) % MOD;
}

int B;

int get_h(string s) {
  int h = 0;
  for (auto ch : s) {
    h = add(mul(h, B), ch - 'a' + 1);
  }
  return h;
}

const int MAXMOD = 1e9;
string mem[MAXMOD / 25 + 1];
int h[MAXMOD / 25 + 1];

string s;

void go(int hsh) {
  if ((int)s.size() == 6) {
    hsh = mul(hsh, B);
    int id = hsh / 25;
    if (!mem[id].empty()) {
      string t = mem[id];
      int h1 = h[id];
      s.push_back('a');
      t.push_back('a');
      if (h1 > hsh) {
        s.back() += (h1 - hsh);
      } else {
        t.back() += (hsh - h1);
      }
      vector<int> all;
      for (int i = 0; i < 100; ++i) {
        string cur;
        for (int j = 0; j < 7; ++j) {
          if (i & (1 << j)) {
            cur += s;
            cout << s;
          } else {
            cur += t;
            cout << t;
          }
        }
        all.push_back(get_h(cur));
        cout << "\n";
      }
      sort(all.begin(), all.end());
      assert(all[0] == all.back());
      exit(0);
    }
    mem[id] = s;
    h[id] = hsh;
    return;
  }
  for (int i = 0; i < 26; ++i) {
    s.push_back('a' + i);
    int hsh1 = add(mul(hsh, B), i + 1);
    go(hsh1);
    s.pop_back();
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  cin >> B >> MOD;
  go(0);

  return 0;
}

详细

Test #1:

score: 0
Memory Limit Exceeded

input:

215465827 841597626

output:

aaajaaeaaajaaeaaajaaeaaajaaeaaajaaeaaajaaeaaajaae
aafafjaaaajaaeaaajaaeaaajaaeaaajaaeaaajaaeaaajaae
aaajaaeaafafjaaaajaaeaaajaaeaaajaaeaaajaaeaaajaae
aafafjaaafafjaaaajaaeaaajaaeaaajaaeaaajaaeaaajaae
aaajaaeaaajaaeaafafjaaaajaaeaaajaaeaaajaaeaaajaae
aafafjaaaajaaeaafafjaaaajaaeaaajaaeaaajaaeaaajaae
...

result: