#678267 (C++17) No.1595 The Final Digit

提出ソース
結果

問題	No.1595 The Final Digit
ユーザー	naskya
提出日時	2021-07-15 18:45:42
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	14,348 bytes
コンパイル時間	1,315 ms
コンパイル使用メモリ	140,940 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-07-04 19:26:14
合計ジャッジ時間	2,049 ms
ジャッジサーバーID （参考情報）	judge5 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

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

raw source code
#pragma region template
// clang-format off

#ifdef LOCAL_NDEBUG
#include <headers.hpp>
#endif

// #define USE_EXTERNAL_CONTAINERS
// #define NO_PRINT_INF

#ifdef USE_EXTERNAL_CONTAINERS
#include <boost/container/flat_map.hpp>
#include <boost/container/flat_set.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
template <class T>          using rb_tree    = __gnu_pbds::tree<T, __gnu_pbds::null_type, std::less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
template <class S, class T> using hash_table = __gnu_pbds::gp_hash_table<S, T>;
#endif

#ifdef LOCAL_DEBUG
#if (defined USE_EXTERNAL_CONTAINERS) || (defined NO_PRINT_INF)
#include <../src/debugger.hpp>
#else
#include <debugger.hpp>
#endif
#endif

// #define PROPER
#define _USE_MATH_DEFINES

#if (defined __INTELLISENSE__) && (!defined PROPER)
#define NDEBUG
namespace std {
#endif

#include <cassert>
#include <cctype>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <algorithm>
#include <array>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <string_view>
#include <tuple>
#include <typeinfo>
#include <type_traits>
#include <utility>
#include <vector>

#if (defined __INTELLISENSE__) && (!defined PROPER)
  using namespace std;
}
#endif

#ifdef LOCAL_DEBUG
#define STR(x) #x
#define STRINGIFY(x) STR(x)
#define FILE_LINE "[Debug] ./" __FILE__ ":" STRINGIFY(__LINE__)
#define see(...) debugger::multi_print(#__VA_ARGS__, __VA_ARGS__)
#define see2(arg) arg.debug_print(#arg)
#define here(...) debugger::os << FILE_LINE << " in " << __func__ << ": \033[32mReached\033[39m\n"
#define com(msg) debugger::os << FILE_LINE << " in " << __func__ << ":\n    \033[36mComment:\033[39m " << msg << "\n"
#define err(msg) debugger::os << FILE_LINE << " in " << __func__ << ":\n    \033[31mError:\033[39m " << msg << "\n"
#define local(...) do { __VA_ARGS__ } while (0)
#define alter(x, y) x
#else
#define see(...) (static_cast<void>(0))
#define see2(arg) (static_cast<void>(0))
#define here(...) (static_cast<void>(0))
#define com(msg) (static_cast<void>(0))
#define err(msg) (static_cast<void>(0))
#define local(...) (static_cast<void>(0))
#define alter(x, y) y
#endif

#if (defined LOCAL_DEBUG) && (!defined NOWARN)
#define warn(msg) debugger::os << FILE_LINE << " in " << __func__ << ":\n    \033[33mWarning:\033[39m " << msg << "\n"
#else
#define warn(msg) (static_cast<void>(0))
#endif

#if (defined LOCAL_DEBUG) || (defined LOCAL_NDEBUG) || (defined __INTELLISENSE__)
#define NOEXCEPT
#define M_assert(expr) assert(expr)
#define O_assert(expr) assert(expr)
#else
#define NOEXCEPT noexcept
#define M_assert(expr) do {if(__builtin_expect(!(expr), 0)) {auto p = static_cast<std::int64_t*>(std::malloc(1 << 30)); for (int i = 0; i < (1 << 27); p[i] = 1, i += (1 << 9)); std::cerr << (*p);}} while (0)
#define O_assert(expr) do {if(__builtin_expect(!(expr), 0)) {const auto X = std::string(1000, '-'); for(int i = 0; i < (1 << 18); i++) std::cout << X;}} while (0)
#endif

#define as(type, val) static_cast<std::decay_t<type>>(val)
#define INDIRECT(...) __VA_ARGS__

