#907528 (C++23) No.2441 行列累乗

提出ソース

結果

問題	No.2441 行列累乗
ユーザー	shirokami
提出日時	2023-08-25 21:21:18
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	3 ms / 2,000 ms
コード長	9,460 bytes
コンパイル時間	5,033 ms
コンパイル使用メモリ	333,240 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-06-06 15:34:45
合計ジャッジ時間	5,740 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 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	1 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	2 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	3 ms 5,376 KB
testcase_19	AC	2 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/extc++.h>
using namespace std;
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// using namespace __gnu_pbds;
// #include <boost/multiprecision/cpp_int.hpp>
// using Bint = boost::multiprecision::cpp_int;
// #include <atcoder/all>
// using namespace atcoder;
// https://atcoder.github.io/ac-library/production/document_ja/
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
constexpr ll mod = 1e9+7;
constexpr ll INF = 9'223'372'036'854'775'807/10;
#define rep(i,n) for (uint i = 0; i < uint(n); ++i)
#define All(a) (a).begin(),(a).end()
#define PI acos(-1)
vector<ll> dx = {1, 0, -1, 0, 1, 1, -1, -1};
vector<ll> dy = {0, 1, 0, -1, 1, -1, 1, -1};
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
struct Edge {
  uint from, to;
  long long cost;
  int idx;

  Edge() {}
  Edge(uint from_, uint to_, long long cost_ = 1, int idx_ = -1) : from(from_), to(to_), cost(cost_), idx(idx_) {}

  bool operator<(const Edge &e) const { return cost < e.cost; }
  bool operator>(const Edge &e) const { return cost > e.cost; }

  friend ostream& operator<<(ostream& os, const Edge& e) {
    os << e.from << " " << e.to << " (" << e.cost << ")";
    return os;
  }
};
struct Graph {
  vector<vector<Edge>> G;
  vector<Edge> edges;
  int idx = 0;
  
  Graph() {}
  Graph(uint n) : G(n) {}

  void add_edge_direct(uint from, uint to, ll cost = 1) {
    G[from].emplace_back(from, to, cost, idx);
    edges.emplace_back(from, to, cost, idx);
    idx++;
  }

  void add_edge(uint from, uint to, ll cost = 1) {
    G[from].emplace_back(from, to, cost, idx);
    G[to].emplace_back(to, from, cost, idx);
    edges.emplace_back(from, to, cost, idx);
    idx++;
  }

  size_t size() const { return G.size(); }

  vector<Edge>& operator[](int k) { return G[k]; }

  friend ostream& operator<<(ostream& os, Graph& g) {
    for (uint i = 0; i < g.size(); i++) {
      for (Edge e : g[i]) {
        cout << e << '\n';
      }
    }
    return os;
  }
};
struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << setprecision(15) << fixed;
  }
} iosetup;
void print(const vector<string> &v) {
  for (string s : v) {
    cout << s << '\n';
  }
}
template<typename T>
void print(const vector<pair<T, T>> &v, uint w = 0) {
  for (uint i = 0; i < (uint)v.size(); i++) {
    cout << right << setw(w) << v[i].first << ' ' << v[i].second << '\n';
  }
}
template<typename T>
void print(const vector<T> &v, uint w = 0) {
  for (uint i = 0; i < (uint)v.size(); i++) {
    cout << right << setw(w) << v[i] << " \n"[i == (int)v.size() - 1];
  }
}
template<typename T>
void print(const vector<vector<T>> &v, uint w = 0) {
  for (uint i = 0; i < (uint)v.size(); i++) {
    print(v[i], w);
  }
}
template<typename T>
void print(const T& arg) {
  cout << arg << '\n';
}
template<typename T, typename... Args>
void print(const T& arg, const Args&... args) {
  cout << arg << ' ';
  print(args...);
}
template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
  for (auto& x : vec) is >> x;
  return is;
}

template<typename T>
struct Matrix {
    int cols, rows;
    vector<vector<T>> mat;
    Matrix(int n, int m) : cols(m), rows(n), mat(n, vector<T>(m)) {}
    Matrix(int n) : cols(n), rows(n), mat(n, vector<T>(n)) {}
    Matrix(vector<vector<T>> &v) : mat(v) {
        rows = mat.size();
        cols = mat[0].size();
    }
    Matrix(vector<T> &v) : mat(v, 1) {
        rows = mat.size();
        cols = mat[0].size();
    }
    Matrix(initializer_list<vector<T>> v) : mat(v) {
        rows = mat.size();
        cols = mat[0].size();
    }
    

    // 要素アクセス
    vector<T>& operator[](int i) {
        return mat[i];
    }
    T& operator()(int i, int j) {
        return mat[i][j];
    }

    // 単位行列
    Matrix eye(int n) {
        Matrix res(n);
        for (int i = 0; i < n; i++) {
            res.mat[i][i] = 1;
        }
        return res;
    }

