結果
問題 | No.2441 行列累乗 |
ユーザー |
👑 |
提出日時 | 2023-10-06 17:29:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 3,434 bytes |
コンパイル時間 | 1,014 ms |
コンパイル使用メモリ | 122,604 KB |
最終ジャッジ日時 | 2025-02-17 04:38:48 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include <iostream> #include <cmath> #include <algorithm> #include <iomanip> #include <string> #include <vector> #include <set> #include <stack> #include <queue> #include <map> #include <bitset> #include <complex> #include <cctype> #include <utility> #include <climits> #include <numeric> #include <functional> using namespace std; using ll = long long; using P = pair<ll,ll>; const ll MOD = 998244353; const ll MODx = 1000000007; const int INF = (1<<30)-1; const ll LINF = (1LL<<62LL)-1; const double EPS = (1e-10); P ar4[4] = {{0,1},{0,-1},{1,0},{-1,0}}; P ar8[8] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}; template <typename T> vector<T> make_vector(size_t a, T b) { return vector<T>(a, b); } template <typename... Ts> auto make_vector(size_t a, Ts... ts) { return vector<decltype(make_vector(ts...))>(a, make_vector(ts...)); } /* 確認ポイント cout << fixed << setprecision(n) << 小数計算//n桁の小数表記になる 計算量は変わらないが楽できるシリーズ min(max)_element(iter,iter)で一番小さい(大きい)値のポインタが帰ってくる count(iter,iter,int)でintがiterからiterの間にいくつあったかを取得できる */ /* function corner below */ /* Function corner above */ /* comment outed because can cause bugs __attribute__((constructor)) void initial() { cin.tie(0); ios::sync_with_stdio(false); } */ template <typename T> struct mat{ vector<vector<T>> x; int h,w; mat():x(vector<vector<T>>()){} mat(int h,int w):x(vector<vector<T>>(h,vector<T>(w))),h(h),w(w){} mat(int h,int w, T c):x(vector<vector<T>>(h,vector<T>(w,c))),h(h),w(w){} mat(vector<vector<T>> A):x(A),h(A.size()),w(A[0].size()){} vector<T>& operator[](int i){return x[i];} mat& operator*=(mat& y){ mat<T> ret(h,y.w,0); if(w != y.h){ for(int i = 0; h > i; i++){ for(int j = 0; y.w > j; j++){ ret[i][j] = -1; } } }else{ for(int i = 0; h > i; i++){ for(int j = 0; y.w > j; j++){ for(int k = 0; w > k; k++){ ret[i][j] = ret[i][j] + x[i][k]*y[k][j]; } } } } for(int i = 0; h > i; i++){ x[i].resize(y.w); } w = y.w; for(int i = 0; h > i; i++){ for(int j = 0; y.w > j; j++){ x[i][j] = ret[i][j]; } } return *this; } mat operator*(mat y){return mat(*this) *= y;} mat pow(long long n){//正方行列のみ mat<T> res(h,w); mat<T> ret(h,w,0); mat<T> a(h,w); for(int i = 0; h > i; i++){ ret[i][i] = 1; } for(int i = 0; h > i; i++){ for(int j = 0; w > j; j++){ a[i][j] = (*this)[i][j]; } } while(n > 0){ if(n & 1){ ret *= a; } a *= a; n/=2; } for(int i = 0; h > i; i++){ for(int j = 0; w > j; j++){ res[i][j] = ret[i][j]; } } return res; } friend istream &operator>>(istream &is, mat &m){ for(int i = 0; m.h > i; i++){ for(int j = 0; m.w > j; j++){ is>>m.x[i][j]; } } return is; } friend ostream &operator<<(ostream &os, const mat &m){ for(int i = 0; m.h > i; i++){ for(int j = 0; m.w > j; j++){ os << m.x[i][j]; if(j+1 != m.w)cout << " "; } if(i+1 != m.h)cout << "\n"; } return os; } }; int main(){ mat<int> A(2,2);cin>>A; cout << A.pow(3) << endl; return 0; }