#712540 (C++17) No.1800 Random XOR

提出ソース
結果

問題	No.1800 Random XOR
ユーザー	Cyanmond
提出日時	2021-11-03 11:36:42
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	14,788 bytes
コンパイル時間	2,045 ms
コンパイル使用メモリ	197,004 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-04-21 02:14:28
合計ジャッジ時間	2,613 ms
ジャッジサーバーID （参考情報）	judge4 / judge3
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	1 ms 6,944 KB
testcase_03	AC	1 ms 6,944 KB
testcase_04	AC	1 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	1 ms 6,940 KB
testcase_10	AC	1 ms 6,940 KB
testcase_11	AC	2 ms 6,940 KB
testcase_12	AC	2 ms 6,944 KB
testcase_13	AC	1 ms 6,940 KB
testcase_14	AC	2 ms 6,940 KB
testcase_15	AC	1 ms 6,944 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include "bits/stdc++.h"
// cmt

#pragma region template

// utility
namespace cl {
using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using std::ignore;
using std::make_pair;
using std::make_tuple;
using std::nullopt;
using std::pair;
using std::tuple;

using usize = std::size_t;
using isize = std::ptrdiff_t;

constexpr std::int64_t operator""_i64(unsigned long long n) noexcept {
  return static_cast<std::int64_t>(n);
}
constexpr std::int32_t operator""_i32(unsigned long long n) noexcept {
  return static_cast<std::int32_t>(n);
}
constexpr std::int16_t operator""_i16(unsigned long long n) noexcept {
  return static_cast<std::int16_t>(n);
}

constexpr std::uint64_t operator""_u64(unsigned long long n) noexcept {
  return static_cast<std::uint64_t>(n);
}
constexpr std::uint32_t operator""_u32(unsigned long long n) noexcept {
  return static_cast<std::uint32_t>(n);
}
constexpr std::uint16_t operator""_u16(unsigned long long n) noexcept {
  return static_cast<std::uint16_t>(n);
}

constexpr usize operator""_uz(unsigned long long n) noexcept { return static_cast<usize>(n); }
constexpr isize operator""_iz(unsigned long long n) noexcept { return static_cast<isize>(n); }

template <class T, T Div = 2>
constexpr T infty = std::numeric_limits<T>::max() / Div - 10;
constexpr std::int32_t infi32 = infty<std::int32_t, 2>;  // 1073741813
constexpr std::int64_t infi64 = infty<std::int64_t, 4>;  // 2305843009213693941
constexpr usize infusz = infty<usize, 2>;

#if __cplusplus < 202002L
template <typename T>
constexpr int popcount(T x) noexcept {
  static_assert(std::is_unsigned_v<T>);
  x = x - ((x >> 1) & 0x5555555555555555);
  x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
  x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f;
  x = x + (x >> 8);
  x = x + (x >> 16);
  x = x + (x >> 32);
  return x & 0x0000007f;
}
#else
using std::popcount;
#endif

template <typename T>
constexpr T ceil_div(const T a, const T b) {
  return (a + b - 1) / b;
}

template <class T>
auto mk_vec(const usize n, const T& value) {
  return std::vector(n, value);
}
template <class... Args>
auto mk_vec(const usize n, Args... args) {
  return std::vector(n, mk_vec(args...));
}

namespace helper {
template <class T, class... Tail>
void zip_sort_renumber(const std::vector<usize>& order, std::vector<T>& head, Tail&... tail) {
  const usize n = order.size();
  std::vector<T> sorted_head(n);
  for (usize i = 0; i < n; ++i) sorted_head[i] = head[order[i]];
  head = std::move(sorted_head);
  if constexpr (sizeof...(Tail) != 0) zip_sort_renumber(order, tail...);
}
}  // namespace helper

template <class Head, class... Tail>
std::vector<usize> zip_sort(std::vector<Head>& head, std::vector<Tail>&... tail) {
  const usize n = head.size();

  std::vector<std::tuple<Head, Tail..., usize>> res(n);
  for (usize i = 0; i < n; ++i) res[i] = std::make_tuple(head[i], tail[i]..., i);
  std::sort(res.begin(), res.end());

  std::vector<usize> order(n);
  for (usize i = 0; i < n; ++i)
    order[i] = std::get<std::tuple_size_v<std::tuple<Head, Tail...>>>(res[i]);
  helper::zip_sort_renumber(order, head, tail...);
  return order;
}

template <class T>
class presser {
  using size_type = std::size_t;
  std::vector<T> m_v;

