#include using namespace std; #define overload2(a, b, c, ...) c #define overload3(a, b, c, d, ...) d #define overload4(a, b, c, d, e ...) e #define overload5(a, b, c, d, e, f ...) f #define overload6(a, b, c, d, e, f, g ...) g #define fast_io ios::sync_with_stdio(false); cin.tie(nullptr); #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") typedef long long ll; typedef long double ld; #define chmin(a,b) a = min(a,b); #define chmax(a,b) a = max(a,b); #define bit_count(x) __builtin_popcountll(x) #define leading_zero_count(x) __builtin_clz(x) #define trailing_zero_count(x) __builtin_ctz(x) #define gcd(a,b) __gcd(a,b) #define lcm(a,b) a / gcd(a,b) * b #define rep(...) overload3(__VA_ARGS__, rrep, rep1)(__VA_ARGS__) #define rep1(i,n) for(int i = 0 ; i < n ; i++) #define rrep(i,a,b) for(int i = a ; i < b ; i++) #define repi(it,S) for(auto it = S.begin() ; it != S.end() ; it++) #define pt(a) cout << a << endl; #define print(...) printall(__VA_ARGS__); #define debug(a) cout << #a << " " << a << endl; #define all(a) a.begin(), a.end() #define endl "\n"; #define v1(T,n,a) vector(n,a) #define v2(T,n,m,a) vector>(n,v1(T,m,a)) #define v3(T,n,m,k,a) vector>>(n,v2(T,m,k,a)) #define v4(T,n,m,k,l,a) vector>>>(n,v3(T,m,k,l,a)) templateistream &operator>>(istream&is,pair&p){is>>p.first>>p.second;return is;} templateostream &operator<<(ostream&os,const pair&p){os<istream &operator>>(istream&is,vector&v){for(T &in:v){is>>in;}return is;} templateostream &operator<<(ostream&os,const vector&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;} templateistream &operator>>(istream&is,vector>&v){for(T &in:v){is>>in;}return is;} templateostream &operator<<(ostream&os,const vector>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?"\n":"");}return os;} templateostream &operator<<(ostream&os,const set&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;} templateostream &operator<<(ostream&os,const multiset&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;} template void printall(Args... args){for(auto i:initializer_list>{args...}) cout< struct Matrix{ int row, col; vector> mat ; private: void init_(vector> A){ row = A.size(); col = A[0].size(); mat = A; } void init_(vector A, bool row_matrix = false){ if(row_matrix) { col = (int)A.size(); row = 1; mat.resize(1); mat[0] = A; } else { col = 1; row = (int)A.size(); mat.resize(row,vector(1)); rep(i,row) mat[i][0] = A[i]; } } Matrix pow_(ll k){ assert(row == col); vector> E(row,vector(row,0)); rep(i,row) rep(j,row) if(i == j) E[i][j] = 1; Matrix res(E); Matrix X(mat); while(k > 0){ if(k & 1) res *= X; X *= X; k >>= 1 ; } return res; } void transpose_() { vector> res(col,vector(row)); rep(i,row) rep(j,col) res[j][i] = mat[i][j]; mat = res; swap(row,col); } void concat_col_(vector &Y) { Matrix X(Y); concat_col_(X); } void concat_col_(vector> &Y) { Matrix X(Y); concat_col_(X); } void concat_col_(Matrix &Y) { assert((int)Y.row == row); col += Y.col; rep(i,row) { rep(j,Y.col) mat[i].push_back(Y.mat[i][j]); } } void concat_row_(vector &Y) { Matrix X(Y,true); concat_row_(X); } void concat_row_(vector> &Y) { Matrix X(Y); concat_row_(X); } void concat_row_(Matrix &Y) { assert((int)Y.col == col); row += Y.row; rep(i,Y.row) mat.push_back(Y.mat[i]); } void print_() { rep(i,row){ rep(j,col) cout << mat[i][j] << " "; cout << endl; } } public: inline Matrix &operator+=(const Matrix Y) { rep(i,row) rep(j,col) mat[i][j] += Y.mat[i][j]; return *this ; } inline Matrix &operator-=(const Matrix Y) { rep(i,row) rep(j,col) mat[i][j] -= Y.mat[i][j]; return *this ; } inline Matrix &operator*=(const Matrix Y) { int x = row, y = Y.col, n = col; vector> res(x,vector(y)); rep(i,x) rep(j,y) rep(k,n) res[i][j] += mat[i][k] * Y.mat[k][j]; swap(mat,res); row = x; col = y; return *this ; } inline Matrix operator-() const { rep(i,row) rep(j,col) mat[i][j] *= -1; return *this ; } inline Matrix operator+(const Matrix Y) const { return Matrix(*this) += Y; } inline Matrix operator-(const Matrix Y) const { return Matrix(*this) -= Y; } inline Matrix operator*(const Matrix Y) const { return Matrix(*this) *= Y; } inline bool operator==(const Matrix Y) const { return mat == Y.mat; } inline bool operator!=(const Matrix Y) const { return mat != Y.mat; } inline vector&operator[](int i) { return mat[i] ; } Matrix(int n): row(n), col(0) { mat.resize(row); } Matrix(vector A, bool row_matrix = false) { init_(A, row_matrix); } Matrix(vector> A){ init_(A); } void init(vector A, bool row_matrix = false) { init_(A, row_matrix); } void init(vector> A) { init_(A); } size_t row_size() { return row; } size_t col_size() { return col; } Matrix pow(ll k){ return pow_(k); } void transpose() { transpose_(); } void concat_col(vector> &Y) { concat_col_(Y); } void concat_col(vector &Y) { concat_col_(Y); } void concat_col(Matrix &Y) { concat_col_(Y); } void concat_row(vector> &Y) { concat_row_(Y); } void concat_row(vector &Y) { concat_row_(Y); } void concat_row(Matrix &Y) { concat_row_(Y); } }; // function : return : description // ----------------------------------------------------- // init(vector, row_matrix) : void : 1次元ベクトルに対して行列化する, 列行列か行行列を選択できる // init(vector>) : void : 2次元ベクトルに対して行列化する // row_size() : int : 行の大きさ // col_size() : int : 列の大きさ // pow(k) : Matrix : 行列をk乗する(n * n 行列であること) // transpose() : void : 転置する // concat_col(vector>) : void : 列に関して結合する // concat_col(vector) : void : 列に関して結合する // concat_col(Matrix) : void : 列に関して結合する // concat_row(vector>) : void : 列に関して結合する // concat_row(vector) : void : 列に関して結合する // concat_row(Matrix) : void : 列に関して結合する // print() : void : 行列を出力する // *注意* 取り敢えず全てをコピペすることを奨励 // verify // https://atcoder.jp/contests/dp/tasks/dp_r int n; void solve(){ int a, b, c, d; cin >> a >> b >> c >> d; Matrix mat({{a,b},{c,d}}); mat = mat.pow(3); cout << mat[0][0] << " " << mat[0][1] << endl; cout << mat[1][0] << " " << mat[1][1] << endl; } int main(){ fast_io int t = 1; // cin >> t; rep(i,t) solve(); }