Submission #50849425

---

Source Code Expand

#include <algorithm>
#include <cstdint>
#include <immintrin.h>
#include <iostream>
#include <random>
#include <string>
#include <tuple>
#include <unordered_set>
#include <vector>

struct BitPoly {
  std::vector<std::uint64_t> bits;

  BitPoly() : bits() {}

  BitPoly(std::string x) {
    unsigned length = x.size();
    bits.resize((length + 63) / 64);
    for (unsigned i = 0; i < length; i++) {
      if (x[i] == '1') {
        bits[i / 64] |= 1ULL << (i % 64);
      }
    }
    reduce();
  }

  void prepare_bit(unsigned i) {
    unsigned vector_pos = i / 64;
    if (vector_pos >= bits.size()) {
      bits.resize(vector_pos + 1);
    }
  }

  void set(unsigned i) {
    prepare_bit(i);
    bits[i / 64] |= 1ULL << (i % 64);
    reduce();
  }

  void flip(unsigned i) {
    prepare_bit(i);
    bits[i / 64] ^= 1ULL << (i % 64);
    reduce();
  }

  bool operator[](unsigned i) const {
    if (i / 64 >= bits.size()) {
      return false;
    }
    return (bits[i / 64] >> (i % 64)) & 1;
  }

  void reduce() {
    while (!bits.empty() && bits.back() == 0) {
      bits.pop_back();
    }
  }

  BitPoly operator+(const BitPoly &other) const {
    BitPoly result = *this;
    if (result.bits.size() < other.bits.size()) {
      result.bits.resize(other.bits.size());
    }
    for (unsigned i = 0; i < other.bits.size(); i++) {
      result.bits[i] ^= other.bits[i];
    }
    result.reduce();
    return result;
  }

  BitPoly operator<<(unsigned shift) const {
    BitPoly result;
    result.bits.resize(bits.size() + (shift + 63) / 64);
    for (unsigned i = 0; i < bits.size(); i++) {
      result.bits[i + shift / 64] |= bits[i] << (shift % 64);
      if (shift % 64 != 0) {
        result.bits[i + shift / 64 + 1] |= bits[i] >> (64 - shift % 64);
      }
    }
    result.reduce();
    return result;
  }

  static std::pair<std::uint64_t, std::uint64_t>
  carryless_mul(std::uint64_t a, std::uint64_t b) {
    __m128i a_ = _mm_cvtsi64_si128(a);
    __m128i b_ = _mm_cvtsi64_si128(b);
    __m128i c = _mm_clmulepi64_si128(a_, b_, 0);
    std::uint64_t low = _mm_extract_epi64(c, 0);
    std::uint64_t high = _mm_extract_epi64(c, 1);
    return {low, high};
  }

  BitPoly operator*(const BitPoly &other) const {
    BitPoly result;
    result.bits.resize(bits.size() + other.bits.size());
    for (unsigned i = 0; i < bits.size(); i++) {
      for (unsigned j = 0; j < other.bits.size(); j++) {
        auto [low, high] = carryless_mul(bits[i], other.bits[j]);
        result.bits[i + j] ^= low;
        result.bits[i + j + 1] ^= high;
      }
    }
    result.reduce();
    return result;
  }

  bool operator==(const BitPoly &other) const {
    if (bits.size() != other.bits.size()) {
      return false;
    }
    for (unsigned i = 0; i < bits.size(); i++) {
      if (bits[i] != other.bits[i]) {
        return false;
      }
    }
    return true;
  }

  unsigned degree() const {
    if (bits.empty()) {
      return 0;
    }
    return 64 * bits.size() - __builtin_clzll(bits.back()) - 1;
  }

  std::pair<BitPoly, BitPoly> divmod(const BitPoly &other) const {
    unsigned self_len = bits.size();
    unsigned other_len = other.bits.size();

    if (self_len < other_len) {
      return {BitPoly(), *this};
    }

    BitPoly quotient;
    quotient.bits.resize(self_len - other_len + 1);
    BitPoly remainder = *this;
    for (unsigned i = self_len - 1; i + 1 >= other_len; i--) {
      unsigned shift = i + 1 - other_len;
      __uint128_t a = 0;
      if (i + 1 < self_len) {
        a = remainder.bits[i + 1];
        a <<= 64;
      }
      a |= remainder.bits[i];
      __uint128_t b = other.bits[other_len - 1];
      b <<= 64;
      if (other_len >= 2) {
        b |= other.bits[other_len - 2];
      }

      std::uint64_t q = 0;
      for (unsigned j = 1; j <= 64; j++) {
        __uint128_t shift_b = b >> j;
        if ((a ^ shift_b) < a) {
          a ^= shift_b;
          q |= 1ULL << (64 - j);
        }
      }

      for (unsigned j = 0; j < other_len; j++) {
        auto [low, high] = carryless_mul(q, other.bits[j]);

        if (j + shift < self_len - 1) {
          remainder.bits[j + shift + 1] ^= high;
        }
        remainder.bits[j + shift] ^= low;
      }
      quotient.bits[shift] = q;
    }

    quotient.reduce();
    remainder.reduce();

    return {quotient, remainder};
  }

