結果
問題 |
No.3224 2×2行列入門
|
ユーザー |
![]() |
提出日時 | 2025-08-08 21:24:51 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 17,493 bytes |
コンパイル時間 | 2,591 ms |
コンパイル使用メモリ | 282,584 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-08-08 21:24:58 |
合計ジャッジ時間 | 3,455 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> #include <cassert> using namespace std; using ll = long long int; using u64 = unsigned long long; using pll = pair<ll, ll>; // #include <atcoder/all> // using namespace atcoder; #define REP(i, a, b) for (ll i = (a); i < (b); i++) #define REPrev(i, a, b) for (ll i = (a); i >= (b); i--) #define ALL(coll) (coll).begin(), (coll).end() #define SIZE(v) ((ll)((v).size())) #define REPOUT(i, a, b, exp, sep) REP(i, (a), (b)) cout << (exp) << (i + 1 == (b) ? "" : (sep)); cout << "\n" // @@ !! LIM(matrix) // ---- inserted library file algOp.cc // Common definitions // zero, one, inverse template<typename T> const T zero(const T& t) { if constexpr (is_integral_v<T> || is_floating_point_v<T>) { return (T)0; } else { return t.zero(); } } template<typename T> const T one(const T& t) { if constexpr (is_integral_v<T> || is_floating_point_v<T>) { return (T)1; } else { return t.one(); } } template<typename T> const T inverse(const T& t) { if constexpr (is_floating_point_v<T>) { return 1.0 / t; } else { return t.inverse(); } } #ifdef BOOST_MP_CPP_INT_HPP template<> const cpp_int zero(const cpp_int& t) { return cpp_int(0); } template<> const cpp_int one(const cpp_int& t) { return cpp_int(1); } #endif // BOOST_MP_CPP_INT_HPP // begin -- detection ideom // cf. https://blog.tartanllama.xyz/detection-idiom/ namespace tartan_detail { template <template <class...> class Trait, class Enabler, class... Args> struct is_detected : false_type{}; template <template <class...> class Trait, class... Args> struct is_detected<Trait, void_t<Trait<Args...>>, Args...> : true_type{}; } template <template <class...> class Trait, class... Args> using is_detected = typename tartan_detail::is_detected<Trait, void, Args...>::type; // end -- detection ideom template<typename T> // using subst_add_t = decltype(T::subst_add(declval<typename T::value_type &>(), declval<typename T::value_type>())); using subst_add_t = decltype(T::subst_add); template<typename T> using has_subst_add = is_detected<subst_add_t, T>; template<typename T> using add_t = decltype(T::add); template<typename T> using has_add = is_detected<add_t, T>; template<typename T> using subst_mult_t = decltype(T::subst_mult); template<typename T> using has_subst_mult = is_detected<subst_mult_t, T>; template<typename T> using mult_t = decltype(T::mult); template<typename T> using has_mult = is_detected<mult_t, T>; template<typename T> using subst_subt_t = decltype(T::subst_subt); template<typename T> using has_subst_subt = is_detected<subst_subt_t, T>; template<typename T> using subt_t = decltype(T::subt); template<typename T> using has_subt = is_detected<subt_t, T>; template <typename Opdef> struct MyAlg { using T = typename Opdef::value_type; using value_type = T; T v; MyAlg() {} MyAlg(const T& v_) : v(v_) {} MyAlg(T&& v_) : v(move(v_)) {} bool operator==(MyAlg o) const { return v == o.v; } bool operator!=(MyAlg o) const { return v != o.v; } operator T() const { return v; } MyAlg zero() const { return MyAlg(Opdef::zero(v)); } MyAlg one() const { return MyAlg(Opdef::one(v)); } MyAlg inverse() const { return MyAlg(Opdef::inverse(v)); } MyAlg operator/=(const MyAlg& o) { return *this *= o.inverse(); } MyAlg operator/(const MyAlg& o) const { return (*this) * o.inverse(); } MyAlg operator-() const { return zero() - *this; } MyAlg& operator +=(const MyAlg& o) { if constexpr (has_subst_add<Opdef>::value) { Opdef::subst_add(v, o.v); return *this; }else if constexpr (has_add<Opdef>::value) { v = Opdef::add(v, o.v); return *this; }else static_assert("either subst_add or add is needed."); } MyAlg operator +(const MyAlg& o) const { if constexpr (has_add<Opdef>::value) { return MyAlg(Opdef::add(v, o.v)); }else if constexpr (has_subst_add<Opdef>::value) { MyAlg ret(v); Opdef::subst_add(ret.v, o.v); return ret; }else static_assert("either subst_add or add is needed."); } MyAlg& operator *=(const MyAlg& o) { if constexpr (has_subst_mult<Opdef>::value) { Opdef::subst_mult(v, o.v); return *this; }else if constexpr (has_mult<Opdef>::value) { v = Opdef::mult(v, o.v); return *this; }else static_assert("either subst_mult or mult is needed."); } MyAlg operator *(const MyAlg& o) const { if constexpr (has_mult<Opdef>::value) { return MyAlg(Opdef::mult(v, o.v)); }else if constexpr (has_subst_mult<Opdef>::value) { MyAlg ret(v); Opdef::subst_mult(ret.v, o.v); return ret; }else static_assert("either subst_mult or mult is needed."); } MyAlg& operator -=(const MyAlg& o) { if constexpr (has_subst_subt<Opdef>::value) { Opdef::subst_subt(v, o.v); return *this; }else if constexpr (has_subt<Opdef>::value) { v = Opdef::subt(v, o.v); return *this; }else static_assert("either subst_subt or subt is needed."); } MyAlg operator -(const MyAlg& o) const { if constexpr (has_subt<Opdef>::value) { return MyAlg(Opdef::subt(v, o.v)); }else if constexpr (has_subst_subt<Opdef>::value) { MyAlg ret(v); Opdef::subst_subt(ret.v, o.v); return ret; }else static_assert("either subst_subt or subt is needed."); } friend istream& operator >>(istream& is, MyAlg& t) { is >> t.v; return is; } friend ostream& operator <<(ostream& os, const MyAlg& t) { os << t.v; return os; } }; // ---- end algOp.cc // ---- inserted library file power.cc template<typename T> T power(const T& a, ll b) { auto two_pow = a; auto ret = one<T>(a); while (b > 0) { if (b & 1LL) ret *= two_pow; two_pow *= two_pow; b >>= 1; } return ret; } // a >= 0, b >= 0; If overflow, returns -1. ll llpower(ll a, ll b) { if (b == 0) return 1; // 0^0 == 1 if (b == 1) return a; if (a == 0) return 0; if (a == 1) return 1; if (a == 2) { if (b >= 63) return -1; else return 1LL << b; } if (b == 2) { ll ret; if (__builtin_smulll_overflow(a, a, &ret)) return -1; return ret; } ll two_pow = a; ll ret = 1; assert(b > 0); while (true) { if (b & 1LL) { if (__builtin_smulll_overflow(ret, two_pow, &ret)) return -1; } b >>= 1; if (b == 0) break; if (__builtin_smulll_overflow(two_pow, two_pow, &two_pow)) return -1; } return ret; } // a >= 0; Returns x s.t. x*x <= a < (x+1)*(x+1) ll llsqrt(ll a) { ll x = llround(sqrt((double)a)); ll y; if (__builtin_smulll_overflow(x, x, &y) or a < y) return x - 1; else return x; } // a >= 0, m >= 2; Returns x s.t. x^m <= a < (x + 1)^m ll llroot(ll a, ll m) { ll x = llround(pow(a, 1.0 / m)); ll y = llpower(x, m); if (y == -1 or a < y) return x - 1; else return x; } // base >= 2, a >= 1; Returns x s.t. base^{x} <= a < base^{x + 1} ll lllog(ll base, ll a) { ll x = llround(log(a) / log(base)); ll y = llpower(base, x); if (y == -1 or a < y) return x - 1; else return x; } // ---- end power.cc // ---- inserted library file matrix.cc template <typename T> struct Matrix { struct Part { const Matrix& mat; int i_size; int j_size; int i_0; int j_0; Part(const Matrix& mat_, int i_size_ = -1, int j_size_ = -1, int i_0_ = 0, int j_0_ = 0) : mat(mat_), i_size(i_size_ >= 0 ? i_size_ : mat.dimI), j_size(j_size_ >= 0 ? j_size_ : mat.dimJ), i_0(i_0_), j_0(j_0_) { if (i_0 + i_size > mat.dimI or j_0 + j_size > mat.dimJ) throw domain_error("part"); } }; int dimI; int dimJ; bool rev_rc = false; // if true, the order in mem is column->row vector<T> mem; T& at(int i, int j) { return rev_rc ? mem[j*dimI + i] : mem[i*dimJ + j]; } const T& at(int i, int j) const { return rev_rc ? mem[j*dimI + i] : mem[i*dimJ + j]; } Matrix() : dimI(1), dimJ(1), mem(1) {} Matrix(int dimI_, int dimJ_) : dimI(dimI_), dimJ(dimJ_), mem(dimI*dimJ) {} Matrix(int dimI_, int dimJ_, const T& t) : dimI(dimI_), dimJ(dimJ_), mem(dimI*dimJ, t) {} template<typename Z> void _from_vec(int dimI_, int dimJ_, Z&& vec) { int sz = vec.size(); dimI = dimI_ <= 0 ? sz / dimJ_ : dimI_; dimJ = dimJ_ <= 0 ? sz / dimI_ : dimJ_; if (dimI * dimJ != sz) throw domain_error("_from_vec: inconsistent sizes"); mem = forward<Z>(vec); } Matrix(int dimI_, int dimJ_, const vector<T>& vec) { _from_vec(dimI_, dimJ_, vec); } Matrix(int dimI_, int dimJ_, vector<T>&& vec) { _from_vec(dimI_, dimJ_, move(vec)); } Matrix(initializer_list<initializer_list<T>> il) { dimI = il.size(); if (dimI == 0) throw domain_error("from_il: zero rows"); dimJ = (*il.begin()).size(); if (dimJ == 0) throw domain_error("from_il: zero columns"); mem.resize(dimI * dimJ); int i = 0; for (auto it : il) { if ((int)it.size() != dimJ) throw domain_error("from_il: not in rectangular shape"); int j = 0; for (const T& t : it) mem[i * dimJ + (j++)] = t; i++; } } Matrix(const Part& cs) : dimI(cs.i_size), dimJ(cs.j_size), mem(dimI*dimJ) { for (int i = 0; i < dimI; i++) for (int j = 0; j < dimJ; j++) at(i, j) = cs.mat.at(cs.i_0 + i, cs.j_0 + j); } bool operator ==(const Matrix& r) const { if (dimI != r.dimI or dimJ != r.dimJ) return false; if (rev_rc == r.rev_rc) return mem == r.mem; for (int i = 0; i < dimI; i++) for (int j = 0; j < dimJ; j++) if (at(i, j) != r.at(i, j)) return false; return true; } bool operator !=(const Matrix& r) const { return !(*this == r); } T _zero_T() const { return ::zero<T>(at(0, 0)); } T _one_T() const { return ::one<T>(at(0, 0)); } template<int sign> Matrix& _add_subt(const Matrix& r) { if (dimI != r.dimI or dimJ != r.dimJ) throw domain_error("_add_subt: dimension mismatch"); for (int i = 0; i < dimI; i++) for (int j = 0; j < dimJ; j++) { if constexpr (sign > 0) at(i, j) += r.at(i, j); else at(i, j) -= r.at(i, j); } return *this; } Matrix& operator +=(const Matrix& r) { return _add_subt<1>(r); } Matrix& operator -=(const Matrix& r) { return _add_subt<-1>(r); } Matrix operator +(const Matrix& r) const { return Matrix(*this) += r; } Matrix operator -(const Matrix& r) const { return Matrix(*this) -= r; } Matrix operator *(const Matrix& r) const { if (dimJ != r.dimI) throw domain_error("mult: dimension mismatch"); Matrix result(dimI, r.dimJ, _zero_T()); for (int i = 0; i < dimI; i++) for (int j = 0; j < r.dimJ; j++) { for (int k = 0; k < dimJ; k++) result.at(i, j) += at(i, k) * r.at(k, j); } return result; } Matrix& operator *=(const Matrix& r) { return *this = *this * r; } Matrix& operator *=(const T& t) { for (int p = 0; p < dimI * dimJ; p++) mem[p] *= t; return *this; } friend Matrix operator *(const Matrix& mat, const T& t) { return Matrix(mat) *= t; } friend Matrix operator *(const T& t, const Matrix& mat) { // Mult of T might be non-commutative Matrix ret(mat); for (int p = 0; p < mat.dimI * mat.dimJ; p++) ret.mem[p] = t * ret.mem[p]; return ret; } vector<T> operator *(const vector<T>& vec) const { auto m = (*this) * Matrix(0, 1, vec); return m.mem; } vector<T> operator *(vector<T>&& vec) const { auto m = (*this) * Matrix(0, 1, move(vec)); return m.mem; } static Matrix from_vvec(const vector<vector<T>>& vvec) { int dimI_ = vvec.size(); if (dimI_ == 0) throw domain_error("from_vvec: zero rows"); int dimJ_ = vvec[0].size(); if (dimJ_ == 0) throw domain_error("from_vvec: zero columns"); Matrix ret(dimI_, dimJ_); for (int i = 0; i < dimI_; i++) { if ((int)vvec[i].size() != dimJ_) throw domain_error("from_vvec: not in rectangular shape"); for (int j = 0; j < dimJ_; j++) ret.mem[i*dimJ_ + j] = vvec[i][j]; } return ret; } Matrix zero() const { return Matrix(dimI, dimJ, _zero_T()); } Matrix unit() const { if (dimI != dimJ) throw domain_error("unit: dimension mismatch"); Matrix ret(dimI, dimI, _zero_T()); for (int i = 0; i < dimI; i++) ret.at(i, i) = _one_T(); return ret; } Matrix one() const { return unit(); } // for general operation Ring Part part(int i_size_ = -1, int j_size_ = -1, int i_0_ = 0, int j_0_ = 0) const { return Part(*this, i_size_, j_size_, i_0_, j_0_); } Matrix rowVec(int i) const { return Matrix(part(1, -1, i, 0)); } Matrix colVec(int j) const { return Matrix(part(-1, 1, 0, j)); } void memcopy(const Part& cs, int i_1 = 0, int j_1 = 0) { for (int i = 0; i < cs.i_size; i++) for (int j = 0; j < cs.j_size; j++) { at(i_1 + i, j_1 + j) = cs.mat.at(cs.i_0 + i, cs.j_0 + j); } } Matrix matpower(ll x) const { return power<Matrix>(*this, x); } Matrix& self_transpose() { rev_rc = not rev_rc; swap(dimI, dimJ); return *this; } Matrix transpose() { return Matrix(*this).self_transpose(); } /* aux functions for sweepout */ void basic_mult(int i, T t) { // multiplies i-th row by t for (int j = 0; j < dimJ; j++) at(i, j) *= t; } void basic_xchg(int i1, int i2) { // exchanges i1-th and i2-th rows for (int j = 0; j < dimJ; j++) swap(at(i1, j), at(i2, j)); } void basic_mult_add(int i1, T t, int i2) { // adds t times of i1-th row to i2-th row for (int j = 0; j < dimJ; j++) at(i2, j) += t * at(i1, j); } pair<int, int> _find_nz(int i0, int j0) const { for ( ; j0 < dimJ; j0++) { int i = i0; for ( ; i < dimI && at(i, j0) == _zero_T(); i++); if (i < dimI) return {i, j0}; } return {dimI, dimJ}; } pair<int, T> self_sweepout() { T det = _one_T(); int j0 = 0; int i0 = 0; for ( ; i0 < dimI; i0++, j0++) { auto [i1, j1] = _find_nz(i0, j0); if (i1 == dimI) break; j0 = j1; if (i1 != i0) { det = -det; basic_xchg(i0, i1); } det *= at(i0, j0); basic_mult(i0, ::inverse<T>(at(i0, j0))); for (int i = 0; i < dimI; i++) { if (i == i0) continue; basic_mult_add(i0, -at(i, j0), i); } } return {i0, move(det)}; } pair<int, T> sweepout() const { Matrix res1(*this); return res1.self_sweepout(); } T determinant() const { auto [rank, det] = sweepout(); return (rank == dimI) ? det : _zero_T(); } optional<Matrix> inv() const { if (dimI != dimJ) throw domain_error("inv: not square"); Matrix work(dimI, dimI * 2); work.memcopy(part()); work.memcopy(unit().part(), 0, dimI); work.self_sweepout(); if (work.at(dimI - 1, dimI - 1) != _one_T()) return {}; Matrix ret(dimI, dimI); ret.memcopy(work.part(dimI, dimI, 0, dimI)); return ret; } Matrix inverse() const { return inv().value(); } // for general operation of Ring / Semi Ring template<bool ret_kernel = false> optional<pair<Matrix, vector<Matrix>>> linSolution(const Matrix& bs) const { if (dimI != bs.dimI or bs.dimJ != 1) throw domain_error("linSolution: invalid bs"); Matrix work(dimI, dimJ + 1); work.memcopy(part()); work.memcopy(bs.part(), 0, dimJ); auto [rank, _] = work.self_sweepout(); Matrix sol(dimJ, 1); vector<Matrix> kernel; if (rank == 0) { if constexpr (not ret_kernel) return make_pair(move(sol), move(kernel)); for (int j = 0; j < dimJ; j++) { Matrix m(dimJ, 1); m.at(j, 0) = _one_T(); kernel.push_back(m); } return make_pair(move(sol), move(kernel)); } if (not ([&]() -> bool { for (int j = 0; j < dimJ; j++) if (work.at(rank - 1, j) != _zero_T()) return true; return false; })()) return nullopt; for (int i = 0, j = 0; i < rank; i++, j++) { for ( ; work.at(i, j) == _zero_T(); j++); sol.at(j, 0) = work.at(i, dimJ); } if constexpr (not ret_kernel) return make_pair(move(sol), move(kernel)); vector<bool> cor(dimJ, false); int i = 0; for (int j = 0 ; j < dimJ; j++) { if (i == dimI || work.at(i, j) == _zero_T()) { Matrix vec(dimJ, 1); vec.at(j, 0) = _one_T(); for (int p = 0, q = 0; p < i; p++, q++) { while (!cor[q]) q++; vec.at(q, 0) = -work.at(p, j); } kernel.push_back(move(vec)); }else { cor[j] = true; if (i < dimI) i++; } } return make_pair(move(sol), move(kernel)); } friend istream& operator >>(istream& is, Matrix& mat) { is >> mat.dimI >> mat.dimJ; mat.rev_rc = false; mat.mem.resize(mat.dimI * mat.dimJ); for (int i = 0; i < mat.dimI; i++) for (int j = 0; j < mat.dimJ; j++) is >> mat.at(i, j); return is; } friend ostream& operator <<(ostream& os, const Matrix& mat) { for (int i = 0; i < mat.dimI; i++) { for (int j = 0; j < mat.dimJ; j++) { if (j > 0) os << ", "; os << mat.at(i, j); } os << "\n"; } return os; } }; // ---- end matrix.cc // @@ !! LIM -- end mark -- int main(/* int argc, char *argv[] */) { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << setprecision(20); ll a1, b1, c1, d1; cin >> a1 >> b1 >> c1 >> d1; ll a2, b2, c2, d2; cin >> a2 >> b2 >> c2 >> d2; Matrix mat1(2, 2, vector<ll>{a1, b1, c1, d1}); Matrix mat2(2, 2, vector<ll>{a2, b2, c2, d2}); Matrix ans = mat1 * mat2 * mat1 * mat2; cout << ans.at(0, 0) << " " << ans.at(0, 1) << "\n"; cout << ans.at(1, 0) << " " << ans.at(1, 1) << "\n"; return 0; }