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

• 問題: No.2441 行列累乗
• ユーザー: primesosu
• 提出日時: 2026-11-12 22:53:10
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1 ms / 2,000 ms
• コード長: 5,892 bytes
• コンパイル時間: 3,090 ms
• コンパイル使用メモリ: 368,300 KB
• 実行使用メモリ: 9,864 KB
• 最終ジャッジ日時: 2026-11-12 22:53:15
• 合計ジャッジ時間: 4,604 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge4_0

ファイルパターン	結果
other	AC * 20

ソースコード

// https://github.com/primesosu91/library
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i <= (ll)(n); i++)
#define rrep(i, n) for (ll i = n - 1; i >= (ll)(0); i--)
#define rrep1(i, n) for (ll i = n; i >= (ll)(1); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define el '\n'
#define sp ' '
#define YN(text) cout << (text ? "Yes" : "No") << el;
#define ANS cout << ans << el;
#define pqmax(...) priority_queue<__VA_ARGS__>
#define pqmin(...) priority_queue<__VA_ARGS__, vector<__VA_ARGS__>, greater<__VA_ARGS__>>
const ll inf = 4e18;
const ll MOD = 998244353;
const ll dx[4] = {1, 0, -1, 0};
const ll dy[4] = {0, 1, 0, -1};
const ll DX[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll DY[8] = {0, 1, 1, 1, 0, -1, -1, -1};
template <class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }
template <class T> bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }


// Tは0・1から構築でき、使用する演算に応じて加算・減算・乗算が可能であること。
// 演算の中間値がTの範囲内に収まること。添字は0-index。
template<class T>
struct Matrix {
private:
    int height, width;
    vector<vector<T>> data;

public:
    // 初期化: Matrix(h,w,value) -> h行w列をvalueで埋める (前提: h,w >= 0)
    Matrix(int h, int w, T value = T(0)) : height(h), width(w) {
        assert(h >= 0 && w >= 0);
        data.assign(h, vector<T>(w, value));
    }

    // 配列から構築: Matrix(a) -> aのコピー (前提: 長方形、行数・列数はintの範囲内)
    // 空配列は0行0列として扱う。
    Matrix(const vector<vector<T>>& a) {
        assert(a.size() <= (size_t)numeric_limits<int>::max());
        assert(a.empty() || a[0].size() <= (size_t)numeric_limits<int>::max());
        height = (int)a.size();
        width = a.empty() ? 0 : (int)a[0].size();
        for (const auto& row : a) {
            assert(row.size() == (size_t)width);
            (void)row;
        }
        data = a;
    }

    // 行数取得: rows() -> 行数
    int rows() const { return height; }

    // 列数取得: cols() -> 列数
    int cols() const { return width; }

    // 行取得: a[i] -> i行目への参照 (前提: 0 <= i < rows(); 行の長さを変更しない)
    // a[i][j]の列添字は0 <= j < cols()を満たすこと。
    vector<T>& operator[](int i) {
        assert(0 <= i && i < height);
        return data[i];
    }

    // 行取得(const): a[i] -> i行目へのconst参照 (前提: 0 <= i < rows())
    const vector<T>& operator[](int i) const {
        assert(0 <= i && i < height);
        return data[i];
    }

    // 単位行列: identity(n) -> n次単位行列 (前提: n >= 0)
    static Matrix identity(int n) {
        Matrix result(n, n);
        for (int i = 0; i < n; i++) result.data[i][i] = T(1);
        return result;
    }

    // 加算代入: a += b -> aにbを加え自身の参照を返す (前提: 同じ行数・列数)
    Matrix& operator+=(const Matrix& other) {
        assert(height == other.height && width == other.width);
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) data[i][j] += other.data[i][j];
        }
        return *this;
    }

    // 減算代入: a -= b -> aからbを引き自身の参照を返す (前提: 同じ行数・列数)
    Matrix& operator-=(const Matrix& other) {
        assert(height == other.height && width == other.width);
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) data[i][j] -= other.data[i][j];
        }
        return *this;
    }

    // 加算: a + b -> 和を返す (前提: 同じ行数・列数)
    Matrix operator+(const Matrix& other) const {
        Matrix result = *this;
        result += other;
        return result;
    }

    // 減算: a - b -> 差を返す (前提: 同じ行数・列数)
    Matrix operator-(const Matrix& other) const {
        Matrix result = *this;
        result -= other;
        return result;
    }

    // 行列積: a * b -> 積を返す (前提: a.cols() == b.rows())
    Matrix operator*(const Matrix& other) const {
        assert(width == other.height);
        Matrix result(height, other.width);
        // i,k,jの順に走査し、右行列と結果の行を連続して参照する。
        for (int i = 0; i < height; i++) {
            for (int k = 0; k < width; k++) {
                for (int j = 0; j < other.width; j++) {
                    result.data[i][j] += data[i][k] * other.data[k][j];
                }
            }
        }
        return result;
    }

    // 乗算代入: a *= b -> 積をaに代入し自身の参照を返す (前提: a.cols() == b.rows())
    Matrix& operator*=(const Matrix& other) {
        *this = *this * other;
        return *this;
    }

    // 累乗: pow(k) -> 自身のk乗を返す (前提: 正方行列、k >= 0; 0乗は単位行列)
    Matrix pow(long long k) const {
        assert(height == width && k >= 0);
        Matrix result = identity(height);
        Matrix base = *this;
        // 二分累乗。最後の不要な二乗は行わず、余分なオーバーフローを避ける。
        while (k > 0) {
            if (k & 1) result *= base;
            k >>= 1;
            if (k > 0) base *= base;
        }
        return result;
    }
};

void solve() {
    ll n = 2;
    vector<vector<ll>> a(2, vector<ll>(2));
    rep(i,n) rep(j,n) cin >> a[i][j];
    Matrix m(a);
    rep(i,n) rep(j,n) cout << m.pow(3)[i][j] << (j == n-1 ? el : sp);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll t = 1;
    // cin >> t;
    rep(i, t) solve();
}