  BitPoly operator/(const BitPoly &other) const { return divmod(other).first; }

  BitPoly operator%(const BitPoly &other) const { return divmod(other).second; }

  std::tuple<BitPoly, BitPoly, BitPoly> extgcd(const BitPoly &other) const {
    BitPoly a = *this, b = other;
    BitPoly sa("1"), ta, sb, tb("1");

    while (!b.bits.empty()) {
      auto [q, r] = a.divmod(b);
      a = b;
      b = r;
      BitPoly tmp = sa;
      sa = sb;
      sb = tmp + sa * q;
      tmp = ta;
      ta = tb;
      tb = tmp + ta * q;
    }
    return {sa, ta, a};
  }

  std::uint64_t hash() const {
    static std::random_device seed_gen;
    static std::uint64_t base = (seed_gen() & ((1ULL << 63) - 1)) << 1;
    std::uint64_t result = 0;
    for (std::uint64_t x : bits) {
      std::uint64_t x1 = x >> 32, x2 = x & ((1ULL << 32) - 1);
      {
        auto [low, high] = carryless_mul(result ^ x1, base);
        result = low >> 1 ^ high ^ high << 1;
      }
      {
        auto [low, high] = carryless_mul(result ^ x2, base);
        result = low >> 1 ^ high ^ high << 1;
      }
    }
    return result;
  }

  BitPoly mod_pow(unsigned k, const BitPoly &mod) const {
    BitPoly result("1");
    BitPoly base = *this;
    while (k > 0) {
      if (k & 1) {
        result = result * base % mod;
      }
      base = base * base % mod;
      k >>= 1;
    }
    return result;
  }
};

void multiply_by_x(BitPoly &f, BitPoly &mod) {
  f = f << 1;
  if (f[mod.degree()]) {
    f = f + mod;
  }
}

int main() {
  unsigned n;
  std::string s, t;
  std::cin >> n >> s >> t;

  BitPoly f_s(s), f_t(t);

  unsigned p;
  std::cin >> p;
  BitPoly f_a;
  for (unsigned i = 0; i < p; i++) {
    unsigned a;
    std::cin >> a;
    f_a.set(a - 1);
  }
  f_a.flip(0);
  f_a.flip(n);

  unsigned q;
  std::cin >> q;
  BitPoly f_b;
  for (unsigned i = 0; i < q; i++) {
    unsigned b;
    std::cin >> b;
    f_b.set(b - 1);
  }

  auto [f_p, f_q, f_g] = f_a.extgcd(f_b);

  auto output = [&](const BitPoly &ans, unsigned length) {
    std::string ans_str(length, '0');
    for (unsigned i = 0; i <= ans.degree(); i++) {
      if (ans[i]) {
        ans_str[length - 1 - i] = '1';
      }
    }
    std::cout << length << std::endl << ans_str << std::endl;
  };

  unsigned f_g_degree = f_g.degree();
  BitPoly f_s_mod_g = f_s % f_g, f_t_mod_g = f_t % f_g;
  BitPoly f_s_q_mod_a = f_s * f_q % f_a, f_t_q_mod_a = f_t * f_q % f_a;

  const unsigned STEP_SIZE = 1000;

  for (unsigned i = 1; i <= std::max(n, STEP_SIZE); i++) {
    multiply_by_x(f_s_mod_g, f_g);
    multiply_by_x(f_s_q_mod_a, f_a);
    BitPoly f_st_q_mod_a = f_s_q_mod_a + f_t_q_mod_a;
    if (f_s_mod_g == f_t_mod_g && f_st_q_mod_a.degree() < i + f_g_degree) {
      output(f_st_q_mod_a / f_g, i);
      return 0;
    }
  }

  std::unordered_set<std::uint64_t> baby_step;
  f_t_mod_g = f_t % f_g;
  BitPoly f_x_step_mod_g("1");
  for (unsigned i = 0; i < STEP_SIZE; i++) {
    baby_step.insert(f_t_mod_g.hash());
    multiply_by_x(f_t_mod_g, f_g);
    multiply_by_x(f_x_step_mod_g, f_g);
  }
  f_s_mod_g = f_s % f_g;
  f_t_mod_g = f_t % f_g;
  unsigned failure_cnt = 0;
  for (unsigned i = 0; i <= (unsigned)1e6; i += STEP_SIZE) {
    BitPoly next_f_s_mod_g = f_s_mod_g * f_x_step_mod_g % f_g;

    if (baby_step.contains(next_f_s_mod_g.hash())) {
      for (unsigned j = 1; j <= STEP_SIZE; j++) {
        unsigned k = i + j;
        multiply_by_x(f_s_mod_g, f_g);
        if (n < k && k <= (unsigned)1e6 && f_s_mod_g == f_t_mod_g) {
          output((f_s * BitPoly("01").mod_pow(k, f_a) + f_t) * f_q % f_a / f_g,
                 k);
          return 0;
        }
      }
      if (n < i && ++failure_cnt == 2) {
        break;
      }
    }
    f_s_mod_g = next_f_s_mod_g;
  }

  std::cout << -1 << '\n';
}

Submission Info

Judge Result