結果
| 問題 | No.2441 行列累乗 |
| ユーザー |
 asaringo
|
| 提出日時 | 2023-08-26 11:44:52 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 8,561 bytes |
| コンパイル時間 | 2,506 ms |
| コンパイル使用メモリ | 216,340 KB |
| 実行使用メモリ | 4,388 KB |
| 最終ジャッジ日時 | 2023-08-26 11:44:56 |
| 合計ジャッジ時間 | 3,518 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,380 KB |
| testcase_01 | AC | 2 ms
4,384 KB |
| testcase_02 | AC | 1 ms
4,380 KB |
| testcase_03 | AC | 2 ms
4,384 KB |
| testcase_04 | AC | 1 ms
4,380 KB |
| testcase_05 | AC | 1 ms
4,384 KB |
| testcase_06 | AC | 2 ms
4,380 KB |
| testcase_07 | AC | 1 ms
4,380 KB |
| testcase_08 | AC | 1 ms
4,380 KB |
| testcase_09 | AC | 1 ms
4,384 KB |
| testcase_10 | AC | 1 ms
4,384 KB |
| testcase_11 | AC | 1 ms
4,380 KB |
| testcase_12 | AC | 1 ms
4,384 KB |
| testcase_13 | AC | 1 ms
4,388 KB |
| testcase_14 | AC | 1 ms
4,380 KB |
| testcase_15 | AC | 1 ms
4,388 KB |
| testcase_16 | AC | 1 ms
4,380 KB |
| testcase_17 | AC | 1 ms
4,380 KB |
| testcase_18 | AC | 1 ms
4,380 KB |
| testcase_19 | AC | 2 ms
4,380 KB |
ソースコード
#include <bits/stdc++.h>
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<T>(n,a)
#define v2(T,n,m,a) vector<vector<T>>(n,v1(T,m,a))
#define v3(T,n,m,k,a) vector<vector<vector<T>>>(n,v2(T,m,k,a))
#define v4(T,n,m,k,l,a) vector<vector<vector<vector<T>>>>(n,v3(T,m,k,l,a))
template<typename T,typename U>istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<typename T,typename U>ostream &operator<<(ostream&os,const pair<T,U>&p){os<<p.first<<" "<<p.second;return os;}
template<typename T>istream &operator>>(istream&is,vector<T>&v){for(T &in:v){is>>in;}return is;}
template<typename T>ostream &operator<<(ostream&os,const vector<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;}
template<typename T>istream &operator>>(istream&is,vector<vector<T>>&v){for(T &in:v){is>>in;}return is;}
template<typename T>ostream &operator<<(ostream&os,const vector<vector<T>>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?"\n":"");}return os;}
template<typename T>ostream &operator<<(ostream&os,const set<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;}
template<typename T>ostream &operator<<(ostream&os,const multiset<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;}
template<class... Args> void printall(Args... args){for(auto i:initializer_list<common_type_t<Args...>>{args...}) cout<<i<<" ";cout<<endl;}
template<typename T> struct Matrix{
int row, col;
vector<vector<T>> mat ;
private:
void init_(vector<vector<T>> A){
row = A.size();
col = A[0].size();
mat = A;
}
void init_(vector<T> 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<T>(1));
rep(i,row) mat[i][0] = A[i];
}
}
Matrix<T> pow_(ll k){
assert(row == col);
vector<vector<T>> E(row,vector<T>(row,0));
rep(i,row) rep(j,row) if(i == j) E[i][j] = 1;
Matrix<T> res(E);
Matrix<T> X(mat);
while(k > 0){
if(k & 1) res *= X;
X *= X;
k >>= 1 ;
}
return res;
}
void transpose_() {
vector<vector<T>> res(col,vector<T>(row));
rep(i,row) rep(j,col) res[j][i] = mat[i][j];
mat = res;
swap(row,col);
}
void concat_col_(vector<T> &Y) {
Matrix X(Y);
concat_col_(X);
}
void concat_col_(vector<vector<T>> &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<T> &Y) {
Matrix X(Y,true);
concat_row_(X);
}
void concat_row_(vector<vector<T>> &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<vector<T>> res(x,vector<T>(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<T>&operator[](int i) { return mat[i] ; }
Matrix(int n): row(n), col(0) { mat.resize(row); }
Matrix(vector<T> A, bool row_matrix = false) { init_(A, row_matrix); }
Matrix(vector<vector<T>> A){ init_(A); }
void init(vector<T> A, bool row_matrix = false) { init_(A, row_matrix); }
void init(vector<vector<T>> 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<vector<T>> &Y) { concat_col_(Y); }
void concat_col(vector<T> &Y) { concat_col_(Y); }
void concat_col(Matrix &Y) { concat_col_(Y); }
void concat_row(vector<vector<T>> &Y) { concat_row_(Y); }
void concat_row(vector<T> &Y) { concat_row_(Y); }
void concat_row(Matrix &Y) { concat_row_(Y); }
};
// function : return : description
// -----------------------------------------------------
// init(vector<T>, row_matrix) : void : 1次元ベクトルに対して行列化する, 列行列か行行列を選択できる
// init(vector<vector<T>>) : void : 2次元ベクトルに対して行列化する
// row_size() : int : 行の大きさ
// col_size() : int : 列の大きさ
// pow(k) : Matrix : 行列をk乗する(n * n 行列であること)
// transpose() : void : 転置する
// concat_col(vector<vector<T>>) : void : 列に関して結合する
// concat_col(vector<T>) : void : 列に関して結合する
// concat_col(Matrix) : void : 列に関して結合する
// concat_row(vector<vector<T>>) : void : 列に関して結合する
// concat_row(vector<T>) : 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<ll> 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();
}