 public:
  size_type size() const noexcept { return m_v.size(); }

  void reserve(const size_type n) { m_v.reserve(n); }

  template <class ForwardIterator>
  void paste(const ForwardIterator first, const ForwardIterator last) {
    std::copy(first, last, std::back_inserter(m_v));
  }

  template <class Container>
  void paste(const Container& c) {
    std::copy(c.begin(), c.end(), std::back_inserter(m_v));
  }

  void add(const T& v) { m_v.push_back(v); }

  size_type build() {
    std::sort(m_v.begin(), m_v.end());
    m_v.erase(std::unique(m_v.begin(), m_v.end()), m_v.end());
    return m_v.size();
  }

  size_type get_idx(const T& val) const {
    return static_cast<size_type>(std::lower_bound(m_v.begin(), m_v.end(), val) - m_v.begin());
  }

  T get_val(const size_type i) const { return m_v[i]; }
};

class rep {
  struct rep_iterator {
    usize itr;
    constexpr rep_iterator(const usize pos) noexcept : itr(pos) {}
    constexpr void operator++() noexcept { ++itr; }
    constexpr bool operator!=(const usize& other) const noexcept { return itr != other; }
    constexpr usize operator*() const noexcept { return itr; }
  };
  const rep_iterator first;
  const usize last;

 public:
  constexpr rep(const usize first_, const usize last_) noexcept : first(first_), last(last_) {}
  constexpr rep_iterator begin() const noexcept { return first; }
  constexpr usize end() const noexcept { return last; }
};

class repstep {
  struct repstep_iterator {
    usize itr, stepsize;
    constexpr repstep_iterator(const usize pos, const usize stp) noexcept
        : itr(pos), stepsize(stp) {}
    constexpr void operator++() noexcept { itr += stepsize; }
    constexpr bool operator!=(const usize& other) const noexcept { return itr < other; }
    constexpr usize operator*() const noexcept { return itr; }
  };
  const repstep_iterator first;
  const usize last;

 public:
  constexpr repstep(const usize first_, const usize last_, const usize stp_)
      : first(first_, stp_), last(last_) {}
  constexpr repstep_iterator begin() const noexcept { return first; }
  constexpr usize end() const noexcept { return last; }
};

class revrep {
  struct revrep_iterator {
    usize itr;
    constexpr revrep_iterator(const usize pos) noexcept : itr(pos) {}
    constexpr void operator++() noexcept { --itr; }
    constexpr bool operator!=(const usize& other) const noexcept { return itr != other; }
    constexpr usize operator*() const noexcept { return itr; }
  };
  const revrep_iterator first;
  const usize last;

 public:
  constexpr revrep(const usize first_, const usize last_) noexcept
      : first(last_ - 1), last(first_ - 1) {}
  constexpr revrep_iterator begin() const noexcept { return first; }
  constexpr usize end() const noexcept { return last; }
};

template <class F>
class rec_lambda {
  F f;

 public:
  explicit constexpr rec_lambda(F&& f_) : f(std::forward<F>(f_)) {}
  template <class... Args>
  constexpr auto operator()(Args&&... args) const {
    return f(*this, std::forward<Args>(args)...);
  }
};

class to4 {
  using value_type = usize;
  static_assert(std::is_unsigned_v<value_type>);
  static constexpr value_type minus1 = std::numeric_limits<value_type>::max();
  static constexpr std::array<value_type, 5> dx = {minus1, 0, 1, 0, 0}, dy = {0, minus1, 0, 1, 0};

  struct to4_iterator {
    int d;
    const value_type h, w, maxh, maxw;
    constexpr to4_iterator(const value_type h_, const value_type w_, const value_type maxh_,
                           const value_type maxw_) noexcept
        : d(0), h(h_), w(w_), maxh(maxh_), maxw(maxw_) {}
    constexpr void operator++() noexcept {
      do {
        ++d;
      } while (d != 4 and (h + dx[d] == minus1 or h + dx[d] == maxh or w + dy[d] == minus1 or
                           w + dy[d] == maxw));
    }
    constexpr bool operator!=(const int other) const noexcept { return d != other; }
    constexpr std::pair<value_type, value_type> operator*() const noexcept {
      return {h + dx[d], w + dy[d]};
    }
  };

