test/yc_3014.test.cpp

#define PROBLEM "https://yukicoder.me/problems/no/3014"

#include <cstdint>
#include <cstdio>
#include <cassert>
#include <string>
#include <vector>

#include "String/tree_attack.cpp"

int main() {
  intmax_t p, b;
  int sigma = 26;
  scanf("%jd %jd %d", &p, &b, &sigma);

  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, sigma);
    if (a.empty()) {
      ++k;
      continue;
    }
    s = t = std::string(n, 'x');
    for (size_t i = 0; i < a.size(); ++i) {
      if (a[i] > 0) {
        s[i] = 'a' + a[i];
        t[i] = 'a';
      }
      if (a[i] < 0) {
        s[i] = 'a';
        t[i] = 'a' - a[i];
      }
    }
  } while (s.empty());

  // for special judges
  // 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, "s: \"%s\"\n", s.data());
  fprintf(stderr, "t: \"%s\"\n", t.data());
  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);
}

#line 1 "test/yc_3014.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/3014"

#include <cstdint>
#include <cstdio>
#include <cassert>
#include <string>
#include <vector>

#line 1 "String/tree_attack.cpp"



/**
 * @brief ロリハを衝突させるやつ (tree attack)
 * @author えびちゃん
 * @see https://codeforces.com/blog/entry/60442
 */

#include <cstddef>
#line 12 "String/tree_attack.cpp"
#include <algorithm>
#include <queue>
#include <tuple>
#line 16 "String/tree_attack.cpp"

#line 1 "utility/literals.cpp"



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

#line 11 "utility/literals.cpp"

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; }

constexpr int8_t   operator ""_i8(unsigned long long n)  { return n; }
constexpr int16_t  operator ""_i16(unsigned long long n) { return n; }
constexpr int32_t  operator ""_i32(unsigned long long n) { return n; }
constexpr int64_t  operator ""_i64(unsigned long long n) { return n; }
constexpr uint8_t  operator ""_u8(unsigned long long n)  { return n; }
constexpr uint16_t operator ""_u16(unsigned long long n) { return n; }
constexpr uint32_t operator ""_u32(unsigned long long n) { return n; }
constexpr uint64_t operator ""_u64(unsigned long long n) { return n; }


#line 18 "String/tree_attack.cpp"

std::vector<int> tree_attack(intmax_t p, intmax_t b, size_t k, int sigma = 2) {
  struct node {
    intmax_t value;
    size_t pos, neg;
    int coef;
    node() = default;
    node(intmax_t v, size_t l, size_t r, int c): value(v), pos(l), neg(r), coef(c) {}
    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, 1));
  intmax_t pow = 1;
  for (size_t j = 1; j < n; ++j) {
    pow = __int128(pow) * b % p;
    cl[0][j].value = pow;
    cl[0][j].coef = 1;
    intmax_t cur = pow;
    for (int s = 2; s < sigma; ++s) {
      cur = __int128(cur + pow) % p;
      if (cur < cl[0][j].value) {
        cl[0][j].value = cur;
        cl[0][j].coef = s;
      }
    }
    cl[0][j].pos = n-1-j;
  }

  std::sort(cl[0].begin(), cl[0].end());

  std::vector<int> coef(n);
  for (size_t i = 0; i < n; ++i)
    coef[cl[0][i].pos] = cl[0][i].coef;

  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? -coef[j]: +coef[j]);
        continue;
      }
      q.emplace(i-1, cl[i][j].pos, neg);
      q.emplace(i-1, cl[i][j].neg, !neg);
    }
    return res;
  }
  return {};
}


#line 10 "test/yc_3014.test.cpp"

int main() {
  intmax_t p, b;
  int sigma = 26;
  scanf("%jd %jd %d", &p, &b, &sigma);

  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, sigma);
    if (a.empty()) {
      ++k;
      continue;
    }
    s = t = std::string(n, 'x');
    for (size_t i = 0; i < a.size(); ++i) {
      if (a[i] > 0) {
        s[i] = 'a' + a[i];
        t[i] = 'a';
      }
      if (a[i] < 0) {
        s[i] = 'a';
        t[i] = 'a' - a[i];
      }
    }
  } while (s.empty());

  // for special judges
  // 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, "s: \"%s\"\n", s.data());
  fprintf(stderr, "t: \"%s\"\n", t.data());
  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);
}