#define rep(loop_var, loop_end) \
  for ( \
    auto loop_var = as(std::make_signed_t<decltype(loop_end)>, 0); \
    loop_var < as(decltype(loop_var), loop_end); \
    ++loop_var \
  )
#define rng(loop_var, loop_start, loop_end, loop_increment) \
  for ( \
    auto loop_var = as(INDIRECT(std::make_signed_t<std::common_type_t<decltype(loop_start), decltype(loop_end)>>), loop_start); \
    ((loop_increment) > 0) ? (loop_var < as(decltype(loop_var), loop_end)) : (loop_var > as(decltype(loop_var), loop_end)); \
    loop_var += (loop_increment) \
  )
#define erng(loop_var, loop_start, loop_end, loop_increment) \
  for ( \
    auto loop_var = as(INDIRECT(std::make_signed_t<std::common_type_t<decltype(loop_start), decltype(loop_end)>>), loop_start); \
    ((loop_increment) > 0) ? (loop_var <= as(decltype(loop_var), loop_end)) : (loop_var >= as(decltype(loop_var), loop_end)); \
    loop_var += (loop_increment) \
  )

[[maybe_unused]] constexpr int         INF   = 1000000005;
[[maybe_unused]] constexpr long long   LINF  = 1000000000000000005LL;
[[maybe_unused]] constexpr double      EPS   = 1e-9;
[[maybe_unused]] constexpr long double LEPS  = 1e-14L;
[[maybe_unused]] constexpr int         dy[9] = {1, 0, -1, 0, 1, 1, -1, -1, 0};
[[maybe_unused]] constexpr int         dx[9] = {0, 1, 0, -1, -1, 1, 1, -1, 0};

template <class... Ts> constexpr auto Min(const Ts... args) { return std::min({ as(std::common_type_t<Ts...>, args) ... }); }
template <class... Ts> constexpr auto Max(const Ts... args) { return std::max({ as(std::common_type_t<Ts...>, args) ... }); }

// clang-format on
#pragma endregion

#pragma region lib_static_matrix

#define lib_matrix
#define lib_static_matrix

#define static_loop(i, R, C, code)                                              \
  [&]<std::size_t... i>(std::index_sequence<i...>) constexpr { ((code), ...); } \
  (std::make_index_sequence<R * C> {})

namespace lib {
  /* prototype declarations */
  template <typename Tp, std::size_t R, std::size_t C> class static_matrix;
  template <typename Tp, std::size_t R, std::size_t C> constexpr static_matrix<Tp, R, C> zero_matrix();
  template <typename Tp, std::size_t R> constexpr static_matrix<Tp, R, R> id_matrix();

  template <typename Tp /* elem type */, std::size_t R /* number of rows */, std::size_t C /* number of columns */>
  class static_matrix {
    std::array<std::array<Tp, C>, R> data;

    public:
    constexpr static_matrix(void) {}
    constexpr static_matrix(const std::initializer_list<Tp>& src) : data() {
      auto iter = src.begin();
      static_loop(i, R, C, std::get<i % C>(std::get<i / C>(data)) = *(iter++));
    }
    constexpr static_matrix(std::initializer_list<Tp>&& src) : data() {
      auto iter = src.begin();
      static_loop(i, R, C, std::get<i % C>(std::get<i / C>(data)) = std::move(*(iter++)));
    }

    static constexpr int rows(void) noexcept { return R; }
    static constexpr int cols(void) noexcept { return C; }
    static constexpr int elems(void) noexcept { return R * C; }
    static constexpr bool is_square(void) noexcept { return R == C; }

    constexpr Tp& operator()(const std::size_t i, const std::size_t j) { return data[i][j]; }
    constexpr Tp operator()(const std::size_t i, const std::size_t j) const { return data[i][j]; }

    template <std::size_t I> constexpr Tp& get(void) { return std::get<I % C>(std::get<I / C>(data)); }
    template <std::size_t I> constexpr Tp get(void) const { return std::get<I % C>(std::get<I / C>(data)); }

    template <std::size_t i, std::size_t j> constexpr Tp& get(void) { return std::get<j>(std::get<i>(data)); }
    template <std::size_t i, std::size_t j> constexpr Tp get(void) const { return std::get<j>(std::get<i>(data)); }

