// https://github.com/primesosu91/library #include #include using namespace std; using ll = long long; using ld = long double; using pll = pair; #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 bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; } template bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; } // Tは0・1から構築でき、使用する演算に応じて加算・減算・乗算が可能であること。 // 演算の中間値がTの範囲内に収まること。添字は0-index。 template struct Matrix { private: int height, width; vector> 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(w, value)); } // 配列から構築: Matrix(a) -> aのコピー (前提: 長方形、行数・列数はintの範囲内) // 空配列は0行0列として扱う。 Matrix(const vector>& a) { assert(a.size() <= (size_t)numeric_limits::max()); assert(a.empty() || a[0].size() <= (size_t)numeric_limits::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& operator[](int i) { assert(0 <= i && i < height); return data[i]; } // 行取得(const): a[i] -> i行目へのconst参照 (前提: 0 <= i < rows()) const vector& 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> a(2, vector(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(); }