    // 足し算
    Matrix operator+(const Matrix& rhs) const {
        assert(rows == rhs.rows && cols == rhs.cols);
        Matrix res(rows, cols);
        for (int i = 0; i < rows; i++) {
            for (int j = 0;j < cols; j++) {
                res.mat[i][j] = mat[i][j] + rhs.mat[i][j];
            }
        }
        return res;
    }
    // 足し算の代入
    Matrix& operator+=(const Matrix& rhs) {
        assert(rows == rhs.rows && cols == rhs.cols);
        for (int i = 0; i < rows; i++) {
            for (int j = 0;j < cols; j++) {
                mat[i][j] += rhs.mat[i][j];
            }
        }
        return *this;
    }
    // 引き算
    Matrix operator-(const Matrix& rhs) const {
        assert(rows == rhs.rows && cols == rhs.cols);
        Matrix res(rows, cols);
        for (int i = 0; i < rows; i++) {
            for (int j = 0;j < cols; j++) {
                res.mat[i][j] = mat[i][j] - rhs.mat[i][j];
            }
        }
        return res;
    }
    // 引き算の代入
    Matrix& operator-=(const Matrix& rhs) {
        assert(rows == rhs.rows && cols == rhs.cols);
        for (int i = 0; i < rows; i++) {
            for (int j = 0;j < cols; j++) {
                mat[i][j] -= rhs.mat[i][j];
            }
        }
        return *this;
    }
    // 掛け算
    Matrix operator*(const Matrix& rhs) const {
        assert(cols == rhs.rows);
        Matrix res(rows, rhs.cols);
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < rhs.cols; j++) {
                for (int k = 0; k < cols; k++) {
                    res.mat[i][j] += mat[i][k] * rhs.mat[k][j];
                }
            }
        }
        return res;
    }
    // 掛け算の代入
    Matrix& operator*=(const Matrix& rhs) {
        assert(cols == rhs.rows);
        Matrix res(rows, rhs.cols);
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < rhs.cols; j++) {
                for (int k = 0; k < cols; k++) {
                    res.mat[i][j] += mat[i][k] * rhs.mat[k][j];
                }
            }
        }
        *this = res;
        return *this;
    }
    // スカラー倍
    Matrix operator*(const long long& rhs) const {
        Matrix res(rows, cols);
        for (int i = 0; i < rows; i++) {
            for (int j = 0;j < cols; j++) {
                res.mat[i][j] = mat[i][j] * rhs;
            }
        }
        return res;
    }
    // スカラー倍の代入
    Matrix& operator*=(const long long& rhs) {
        for (int i = 0; i < rows; i++) {
            for (int j = 0;j < cols; j++) {
                mat[i][j] *= rhs;
            }
        }
        return *this;
    }
    // スカラー逆数倍
    Matrix operator/(const long long& rhs) const {
        Matrix res(rows, cols);
        for (int i = 0; i < rows; i++) {
            for (int j = 0;j < cols; j++) {
                res.mat[i][j] = mat[i][j] / rhs;
            }
        }
        return res;
    }
    // スカラー逆数倍の代入
    Matrix& operator/=(const long long& rhs) {
        for (int i = 0; i < rows; i++) {
            for (int j = 0;j < cols; j++) {
                mat[i][j] /= rhs;
            }
        }
        return *this;
    }

    // 転置
    Matrix transpose() const {
        Matrix res(cols, rows);
        for (int i = 0; i < cols; i++) {
            for (int j = 0;j < rows; j++) {
                res.mat[i][j] = mat[j][i];
            }
        }
        return res;
    }
    // 内積
    long long dot(const Matrix& rhs) const {
        assert(rows == 1 && rhs.rows == 1 && cols == rhs.cols);
        long long res = 0;
        for (int i = 0; i < cols; i++) {
            res += mat[0][i] * rhs.mat[0][i];
        }
        return res;
    }
    long long dot(const vector<long long>& rhs) const {
        assert(rows == 1 && cols == rhs.size());
        long long res = 0;
        for (int i = 0; i < cols; i++) {
            res += mat[0][i] * rhs[i];
        }
        return res;
    }
    // 外積
    Matrix cross(const Matrix& rhs) const {
        assert(rows == 1 && rhs.rows == 1 && cols == rhs.cols && cols == 3);
        Matrix res(1, 3);
        res.mat[0][0] = mat[0][1] * rhs.mat[0][2] - mat[0][2] * rhs.mat[0][1];
        res.mat[0][1] = mat[0][2] * rhs.mat[0][0] - mat[0][0] * rhs.mat[0][2];
        res.mat[0][2] = mat[0][0] * rhs.mat[0][1] - mat[0][1] * rhs.mat[0][0];
        return res;
    }

    // 累乗
    Matrix pow(long long n) const {
        assert(rows == cols);
        Matrix res(rows, cols);
        Matrix x = *this;
        for (int i = 0; i < rows; i++) {
            res.mat[i][i] = 1;
        }
        while (n > 0) {
            if (n & 1) res *= x;
            x *= x;
            n >>= 1;
        }
        return res;
    }


};
template <typename T>
void print(Matrix<T> a, int w = 1) {
  cout << "Matrix: " << a.rows << " x " << a.cols << endl;
  for (int i = 0; i < a.rows; i++) {
    for (int j = 0; j < a.cols; j++) {
      cout << right << setw(w);
      cout << a.mat[i][j] << " \n"[j == a.cols - 1];
    }
  }
}

void solve() {
  vector<vector<ll>> a(2, vector<ll>(2));
  rep(i, 2) rep(j, 2) cin >> a[i][j];
  Matrix<ll> A(a);
  A = A.pow(3);
  rep(i,2) rep(j,2) cout << A[i][j] << " \n"[j==1];
}

int main() {
  uint t = 1;
  // cin >> t;
  while (t--) {
    solve();
  }
}

yukicoder

結果

テストケース

ソースコード