    template <typename op> static constexpr static_matrix elemwise_op(static_matrix lhs, const static_matrix& rhs) {
      static_loop(i, R, C, lhs.template get<i>() = op {}(lhs.template get<i>(), rhs.template get<i>()));
      return lhs;
    }

    constexpr static_matrix& operator+(void) { return *this; }
    constexpr static_matrix operator+(void) const { return *this; }

    constexpr static_matrix operator-(void) const {
      auto res(*this);
      static_loop(i, R, C, res.template get<i>() = -res.template get<i>());
      return res;
    }

    constexpr static_matrix operator+(const static_matrix& rhs) const { return elemwise_op<std::plus<>>(*this, rhs); }
    constexpr static_matrix operator-(const static_matrix& rhs) const { return elemwise_op<std::minus<>>(*this, rhs); }

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

    template <std::size_t C2> constexpr auto operator*(const static_matrix<Tp, C, C2>& rhs) const {
      auto res = zero_matrix<Tp, R, C2>();
      [&]<std::size_t... i>(std::index_sequence<i...>) constexpr {
        ((res.template get<i / (C * C2), i % C2>() += get<i / C2>() * rhs.template get<(i / C2) % C, i % C2>()), ...);
      }
      (std::make_index_sequence<R * C * C2> {});
      return res;
    }
    constexpr decltype(auto) operator*=(const static_matrix<Tp, C, C>& rhs) { return (*this) = (*this) * rhs; }

    static_matrix pow(long long index) const {
      static_assert(is_square());
      auto res = id_matrix<Tp, R>(), base = (*this);
      while (index) {
        if (index & 1) res *= base;
        base *= base;
        index >>= 1;
      }
      return res;
    }
    void pow_self(long long index) {
      static_assert(is_square());
      if (index == 0) {
        *this = id_matrix<Tp, R>();
        return;
      }
      index--;
      auto base = (*this);
      while (index) {
        if (index & 1) (*this) *= base;
        base *= base;
        index >>= 1;
      }
    }

    template <typename ReturnType = Tp> constexpr ReturnType total(void) const {
      ReturnType res = 0;
      [&]<std::size_t... i>(std::index_sequence<i...>) {
        ((res += std::reduce(std::get<i>(data).cbegin(), std::get<i>(data).cend(), (ReturnType) 0)), ...);
      }
      (std::make_index_sequence<R> {});
      return res;
    }

    constexpr static_matrix<Tp, C, R> transposed(void) const noexcept {
      static_matrix<Tp, C, R> res;
      static_loop(i, R, C, INDIRECT(res.template get<i % C, i / C>() = get<i / C, i % C>()));
      return res;
    }

#ifdef LOCAL_DEBUG
    void debug_print(std::string_view name = "static_matrix") const {
      debugger::os << name << ": ";
      const auto padding = std::string(name.size() + 2, ' ');
      for (int i = 0; i < R; i++) {
        if (i > 0) debugger::os << padding;
        debugger::os << "[ ";
        for (int j = 0; j < C; j++)
          debugger::os << get(i, j) << " ";
        debugger::os << "]\n";
      }
    }
#else
    void debug_print(std::string_view) const noexcept {}
#endif
  };

  namespace internal {
    template <typename T> constexpr bool is_static_matrix_v                                                       = false;
    template <typename T, std::size_t R, std::size_t C> constexpr bool is_static_matrix_v<static_matrix<T, R, C>> = true;
  }  // namespace internal

  template <typename LhsType, typename Tp, std::size_t R, std::size_t C, std::enable_if_t<!internal::is_static_matrix_v<LhsType>, std::nullptr_t> = nullptr>
  constexpr static_matrix<Tp, R, C> operator*(const LhsType lhs, static_matrix<Tp, R, C> rhs) {
    static_loop(i, R, C, rhs.template get<i>() = lhs * rhs.template get<i>());
    return rhs;
  }
  template <typename RhsType, typename Tp, std::size_t R, std::size_t C, std::enable_if_t<!internal::is_static_matrix_v<RhsType>, std::nullptr_t> = nullptr>
  constexpr static_matrix<Tp, R, C> operator*(static_matrix<Tp, R, C> lhs, const RhsType rhs) {
    static_loop(i, R, C, lhs.template get<i>() *= rhs);
    return lhs;
  }
  template <typename RhsType, typename Tp, std::size_t R, std::size_t C, std::enable_if_t<!internal::is_static_matrix_v<RhsType>, std::nullptr_t> = nullptr>
  constexpr static_matrix<Tp, R, C>& operator*=(static_matrix<Tp, R, C>& lhs, const RhsType rhs) {
    static_loop(i, R, C, lhs.template get<i>() *= rhs);
    return lhs;
  }