  const to4_iterator i;

 public:
  constexpr to4(const value_type h, const value_type w, const value_type maxh,
                const value_type maxw) noexcept
      : i(h, w, maxh, maxw) {}
  constexpr to4_iterator begin() const noexcept { return i; }
  constexpr int end() const noexcept { return 4; }
};

class to8 {
  using value_type = usize;
  static_assert(std::is_unsigned_v<value_type>);
  static constexpr value_type minus1 = std::numeric_limits<value_type>::max();
  static constexpr std::array<value_type, 9> dx = {minus1, minus1, minus1, 0, 0, 1, 1, 1, 0},
                                             dy = {minus1, 0, 1, minus1, 1, minus1, 0, 1, 0};

  struct to8_iterator {
    int d;
    const value_type h, w, maxh, maxw;
    constexpr to8_iterator(const value_type h_, const value_type w_, const value_type maxh_,
                           const value_type maxw_) noexcept
        : d(0), h(h_), w(w_), maxh(maxh_), maxw(maxw_) {}
    constexpr void operator++() noexcept {
      do {
        ++d;
      } while (d != 8 and (h + dx[d] == minus1 or h + dx[d] == maxh or w + dy[d] == minus1 or
                           w + dy[d] == maxw));
    }
    constexpr bool operator!=(const int other) const noexcept { return d != other; }
    constexpr std::pair<value_type, value_type> operator*() const noexcept {
      return {h + dx[d], w + dy[d]};
    }
  };

  const to8_iterator i;

 public:
  constexpr to8(const value_type h, const value_type w, const value_type maxh,
                const value_type maxw) noexcept
      : i(h, w, maxh, maxw) {}
  constexpr to8_iterator begin() const noexcept { return i; }
  constexpr int end() const noexcept { return 8; }
};

template <std::uint32_t MOD>
class StaticModint {
  using this_type = StaticModint;
  std::uint32_t value;

 public:
  static constexpr std::uint32_t mod() noexcept { return MOD; }
  template <class T>
  static constexpr T mod() noexcept {
    return static_cast<T>(MOD);
  }

  template <class T, std::enable_if_t<std::is_unsigned_v<T>>* = nullptr>
  static constexpr std::uint32_t normalize(const T v) noexcept {
    return static_cast<std::uint32_t>(v % mod<T>());
  }
  template <class T, std::enable_if_t<std::is_signed_v<T>>* = nullptr>
  static constexpr std::uint32_t normalize(const T v) noexcept {
    if (v < 0)
      return static_cast<std::uint32_t>(v % mod<T>() + mod<T>());
    else
      return static_cast<std::uint32_t>(v % mod<T>());
  }

  constexpr StaticModint() noexcept : value(0) {}
  template <class T>
  constexpr StaticModint(const T v) noexcept : value(normalize(v)) {}

  template <class T>
  static constexpr this_type raw(const T v) noexcept {
    this_type ret;
    ret.value = static_cast<std::uint32_t>(v);
    return ret;
  }

  constexpr const std::uint32_t& val() const noexcept { return value; }
  constexpr this_type operator-() const noexcept { return value == 0 ? 0 : mod() - value; }

  constexpr bool operator==(const this_type& rhs) const noexcept { return value == rhs.value; }
  constexpr bool operator!=(const this_type& rhs) const noexcept { return value != rhs.value; }
  constexpr bool operator<(const this_type& rhs) const noexcept { return value < rhs.value; }
  constexpr bool operator<=(const this_type& rhs) const noexcept { return value <= rhs.value; }
  constexpr bool operator>(const this_type& rhs) const noexcept { return value > rhs.value; }
  constexpr bool operator>=(const this_type& rhs) const noexcept { return value >= rhs.value; }
  constexpr this_type& operator++() noexcept {
    ++value;
    if (value == mod()) value = 0;
    return *this;
  }
  constexpr this_type& operator--() noexcept {
    if (value == 0) value = mod();
    --value;
    return *this;
  }
  constexpr this_type operator++(int) noexcept {
    this_type ret(*this);
    ++*this;
    return ret;
  }
  constexpr this_type operator--(int) noexcept {
    this_type ret(*this);
    --*this;
    return ret;
  }

