結果

問題 No.3014 多項式ハッシュに関する教育的な問題
ユーザー rsk0315rsk0315
提出日時 2020-03-03 04:00:28
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 3,279 bytes
コンパイル時間 1,080 ms
コンパイル使用メモリ 90,588 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-13 21:40:24
合計ジャッジ時間 1,620 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/**
 * @brief ユーザ定義リテラル
 * @author えびちゃん
 */

#ifndef H_int_literals
#define H_int_literals

#include <cstddef>
#include <cstdint>

constexpr intmax_t  operator ""_jd(unsigned long long n) { return n; }
constexpr uintmax_t operator ""_ju(unsigned long long n) { return n; }
constexpr size_t    operator ""_zu(unsigned long long n) { return n; }
constexpr ptrdiff_t operator ""_td(unsigned long long n) { return n; }

#endif  /* !defined(H_int_literals) */

#include <cstdio>
#include <cstdint>
#include <cassert>
#include <algorithm>
#include <queue>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

std::vector<int> tree_attack(intmax_t p, intmax_t b, size_t k) {
  struct node {
    intmax_t value;
    size_t pos, neg;
    node() = default;
    node(intmax_t v, size_t l, size_t r): value(v), pos(l), neg(r) {}
    bool operator <(node const& that) const { return value < that.value; }
  };

  std::vector<std::vector<node>> cl(k+1);
  size_t n = 1_zu << k;
  cl[0].assign(n, node(1, n-1, -1_zu));
  for (size_t j = 1; j < n; ++j) {
    cl[0][j].value = __int128(cl[0][j-1].value) * b % p;
    cl[0][j].pos = n-1-j;
  }
  std::sort(cl[0].begin(), cl[0].end());

  for (size_t i = 1; i <= k; ++i) {
    cl[i].resize(n >> i);
    for (size_t j = 0; j < cl[i].size(); ++j) {
      size_t jl = j << 1 | 0;
      size_t jr = j << 1 | 1;
      if (cl[i-1][jr] < cl[i-1][jl]) {
        cl[i][j].value = cl[i-1][jl].value - cl[i-1][jr].value;
        cl[i][j].pos = jl;
        cl[i][j].neg = jr;
      } else {
        cl[i][j].value = cl[i-1][jr].value - cl[i-1][jl].value;
        cl[i][j].pos = jr;
        cl[i][j].neg = jl;
      }
    }
    std::sort(cl[i].begin(), cl[i].end());
    if (cl[i][0].value > 0) continue;

    std::vector<int> res(n, 0);
    std::queue<std::tuple<size_t, size_t, bool>> q;  // i, j, neg?
    q.emplace(i-1, cl[i][0].pos, false);
    q.emplace(i-1, cl[i][0].neg, true);
    while (!q.empty()) {
      auto [i, j, neg] = q.front();
      q.pop();
      if (i == -1_zu) {
        if (j != -1_zu) res[j] = (neg? -1: +1);
        continue;
      }
      q.emplace(i-1, cl[i][j].pos, neg);
      q.emplace(i-1, cl[i][j].neg, !neg);
    }
    return res;
  }
  return {};
}

int main() {
  intmax_t p, b;
  scanf("%jd %jd", &p, &b);

  auto h = [&](auto const& s) -> intmax_t {
    __int128 h = 0;
    for (size_t i = 0; i < s.size(); ++i)
      h = (h * b + s[i]) % p;
    return h;
  };

  size_t k = 2;
  std::string s, t;
  do {
    size_t n = 1_zu << k;
    std::vector<int> a = tree_attack(p, b, k);
    if (a.empty()) {
      ++k;
      continue;
    }
    s = t = std::string(n, 'x');
    for (size_t i = 0; i < a.size(); ++i) {
      if (a[i] == +1) {
        s[i] = 'b';
        t[i] = 'a';
      }
      if (a[i] == -1) {
        s[i] = 'a';
        t[i] = 'b';
      }
    }
  } while (s.empty());

  printf("%s\n", s.data());
  printf("%s\n", t.data());

  std::vector<int> u(s.length());
  for (size_t i = 0; i < s.length(); ++i)
    u[i] = s[i]-t[i];

  fprintf(stderr, "length: %zu\n", s.length());
  fprintf(stderr, "h(s): %jd\n", h(s));
  fprintf(stderr, "h(t): %jd\n", h(t));
  fprintf(stderr, "h(s-t): %jd\n", h(u));
  assert(h(u) == 0);
  assert(h(s) == h(t));
  assert(s != t);
}
0