  template <typename Tp, std::size_t R, std::size_t C> constexpr static_matrix<Tp, R, C> zero_matrix() {
    static_matrix<Tp, R, C> res;
    static_loop(i, R, C, res.template get<i>() = 0);
    return res;
  }
  template <typename Tp, std::size_t R> constexpr static_matrix<Tp, R, R> id_matrix() {
    static_matrix<Tp, R, R> res;
    static_loop(i, R, R, res.template get<i>() = ((i / R) == (i % R)));
    return res;
  }

  template <typename Tp, std::size_t N> using static_vector = static_matrix<Tp, N, 1>;

  template <typename Tp, std::size_t N> constexpr Tp dot(const static_vector<Tp, N>& lhs, const static_vector<Tp, N>& rhs) {
    Tp res = 0;
    [&]<std::size_t... i>(std::index_sequence<i...>) constexpr {
      ((res += lhs.template get<i, 0>() * rhs.template get<i, 0>()), ...);
    }
    (std::make_index_sequence<N> {});
    return res;
  }

  template <typename Tp> constexpr Tp cross(const static_vector<Tp, 2>& lhs, const static_vector<Tp, 2>& rhs) {
    return lhs.template get<0, 0>() * rhs.template get<1, 0>() - lhs.template get<1, 0>() * rhs.template get<0, 0>();
  }
  template <typename Tp> constexpr static_vector<Tp, 3> cross(const static_vector<Tp, 3>& lhs, const static_vector<Tp, 3>& rhs) {
    return static_vector<Tp, 3>({
      lhs.template get<1, 0>() * rhs.template get<2, 0>() - lhs.template get<2, 0>() * rhs.template get<1, 0>(),
      lhs.template get<2, 0>() * rhs.template get<0, 0>() - lhs.template get<0, 0>() * rhs.template get<2, 0>(),
      lhs.template get<0, 0>() * rhs.template get<1, 0>() - lhs.template get<1, 0>() * rhs.template get<0, 0>(),
    });
  }
}  // namespace lib

#undef static_loop
#define at(i, ...) template get<i, ##__VA_ARGS__>()

#pragma endregion

struct Int {
  int val;

  Int() {}
  Int(const int x) : val(x % 10) {}

  Int operator+(Int rhs) const {
    rhs.val += val;
    if (rhs.val >= 10) rhs.val -= 10;
    return rhs;
  }
  Int operator-(Int rhs) const {
    rhs.val -= val;
    if (rhs.val < 0) rhs.val += 10;
    return rhs;
  }
  Int operator*(Int rhs) const {
    rhs.val *= val;
    rhs.val %= 10;
    return rhs;
  }
  Int operator+=(Int rhs) {
    return (*this) = ((*this) + rhs);
  }
  Int operator-=(Int rhs) {
    return (*this) = ((*this) - rhs);
  }
  Int operator*=(Int rhs) {
    return (*this) = ((*this) * rhs);
  }
};

void solve() {
  int p, q, r;
  long long K;
  std::cin >> p >> q >> r >> K;

  auto M = lib::zero_matrix<Int, 3, 3>();
  auto V = lib::static_vector<Int, 3>();

  V.at(0) = p;
  V.at(1) = q;
  V.at(2) = r;

  M.at(0, 1) = M.at(1, 2) = M.at(2, 0) = M.at(2, 1) = M.at(2, 2) = 1;
  M.pow_self(K - 1);

  std::cout << (M * V).at(0).val << "\n";
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  solve();
}
yukicoder

結果

テストケース

ソースコード