  constexpr this_type operator+(const this_type& rhs) const noexcept {
    return this_type(*this) += rhs;
  }
  constexpr this_type operator-(const this_type& rhs) const noexcept {
    return this_type(*this) -= rhs;
  }
  constexpr this_type operator*(const this_type& rhs) const noexcept {
    return this_type(*this) *= rhs;
  }
  constexpr this_type operator/(const this_type& rhs) const noexcept {
    return this_type(*this) /= rhs;
  }

  constexpr this_type& operator+=(const this_type& rhs) noexcept {
    if ((value += rhs.value) >= mod()) value -= mod();
    return *this;
  }
  constexpr this_type& operator-=(const this_type& rhs) noexcept {
    if (value < rhs.value) value += mod();
    value -= rhs.value;
    return *this;
  }
  constexpr this_type& operator*=(const this_type& rhs) noexcept {
    value =
        static_cast<std::uint32_t>(static_cast<std::uint64_t>(value) *
                                   static_cast<std::uint64_t>(rhs.value) % mod<std::uint64_t>());
    return *this;
  }
  constexpr this_type& operator/=(const this_type& rhs) noexcept { return *this *= rhs.inv(); }

  template <class T>
  constexpr this_type pow(T n) {
    this_type ret(1), x(*this);
    while (n != 0) {
      if (n & 1) ret *= x;
      x *= x;
      n >>= 1;
    }
    return ret;
  }
  constexpr this_type inv() const {
    std::int64_t s = mod<std::int64_t>(), t = static_cast<std::int64_t>(value), a = 0, b = 1;
    while (t != 0) {
      const std::int64_t u = s / t;
      s -= t * u;
      a -= b * u;
      auto k = s;
      s = t;
      t = k;
      k = a;
      a = b;
      b = k;
    }
    if (a < 0) a += mod<std::int64_t>();
    return this_type::raw(a);
  }
};

template <class T>
class StaticModintUtility {
  using size_type = std::size_t;
  static inline size_type size = 1;

 public:
  static void upsize(const size_type n) {
    if (n > size) {
      for (size_type i = size + 1; i <= n; ++i) {
        fact.emplace_back(fact[i - 1] * T::raw(i));
        inv.emplace_back(-inv[T::mod() % i] * (T::mod() / i));
        fact_inv.emplace_back(fact_inv[i - 1] * inv[i]);
      }
      size = n;
    }
  }

  static inline std::vector<T> fact = {1, 1}, inv = {0, 1}, fact_inv = {1, 1};

  static T comb(const size_type n, const size_type r) {
    if (n < r) return 0;
    upsize(n);
    return fact[n] * fact_inv[n - r] * fact_inv[r];
  }

  static T homo(const size_type n, const size_type r) {
    if (n == 0 and r == 0) return T(1);
    return comb(n + r - 1, r);
  }
};
}  // namespace cl

// io
namespace cl {
template <class T>
inline T scan() {
  T ret;
  std::cin >> ret;
  return ret;
}

constexpr char eoln = '\n';
}  // namespace cl

#pragma endregion

namespace cl {
#ifdef CL_DEBUG
// output "Debug : names = values"
#define pdebug(...)                                   \
  {                                                   \
    std::cerr << "Debug : " << #__VA_ARGS__ << " = "; \
    debug_impl::converter(__VA_ARGS__);               \
  }
#else
#define pdebug(...)
#endif

using Modint = StaticModint<1000000007>;

void main_() {
  const i64 N = scan<i64>();
  const i64 M = scan<i64>();

  std::cout << ((Modint::raw(2).pow(M) - 1) / 2).val() << eoln;
}

#undef pdebug
}  // namespace cl

int main() {
  // std::ios::sync_with_stdio(false);
  // std::cin.tie(nullptr);

#ifdef CL_LOCAL
  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);
#endif

  std::size_t T = 1;
  // std::cin >> T;
  while (T--) cl::main_();
  return 0;
}
yukicoder

結果

テストケース

ソースコード
